문제 링크 https://www.acmicpc.net/problem/20164 20164번: 홀수 홀릭 호석 호석이는 짝수랑 홀수 중에서 이니셜이 같은 홀수를 더 좋아한다. 운전을 하던 호석이는 앞차의 번호판이 홀수로 가득할 때 사랑스러움을 느낄 정도이다. 전화번호도 홀수만 있고 싶다. 그렇게 www.acmicpc.net 문제 풀이 하나의 수가 주어졌을 때 호석이는 한 번의 연산에서 다음과 같은 순서를 거친다. 1. 수의 각 자리 숫자 중에서 홀수의 개수를 종이에 적는다. 2. 수가 한 자리이면 더 이상 아무것도 하지 못하고 종료한다. 3. 수가 두 자리이면 2개로 나눠서 합을 구하여 새로운 수로 생각한다. 4. 수가 세 자리 이상이면 임의의 위치에서 끊어서 3개의 수로 분할하고, 3개를 더한 값을 새로..

메모리 초과의 경우 - 재귀 호출로 인한 스택 오버 플로우 발생할 경우 종료 조건 확인 - 변수 타입이 범위 초과할 경우 (long인데 int로 선언하거나) 시간 초과의 경우 (1초에 1억번 연산을 가정했을때) - 시간 복잡도가 적철지 못한 문제 풀이 했을 때 - 주어진 query에 대한 결과나, 조합에 대한 결과를 구할 때 전처리 후 사용하기 결과 값을 구해지는데 실패가 케이스가 뜨는 경우 - 변수 타입, 최대치, 초기화 확인 문제 링크 https://www.acmicpc.net/problem/20181 20181번: 꿈틀꿈틀 호석 애벌레 - 효율성 꿈틀꿈틀 호석 애벌레는 N 개의 먹이가 일렬로 나열된 나뭇가지를 오른쪽으로 기어가려고 한다. 시작하는 순간의 호석 애벌레가 0의 위치에 있고 i 번째 먹이..

HashMap - 내부적으로 hash 값을 인덱스로 하여 자료 구조 관리 - Key 중복 x , Value 중복 허용 - hash 값의 중복이 발생하는 경우 LinkedList, Tree 자료 구조 사용하여 해결하고 있음  Method 살펴보기put()- key 로 만든 hash 값에 해당하는 bucket이 없는 경우 신규 Node 저장, 있는 경우 value를 덮어씌움- 동일한 hash 값이 있는 경우 ThreadHold 값에 따라 LinkedList, Tree 로 자료 연결되어 관리 참고. HashMap put() 살펴보기  예시테스트 파일에서 공통으로 사용할 Map의 데이터를 초기화public class HashMapTest { Map map = new HashMap(); @BeforeE..

Set ? - 집합을 다루는 자료구조- 중복 x, 순서 x- 대표적인 구현체 : HashSet / TreeSet / LinkedHashSet / EnumSet- 내부적으로 Map 자료 구조에 Key에 데이터를 담는다 (Map은 Key의 중복 허용하지 않음)//java.util.HashSet.classprivate transient HashMap map;private static final Object PRESENT = new Object();public HashSet() { this.map = new HashMap();}//..public boolean add(E e) { return this.map.put(e, PRESENT) == null; // HashMap의 Key에 element를 담..

Array (배열)- 동일한 자료형(Data Type)의 데이터를 연속된 공간에 저장하기 위한 자료 구조- 기본형(Primitive Types) 또는 인스턴스(Reference Type)을 저장하기 위해 배열 사용- 처음 선언시 길이를 지정하기 때문에 런타임 환경에서 크기를 변경할 수 없다 (정적 할당, static allocation) Array 선언 및 초기화 예시# 1int[] arr = new int[10];arr[1] = 1; // .. 이하 생략# 2int[] arr = new int[] {1, 2, 3, 4};# 3 int[][] arr = {{1, 0}, {0, 1}, {-1, 0}, {-1, 0}}; 장점구조가 간단하고, 인덱스로 해당 element에 접근할 경우 시간 복잡도 O(1) 소..

설명 - 피벗을 기준으로 좌측에 피벗 보다 작은 값, 우측에 피벗보다 큰 값을 위치 시킴 - partition(파티션)을 나눠 행위를 반복한다 - partition을 최소 까지 나눴을 때는 이미 정렬이 완료된 상태이다. 파티션을 나누기 전에 pivot 기준으로 임의 정렬을 하고 partition을 나눠 행위 반복하면 더이상 나눌 수 없을 때 이미 정렬이 완료된다. 반대로 merge sort의 경우 제일 작은 크기 까지 파티션을 먼저 나눈 후 병합을 하면서 정렬 수행한다. *과정 (1) pivot 을 정함 (2) 양쪽 끝에 L, R 포인터를 두고 다음 수행 2-1) L < pivot 경우 포인터 증가 L += 1 (pivot 기준 좌변은 항상 작아야 하므로, 큰 값이 나올 때까지 포인터 이동) 2-2) p..

설명 1) 리스트의 길이가 1이 될 때 까지 나눈다(mergeSort()) 2) 왼쪽과 오른쪽 리스트를 대소 비교 하여 정렬된 결과(merge()) 반환 - 재귀 함수 호출하여 작은 문제로 나눈 후 큰 문제의 정답을 구한다 - 재귀 호출로 인해 스택 오버플로우 발생가능(단점) - Java의 경우 인스턴스 메서드 *.subList(int from, int to) 사용하여 쉽게 리스트 분할 가능하다 시간 복잡도 : O(NlogN) - 파티션을 나누는데 logN 만큼 걸리고, 다시 병합할 경우 N 만큼의 소요 공간 복잡도 : O(N) 영상 참고 https://www.youtube.com/watch?v=3j0SWDX4AtU 작은 문제로 나눠서 큰 문제의 해답을 구한다 코드 - 오름차순 정렬 기준으로 작성 - 내..

문제 링크 https://www.acmicpc.net/problem/10942 10942번: 팰린드롬? 총 M개의 줄에 걸쳐 홍준이의 질문에 대한 명우의 답을 입력으로 주어진 순서에 따라서 출력한다. 팰린드롬인 경우에는 1, 아닌 경우에는 0을 출력한다. www.acmicpc.net 문제 풀이 시간복잡도 - 상향식(Bottom-Up) 풀이시 O(N^2) = O(2000^2) - 하향식(Top-Down) 풀이시 O(N!) = O(2000!) 시간 초과 발생 가능 -> memorization 기법으로 시간내 풀이 가능 *팰린드롬 (PALINDROME) ? - 길이가 1일 때 자기 자신도 팰린드롬이다. (1, 2, 3, ...) - 길이가 2인 경우 두 숫자가 동일할때 팰린드롬이다. (11, 22) - 길이가..

문제 링크 https://www.acmicpc.net/problem/11049 11049번: 행렬 곱셈 순서 첫째 줄에 입력으로 주어진 행렬을 곱하는데 필요한 곱셈 연산의 최솟값을 출력한다. 정답은 231-1 보다 작거나 같은 자연수이다. 또한, 최악의 순서로 연산해도 연산 횟수가 231-1보다 작거나 같 www.acmicpc.net 문제 풀이 백준 11066 파일 합치기와 비슷한 문제였으나 행렬 곱셉을 어떻게 DP 배열로 처리할 지에 대해 파악하기 힘든 문제였다. - 상향식(Bottom-Up)으로 풀 경우 시간 복잡도 O(N^2) - 하향식(Top-Down)으로 풀경우 O(N!) , memorization 기법 활용하여 시간 내에 풀이 가능 - 최대치는 Integer 범위 - 행렬 A (m x k) ,..

문제 링크 https://www.acmicpc.net/problem/1949 1949번: 우수 마을 N개의 마을로 이루어진 나라가 있다. 편의상 마을에는 1부터 N까지 번호가 붙어 있다고 하자. 이 나라는 트리(Tree) 구조로 이루어져 있다. 즉 마을과 마을 사이를 직접 잇는 N-1개의 길이 있으며, www.acmicpc.net 문제 풀이 - 인접 리스트 사용하여 시간 복잡도 O(V + E) = O(10,000 + 9,999) - 트리이기 때문에 간선의 수 = 노드의 수 - 1 - DFS 방식으로 리프 노드 구하는 문제에서 응용하는 문제로 2차원 배열로 방문 여부에 따라 조건 처리를 하게 된다 - 시작 노드는 1로 해서 최종적으로 DP[1][0], DP[1][1] 중 최대값이 최대 인구에 해당한다 DP..

문제 링크 https://www.acmicpc.net/problem/1509 1509번: 팰린드롬 분할 세준이는 어떤 문자열을 팰린드롬으로 분할하려고 한다. 예를 들어, ABACABA를 팰린드롬으로 분할하면, {A, B, A, C, A, B, A}, {A, BACAB, A}, {ABA, C, ABA}, {ABACABA}등이 있다. 분할의 개수의 최솟값을 출력하 www.acmicpc.net 문제 풀이 스스로 풀지 못하여서 기술 블로그를 참고 하였고, 이번 문제를 통해 DP 기법과 Two Poiner 기법 응용하는 방식에 대해 처음으로 알게 되었다. 풀이 후 몇일 있다가 손으로 그려보고 Top-Down, Bottom-Up 풀이하는데 역시나 쉽지 않은 문제인 것 같다. 가짜문제 정의, 초기화 항목 .. 단순히..

문제 링크 https://www.acmicpc.net/problem/15681 15681번: 트리와 쿼리 트리의 정점의 수 N과 루트의 번호 R, 쿼리의 수 Q가 주어진다. (2 ≤ N ≤ 105, 1 ≤ R ≤ N, 1 ≤ Q ≤ 105) 이어 N-1줄에 걸쳐, U V의 형태로 트리에 속한 간선의 정보가 주어진다. (1 ≤ U, V ≤ N, U ≠ V) www.acmicpc.net 문제 풀이 - 시간 복잡도 O(V + E) // 인접 리스트 사용 - 백준 링크에 들어가보면 하단에 친절하게 로직을 설명하고 있어 참고하면 됨 # 입력 트리를 그릴 경우 5번 Root 기준 5 4 6 3 7 8 9 1 2 # subtree 결과 subtree [0, 1, 1, 3, 4, 9, 4, 1, 1, 1] 제출 코드 ..

문제 링크 https://www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 문제 풀이 - 시간복잡도 O(N) 처음 문제 풀이시 아래 (1)과 같이 점화식을 사용하여 문제 풀이를 수행했다 // i = 1, 2 일때 초기화 수행 DP[i] = DATA[i] + Math.max(DATA[i - 1] + DP[i - 3], DP[i - 2]) 이후에 더 나은 방식이 없는지 고민하던 중 예전에 구입했던 패스트 캠퍼스 강의를 확인했고, 2차원 배열을 사용하여 의미 부여를 통해 풀이하..

문제 링크 https://www.acmicpc.net/problem/15990 15990번: 1, 2, 3 더하기 5 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 1,000,000,009로 나눈 나머지를 출력한다. www.acmicpc.net 문제 풀이 - 시간 복잡도 : O(N) - 1,2,3 더하기 문제에서 조금 변형된 문제, 상향식, 하향식 연습하기 좋은 문제 - 단, 같은 숫자를 연속적으로 붙일 수 없기 때문에 이전 숫자에서 무엇이 사용되었는지 상태값을 기록할 필요가 있다 (2차원 배열 사용) - 간단하게 2차원 배열로 해서 1 ~ 3 숫자 사용 여부를 표기하고 동일하게 점화식으로 구하면 됨 - 최대치 long DP[N + 1][4] 2차원 배열 생성 ( DP[N][1..

문제 링크 https://www.acmicpc.net/problem/15988 15988번: 1, 2, 3 더하기 3 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 1,000,000,009로 나눈 나머지를 출력한다. www.acmicpc.net 문제 풀이 - 시간 복잡도의 경우 둘다 O(N) - 최대치의 경우 long ( 나머지 연산 처리해도 N이 최대이면 범위가 넘는 듯 함) - 피보나치에서 조금 변형된 기본 DP 문제 - 상향식, 하향식 형식 연습하기 좋은 기본 문제 0 1 2 3 4 0 1 1 + 1 2 1 + 1 + 1 2 + 1 3 1 + 1 + 1 + 1 2 + 1 + 1 3 + 1 1 + 1 + 2 2 + 2 1 + 3 점화식 DP[i] = (DP[i - 1] + ..

문제 링크 https://www.acmicpc.net/problem/2688 2688번: 줄어들지 않아 첫째 줄에 테스트 케이스의 개수 T(1

문제 링크 https://www.acmicpc.net/problem/1495 1495번: 기타리스트 첫째 줄에 N, S, M이 주어진다. (1 ≤ N ≤ 50, 1 ≤ M ≤ 1,000, 0 ≤ S ≤ M) 둘째 줄에는 각 곡이 시작하기 전에 줄 수 있는 볼륨의 차이가 주어진다. 이 값은 1보다 크거나 같고, M보다 작거나 같다. www.acmicpc.net 문제 풀이 - 시간복잡도의 경우 상향식 O(N), 하향식 O(2^N) 소요됨 - 하향식의 경우 메모리제이션 기법 사용하여 풀이 - 상향식으로 풀 때 초기항부터 누적하는 형태로 풀이할 경우 최대치가 int를 초과하는 것으로 생각됨 (최대치 따로 구해보기) *하향식 풀이의 경우 아래 기술 블로그 통해 형식 이해함 https://steady-coding...

문제 링크 https://www.acmicpc.net/problem/5557 5557번: 1학년 상근이가 1학년 때, 덧셈, 뺄셈을 매우 좋아했다. 상근이는 숫자가 줄 지어있는 것을 보기만 하면, 마지막 두 숫자 사이에 '='을 넣고, 나머지 숫자 사이에는 '+' 또는 '-'를 넣어 등식을 만들며 놀 www.acmicpc.net 문제 풀이 - 입력의 경우 int 배열로 100개까지 받으므로 400byte - 연산에 필요한 DP의 경우 행20 * 100 * 8byte = 16KB 정도 메모리 잡음 - 최대치의 경우 출력에 2^63 -1 명시되어 있기 때문에 long으로 처리 시간 복잡도 상향식 (Bottom-Up) 하향식(Top-Down, 재귀 함수) O(N * 20) O(2^n) = O(2^100) - ..