0. 학습 목적인터페이스의 구성요소에 대해 이해한다.인터페이스는 언제 쓰는지 이해한다.1. 인터페이스란?인터페이스 란, '무엇을 할 것인가' 에 대한 명세만 적혀있는 계약 형 추상 자료형이다.(1) 계약이란?계약은 실생활에서 상호 간에 지켜야 하는 약속을 말한다. 인터페이스는 사용자와, 또 그것을 구현하고자 하는 class와 두 번 계약을 하게 된다.사용자와의 계약: 사용자가 인터페이스 내 원하는 매서드를 규칙에 맞게 호출하면, 사용자가 예상하는 결과를 반환 해줘야 한다.구현체와의 계약: 구현체는 추상 매서드의 규칙 (인수, 반환값)을 준수하여 구현하여야 하고, 그것의 용도에 맞는 행동을 해야 한다.(2) 인터페이스 활용의 효과구현 분리와 느슨한 결합A. 구현 분리 = 논리적 결합도 낮춤인터페이스가 없었..

0. 학습 목적String Constant Pool 이라는 개념에 대해서 이해한다.String을 왜 불변 객체로 만들었는지 유추한다.1. String Constant Pool 이란?JVM Heap에 존재하는 메모리 공간으로 불변 객체인 String 리터럴 전용 저장 공간 이다.프로그램 내부에서 선언된 모든 String 리터럴은 String Constant Pool에 저장된다.2. 특징String Literal 만 저장Pool에 존재하는 문자열이 재 선언되면, 새로 할당하지 않고 있는 거 재활용 (1) String Literal 만 저장한다.String 객체 선언 방식은 2개로 나뉜다.// 리터럴 방식 선언String str1 = "Hello World";// 객체 방식 선언String str2 = new..

0. 학습 목적String은 불변 객체임을 이해한다.유용한 String 클래스 함수를 알아둬서 알고리즘 문제를 풀 때 적용한다.1. String의 특징 : 불변성String 객체의 가장 큰 특징은 불변성이 보장 되는 객체 라는 것이다.(1) final 클래스로 선언됨final 클래스로 선언되어 있어서 상속이 불가능하다.(2) 값을 담는 멤버 변수도 private final 임String 문자열의 실질적 값을 담는 byte 배열도 private final로 선언되어 있다. 이 때문에, String 객체가 한 번 선언되면, 이후 새로운 값을 재할당 할 수 없다.(3) 그렇다면 문자열 변경 코드나 함수는 어떻게 작동할까?원래의 String 객체에 값이 추가되는 것이 아니라, 새로운 String 객체가 만들어진..

1. 요약 답변✅KEY WORD: 메모리 관리, 클래스 수준의 공유 자원, 객체 지향 위반, 숨겨진 의존성 문제, 단위 테스트가 어려움static 키워드를 사용한 변수 혹은 매서드는 컴파일시점에 딱 한번만 Method 영역에 할당된 뒤에, 프로그램 종료 시까지 유지됩니다.이러한 특성 덕에, 메모리 관리에 효율적이고, 클래스 수준의 공유 자원으로 사용되어야 하는 불변 상수나 Utill 함수를 구현할 때 사용됩니다. 하지만 static은 다음과 같은 심각한 부작용이 동반될 수 있으므로 사용 시 유의 해야 합니다.첫 번째로, 객체 지향 프로그래밍을 위반하는 키워드 입니다.static 멤버 변수를 활용하는 클래스의 객체는 자신의 상테를 스스로 완벽하게 제어하지 못하며, 타 객체나 서비스에 의해 자신의 상태가 ..

0. 학습 목적@Transactional이 무엇인지 이해한다@Transactional의 구성요소와 작동원리를 이해한다.왜 새로운 스레드에는 트랜잭션이 전파되지 않는지 이해한다.1. @Transactional 이란?Spring Framework에서 트랜잭션을 선언적으로 관리할 수 있게 만든 어노테이션(1) '선언적으로 관리한다. ' 의 의미트랜잭션 관리가 필요한 클래스나 매서드에 @Transactional 어노테이션을 '선언'만 하면, 선언된 범위를 하나의 트랜잭션 컨텍스트로 묶어서 관리해준다.장점은 다음과 같다.트랜잭션 간의 경계 파악이 쉽다.비즈니스 로직과 트랜잭션 관리 로직이 분리되어 비즈니스 로직 집중과 유지보수가 수월해진다.(2) 트랜잭션 선언 범위에 따른 의미클래스에 설정 시, 해당 클래스의 모..

1. 문제에 대하여 📦문제 링크: https://www.acmicpc.net/problem/3980(1) 조건 분석 📊2차원 배열로 11명의 선수의 포지션 별 능력치가 주어진다.만약 members(i)(j) = k 라면, i번 선수의 j 포지션 능력치는 k라는 뜻이다. 만약 members(i)(j) = 0 라면, i번 선수는 j 포지션에서 뛸 수 없다.11명의 선수를 포지션에 잘 배치해서 능력치 합계의 최대치를 출력하라.2. 코드가 나오기까지 🛠️KEY WORD: 순열, 백트래킹 순열로 포지션 별 선수 뽑기이때 현재 조회 중인 선수가 해당 포지션에서 뛸 능력이 없다면 넘어감 -> 백트래킹base-case에서 선수들의 포지션별 능력치 합계를 낸다.최대치를 갱신한다.(1) 시간복잡도 분석 ⏳11! =..

1. 문제에 대하여 📦문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/42839(1) 조건 분석 📊numbers의 문자 하나 하나를 하나의 종이 조각이라 생각한다. (즉 일의 자릿수로 이루어진 종이가 존재함) 이 종이들을 조합하여 숫자를 만들 때, 그 숫자가 소수인 경우가 몇 개 있는지 그 개수를 세어라 2. 코드가 나오기까지 🛠️KEY WORD: 순열, 소수 판정 순열로 숫자 조합을 찾는다.각 depth 마다 소수 판정을 해서, 나올 수 있는 모든 자릿수의 수에 대하여 소수 확인을 거친다.소수인 수들의 개수를 세서 반환한다. (1) 시간복잡도 분석 ⏳N개의 숫자가 주어졌을 때, 모든 자릿수의 숫자 조합을 구하는 가짓수: $_N ..

1. 문제에 대하여 📦문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/42576(1) 조건 분석 📊마라톤 참가자와 마라톤 완주자 목록이 주어졌을 때, 완주하지 못한 인원을 구하는 문제2. 코드가 나오기까지 🛠️KEY WORD: Hash Map의 compute 활용 마라톤 참가자들을 모두 HashMap 자료구조에 넣어서 정보를 저장한다. 이다.이는 동명이인을 상정하고 그렇게 만든 것이다.이후 완주자 리스트를 순회하며, 리스트의 이름을 참가자 리스트에서 지운다.지운다의 의미는 'HashMap에서 해당 이름의 value를 1 삭제한다.' 는 뜻이다. 만약 삭제했을 시, value가 0이 되면 그대로 삭제한다. (이를 쉽게 계산하기 위해..

1. 문제에 대하여 📦문제 링크: https://www.acmicpc.net/problem/16926(1) 조건 분석 📊배열을 원이라 쳤을 때, 동심원 별로 한 바퀴 돌리면 된다.2. 코드가 나오기까지 🛠️KEY WORD: 시뮬레이션(1) 배열을 회전시키는 방법문제 요구사항은 반 시계 방향으로의 회전이다. 이걸 실제로 구현하려면 나보다 뒷순서의 원소값을 나의 위치에 옮겨 담는 작업이 필수이므로, 실제 원소 재할당의 움직임은 시계 방향(문제 요구사항의 역방향)으로 이루어져야 한다.(2) 점점 안 쪽 동심원으로 들어가는 방법이것은 출발점을 정하면 쉽다. 한 번의 동심원 회전이 끝나면 (i,i) 였던 출발점을 (i+1, i+1)로 바꾸면 된다. 근데 여기서 주의해야할 지점이 있다.바로 얼마나 들어가야할..

1. 문제에 대하여 📦https://www.acmicpc.net/problem/2252(1) 조건 분석 📊키 순서별로 학생들을 정렬하려 한다.키 순서에는 순환이 존재할 수 없다. (사이클 없는 그래프)키에는 대소가 존재한다. (방향 그래프)키의 대소 관계가 일부만 존재하기 때문에, 답이 여러가지인 경우 아무거나 출력해라2. 코드가 나오기까지 🛠️KEY WORD: 위상 정렬이 문제는 전형적인 위상정렬 문제이다.만약 위상정렬에 대한 이해가 부족하신 분들은 [알고리즘] 위상정렬, 그림으로 쉽게 설명^^을 보고 오시길 바란다.처음에는 그저 진입 차수 배열 + for, while 반복문으로 문제를 풀었더니 시간이 963ms 정도로 높게 나왔다. 이를 최적화 하려면 인접리스트 + BFS 방식으로 가장 선행되는..

1. 문제에 대하여 📦https://www.acmicpc.net/problem/15683(1) 조건 분석 📊상남자의 문제 완전탐색이다.그냥 문제 조건 그대로 시간복잡도 신경 안쓰고 풀면 된다.'오류가 없다면' 순열과 조합을 써도 문제가 풀려야 한다.2. 코드가 나오기까지 🛠️KEY WORD: 순열, 완전 탐색1번2번3번4번5번출처: 해당 문제의 이미지 사진A. 순열은 어디에 쓰는가?순열은 CCTV가 동작할 수 있는 모든 경우의 수를 세기 위하여 필요로 되어진다. 위에 나오는 각 CCTV는 90도씩 회전이 가능하다. 1,3,4번은 동서남북 모두 경우의 수가 다르고, 2번은 상하, 좌우만 다르며 5번에서는 나올 수 있는 경우의 수가 딱 하나이다. cctv는 1개 이상 8개 이하일 수 있기 때문에, ..

1. 문제에 대하여 📦https://www.acmicpc.net/problem/4803(1) 조건 분석 📊트리의 수 세기사이클이 있는 그래프는 트리가 아니므로, 갯수 센 것에서 제외하기2. 코드가 나오기까지 🛠️KEY WORD: Union & Find나머지 정점 N개 간선 N-1 개 등, 다른 트리의 특징들은 해당 문제에서 2개의 정점 사이에는 하나의 간선밖에 업다고 못 박아 두었기 때문에 신경 쓸 필요가 없다. 따라서 사이클이 생기는지만 신경써서 확인해주면 된다.필자는 다음과 같은 방법을 거쳐 사이클 여부를 확인했다. (내용을 진행하기 앞서, 독자들이 Union&Find에 대해 알고 있다는 가정 하에 설명을 이어가겠다. 혹시 모르시는 분은 [알고리즘] 유니온 파인드 쉽게 이해하기 ^^를 한 번 읽..

1. 문제에 대하여 📦https://www.acmicpc.net/problem/2933(1) 조건 분석 📊배열의 오른쪽과 왼쪽에서 한 번씩 번갈아 막대기를 던져서 미네랄 파괴고드름처럼 밑둥을 치면 아래것들은 떨어진다. 떨어질 때 형태가 유지되어야 함. 즉 ㄱ 자로 떨어지면 ㄱ 자 형태 그대로 맨 끝의 문자가 x 또는 바닥을 만날 때까지 떨어진다.광물의 끝점이 하나인 경우만 주어진다. (즉 맨 아래가 하나인 경우만 주어진다. ㄱ자, ㅋ자는 가능하지만, ㄴ자 ㄷ자는 불가)2. 코드가 나오기까지 🛠️KEY WORD: BFS, 완전 탐색해당 문제는 문제에 나온 설명 그대로 구현하면 되는 시뮬레이션 문제이다.필요한 함수는 다음과 같다.A. 막대기 맞은 광물 부수기왼쪽, 오른쪽 번갈아 던지기 구현 필요B. 떨..

1. 문제 설명 📌(1) 링크🔗문제 링크(2) 해설🕵시작도시에서부터 도착도시로 가며 최대한 많은 이윤을 내는 것이 목표(+도시에서 장사해서 얻는 이득, - 이동 비용) 2. 생각의 흐름: 코드가 나오기까지 🗃️(1) IDEA 도출💡KEY WORD: 벨만포드, BFS주목해야할 문제 조건은 다음과 같다.방문한 도시는 또 방문할 수 있다.시작 지점에서 도착 지점으로 도달할 수 없는 경우 gg 출력도착지점에 도착했을 시 돈을 무한히 가질 수 있다면, Gee 출력A. 조건 1에 대하여방문한 도시를 또 방문할 수 있다는 조건에서 벨만 포드를 고려했다. 벨만포드는 총 N-1번의 완화 과정을 거치며, 시작 정점에서 모든 정점까지의 최단 거리를 구한다.(이는 시작 지점에서 갈 수 있는 제일 먼 정점이라도, 최대..

1. 문제 설명 📌(1) 링크🔗https://www.acmicpc.net/problem/10775(2) 해설🕵게이트와 비행기가 존재비행기마다 착륙할 수 있는 게이트의 한계치가 있음. (만약 문제에서 비행기의 정차 $g_i$를 5라고 하면, 해당 비행기는 GATE 1번부터 5번까지 중에서 한 곳에만 착륙해야함.)만약 임의의 비행기가 착륙할 수 있는 GATE가 없다면 비행기를 폐쇄해야함.2. 생각의 흐름: 코드가 나오기까지 🗃️(1) IDEA 도출💡KEY WORD: Greedy Algorithm, Union Find첫 번째 시도 Greedy Algorithm각 비행기마다 그 비행기가 착률할 수 있는 GATE의 끝 순번부터 시도해서 가능한 게이트에 댄다.이렇게 하는 이유는 다음과 같다.만약 비행기 착..

1. 문제 설명 📌(1) 링크🔗https://www.acmicpc.net/problem/4195(2) 해설🕵각 TC마다, 친구 맺는 숫자와 실제 친구 맺는 사람들이 (a, b) 형태로 이름이 나열된다.각 ROW 마다 친구를 맺었을 때, 두 사람의 친구 네트워크 (중복 제거하거 각자 파도타기 해서 들어갈 수 있는 친구 수)를 출력하라.2. 생각의 흐름: 코드가 나오기까지 🗃️(1) IDEA 도출💡KEY WORD: UNION FIND, Hash Map 변환이름 자체가 문자열로 주어지는데, 이를 매번 다 equals()로 확인하면, 시간 초과가 날 것이 뻔했다. 왜냐하면 TC가 몇 개인지도 모르는데, 한 번의 TC 당 100,000 개의 (a,b) 문자열 쌍이 주어진다. 그럼 최대 200,000개의 ..

1. 문제 설명 📌(1) 링크🔗https://www.acmicpc.net/problem/1043(2) 해설🕵지민이가 거짓말쟁이가 되는 경우의 수 2가지진실을 모르는 사람들만 있는 파티에서 영호가 지민이의 과장된 무용담을 듣는다.이후 영호가 진실을 아는 사람 파티에 또 간다. (선 과장 - 후 진실)진실을 아는 사람이 한 명이라도 있는 파티에서 영호가 지민의 진실된 이야기를 듣는다.이후 영호만 진실된 이야기를 알고, 나머지는 모르는 상황인 추후 파티에서 지민이의 과장된 무용담을 듣는다.(선 진실 - 후 과장)따라서 진실을 먼저 알게되든 나중에 알게되든 상관없이 진실을 알게만 된다면 지민이는 거짓말쟁이가 된다. 실시간성 계산이 없으므로, 모든 유니온 파인드 진행 후 파티의 유효성 검증을 해도 괜찮다...

0. 들어가며HashMap 자료형을 사용하며 풀어야 했던 문제 중, compute를 쓸 일이 있었는데, 갑자기 해당 내용이 생각이 나지 않아서 다시 정리한다. HashMap의 compute는 putIfPresent, putIfAbsent 등을 전부 포괄하며 내가 하고 싶은 작업의 대부분을 할 수 있어서 편하다. 이번엔 compute에 대해 자세히 알아보겠다.1. 형태V compute(K key, BiFunction remappingFunction);// exmap.compute(key, (key,oldValue) -> {... return newValue});반환형: 반환형의 V는 현재 함수를 부른 Map의 value의 자료형을 뜻한다. 만약 HashMap 였다면 V는 Integer가 되는 형식이다.인수..

1. 문제 설명 📌(1) 링크🔗https://www.acmicpc.net/problem/9663(2) 해설🕵체스에서 Queen은 8방향을 갈 수 있는 말이다. (사방 탐색 + 사방의 대각)체스는 자신이 한 번의 움직임으로 갈 수 있는 경로에 있는 말을 죽일 수 있다.이 Queen을 모든 행에 하나씩 둘 때, 서로가 서로를 죽일 수 없게 두는 경우의 수를 구하는 것이다. 2. 생각의 흐름: 코드가 나오기까지 🗃️(1) IDEA 도출💡KEY WORD: BACK TRACKINGN의 최대값이 15라서, 1515 체스판에서 백트래킹을 해도 시간 초과가 나지 않는다. 따라서 *백 트래킹**을 활용한다. 경로가 겹치는지 확인하기 위해서는 다음 4가지를 확인해야 한다.1️⃣ 현재 Queen을 놓으려는 행에 이..

1. 문제 설명 📌(1) 링크🔗https://www.acmicpc.net/problem/1934(2) 해설🕵최대공약수와 최소 공배수의 관계를 알고 있는지 묻는 문제2. 생각의 흐름: 코드가 나오기까지 🗃️(1) IDEA 도출💡KEY WORD: 유클리드 호제법유클리드 호제법의 개념만 알면 문제가 쉬워서 바로 SUDO CODE로 넘어가겠다. 혹시 개념에 대해 모르시는 분들은 다음 두 개의 포스팅을 한번 읽고 오시길 바란다.https://dalcheonroadhead.tistory.com/485https://dalcheonroadhead.tistory.com/486(2) SUDO CODE 📜1️⃣ 입력으로 받은 A, B의 최대공약수 G를 구한다.2️⃣ G 로 A,B를 나눠서 몫인 a, b를 얻는다...

1. 문제 설명 📌(1) 링크🔗https://www.acmicpc.net/problem/11689(2) 해설🕵오일러의 피를 알고 있는지 묻는 문제이다. 오일러의 피 함수 $φ(n)$ 이란, n 이하 자연수 중 n과 서로소인 숫자의 개수를 반환하는 함수이다.저번 오일러의 피 이론 정리 포스팅에서는 N개의 영역 내의 모든 수에 대한 오일러의 피 함수를 구했는데, 이번 문제는 N의 최대값이 $10^{12}$ 여서 그러한 배열을 만들 수도 없고, 문제에서도 N 하나에 대한 오일러 피 함수를 구하라 했으므로, N에 대해서만 오일러 피 함수를 구하면 된다.2. 생각의 흐름: 코드가 나오기까지 🗃️(1) IDEA 도출💡KEY WORD: 에라토스테네스의 체, 오일러 피 함수에라토스테네스의 체를 따로 구할 메모..