Leo.K | To become a cooler Developer

오늘도 정렬로 분류되는 알고리즘 문제를 풀어보도록 하자. 문제의 난이도가 골드 2로 올라와서 그런지 따져야 할 조건도 많고, 풀이도 떠올리기가 간단하지는 않았다. 기본 베이스는 정렬과 그리디 알고리즘이지만, 이번 문제는 우선순위 큐라는 자료구조를 적당히 잘 사용해서 풀어야 한다. https://www.acmicpc.net/problem/1202 1202번: 보석 도둑 첫째 줄에 N과 K가 주어진다. (1 ≤ N, K ≤ 300,000) 다음 N개 줄에는 각 보석의 정보 Mi와 Vi가 주어진다. (0 ≤ Mi, Vi ≤ 1,000,000) 다음 K개 줄에는 가방에 담을 수 있는 최대 무게 Ci가 주어진다. (1 ≤ Ci www.acmicpc.net 1. 문제 분석 보석의 수 N과 가방의 수 K의 최댓값이 ..

오늘 풀이해 볼 문제는 지난 시간과 동일하게 그리디 알고리즘을 적용하는 정렬파트의 문제이다. 지난 번에 풀었던 보물보다는 한 번더 생각을 해야 하지만 크게 복잡하지는 않으니 문제부터 보도록 하자. https://www.acmicpc.net/problem/1946 1946번: 신입 사원 첫째 줄에는 테스트 케이스의 개수 T(1 ≤ T ≤ 20)가 주어진다. 각 테스트 케이스의 첫째 줄에 지원자의 숫자 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개 줄에는 각각의 지원자의 서류심사 성 www.acmicpc.net 문제 분석 최대한 많은 신입사원을 뽑아야 한다. 뽑힌 신입사원들 끼리는 우열을 가릴 수 없어야 한다. 우열을 가릴 수 없다 : 서류 혹은 면접이 나와 다른 한 사람과 비교했을 때 반..

연초에 계획했던 바와는 다르게 또 다시 귀찮음이 용솟음 치며 열심히 알고리즘을 풀고 정리하겠다 했던 다짐이 한 동안 죽어있다가 연말이 되어서야 다시 살아난다. 나름 직장인이 된지도 어언 만 2년차를 바라보고 있는 시점에 진짜로 다시금 마음을 잡고 꾸준히 공부를 하고자 한다. 매일 공부를 할 수 있는 주기적인 시간이 나오는 것은 아니지만, 시간이 되는 날에라도 놀지 않고 한 문제씩이라도 문제를 풀면서 개념을 정리하고자 한다. 오늘 풀어볼 문제는 백준 1026에 속해 있는 정렬 파트 문제이다. https://www.acmicpc.net/problem/1026 1026번: 보물 첫째 줄에 N이 주어진다. 둘째 줄에는 A에 있는 N개의 수가 순서대로 주어지고, 셋째 줄에는 B에 있는 수가 순서대로 주어진다. N..

오늘은 자료구조 편 문제 풀이 2번째 시간이다. https://www.acmicpc.net/problem/1546 1546번: 평균 첫째 줄에 시험 본 과목의 개수 N이 주어진다. 이 값은 1000보다 작거나 같다. 둘째 줄에 세준이의 현재 성적이 주어진다. 이 값은 100보다 작거나 같은 음이 아닌 정수이고, 적어도 하나의 값은 0보 www.acmicpc.net 문제를 읽어보고 시간 복잡도 -> 분석 -> 텍스트 코딩 -> 실제 코딩 순서로 진행해 보자 1. 시간 복잡도 해당 문제의 시간 제한은 2초이기 때문에 2억 번의 연산 안에 마무리하면 된다. 문제에서 제시되는 데이터의 크기가 1000개 이하이기 때문에 일반적인 연산을 통해서도 시간제한 나오기는 쉽지 않을 것이다. 2. 분석 최고점을 구한 후에 ..

동적계획법 주어진 문제를 여러 부분 문제들로 나누어 푼 다음, 그 결과들로 큰 문제를 푸는 알고리즘 어떤 문제를 풀기 위해 해결해야 하는 부분 문제의 개수가 k개라고 한다면, 전체적으로 풀어야하는 문제의 개수는 O(kN)개가 될 것이다. 이때 k가 충분히 무시할 수 있을 정도로 작은 수이고, 각가의 문제를 푸는데 걸리는 시간이 O(1)이라면, 문제의 결과를 저장할 O(N)의 메모리가 필요하며, O(N)만큼의 시간이 소요된다. 분할 정복 vs DP 분할하는 점은 동일하지만 전자는 겹치는 부분문제가 없지만, 후자는 있다는 것이다. 따라서 메모이제이션 기법으로 비효율적인 반복 연산을 줄인다. Greedy vs DP 모든 경우를 메모리까지 소비해가며 샅샅이 체크하는 점에서 전자보다 후자가 실행 시간은 길지만, ..

동적 계획법 주어진 문제를 여러 개의 부분 문제들로 나누어 푼 다음, 그 결과들로 주어진 큰 문제를 푸는 것 F(N)을 구하기 위해서 풀어야 하는 문제의 개수는 O(N)개 이고, 이 답을 모두 저장할 O(N)의 메모리가 필요하며, 각각의 문제를 푸는 데 걸리는 시간이 O(1)이므로 O(N)개의 문제를 푸는 데 O(N)의 시간이 든다. 분할 정복 VS DP 분할정복과의 차이점은 분할정복은 문제를 분할했을 때 생성되는 부분 문제들 중 겹치는 문제가 발생하지 않는다. 하지만 DP는 겹치는 문제가 발생하기 때문에 메모이제이션 기법이 필요하다. EX) 피보나치 -> F(N)[구해야할 문제] = F(N-1) [ 부분 문제 ] + F(N-2) [ 부분 문제 ] Greedy VS DP 모든 경우를 메모리까지 소비해가며..

취업을 하고 자사의 솔루션을 학습한다는 핑계로 미뤄두었던 알고리즘 학습을 다시금 천천히 시작해보려 한다. 오늘은 트리부터 시작해서 간단한 개념 정리와 문제풀이를 하려고 한다. 트리는 노드와 에지로 연결된 그래프의 특수한 형태로, 주요 특징은 아래와 같다. 순환 구조를 가지고 있지 않고, 1개의 루트 노드가 존재한다. 루트 노드를 제외한 나머지 노드는 반드시 단 하나의 부모노드를 가진다. 2개 이상의 부모 노드가 있다면 순환구조가 생길 수 밖에 없음 트리의 부분 트리 역시 트리의 모든 특징을 따른다. 트리의 구성요소 구성 요소 설명 노드 데이터의 index와 value를 표현하는 요소 에지 노드와 노드의 연결관계를 나타내는 선 루트 노드 트리에서 가장 상위에 존재하는 노드 부모 노드 두 노드 사이의 관계에..

최근에 네이버 공채를 지원해보고, 코딩테스트를 보았다. 나름 준수하게 푼 것 같긴 한데, 생각보다 애먹었던 내용과 비슷했던 문제를 다시 풀어보고자 한다. 너비우선탐색을 진행하는데, 실제탐색은 2차원 배열로 진행하지만, 각 요소가 익숙했던 정사각형이 아닌 정육각형으로 이질감이 있게 생겼다. 물론 이에 따라서 이동가능한 경우의 수도 (상, 하, 좌, 우) 4가지에서 (좌, 좌상, 좌하, 우, 우상, 우하)6가지로 바뀌었다는 점, 더불어 현재 행이 짝수인지, 홀수인지에 따라서 이동하는 위치가 다르다는 것이다. 말로만 설명하면 어려우니 간단한 예시를 보자. 문제에서 예시로 주어진 그림을 보면 척 봐도 모든게 복잡하다. 일단 그림부터도 불편하긴 한데, 행과 열이 거꾸로 되어 있기까지 하다니,,, 하지만 이는 모양..

https://www.acmicpc.net/problem/16236 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가 www.acmicpc.net 문제를 풀기 위한 조건이 많기도 하지만 조건을 맞추기가 굉장히 까다로웠다. 충족해야 하는 조건을 크게 잡아보면 아래와 같다. 최단거리 탐색 방법 최단거리하면 떠오르는 알고리즘은 단연 다익스트라가 먼저일 것이다. 하지만 모든 간선의 가중치가 1인 경우에는 더 효율적인 BFS가 있기 때문에, BFS를 활용해서 풀이해보도록 하자. 거리가 같은 경우 우선순위가 높은 물고기를 잡으러 가는 방법 가장..

https://www.acmicpc.net/problem/16234 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모 www.acmicpc.net 오늘부터는 본격적으로 코딩테스트를 준비하기 위해서 그래프 탐색문제를 집중적으로 풀이해보려 한다. 오늘 풀이해볼 문제는 골드5문제로 너비우선 탐색을 이용해서 구현을 하는 문제이다. 문제만 보면 조금 복잡해 보일 수 있지만, 예시에 친절하게 나와있기 때문에, 인구이동이 일어나는 날에 필요한 작업을 해주고, 최종적으로 인구이동이 일어난 날을 반환하는 것이다. 천천히 단계적으로 풀이를 해보..

이제 슬슬 그래프에 대한 모든 개념을 정복하기 위해서 위상정렬 문제를 풀이하면서 간단하게 개념을 소개할까 한다. 그래프의 종류에 대해서는 아래 필자의 블로그를 학습하고 오기를 바란다. https://cm-me0410.tistory.com/78 그래프(Graph)의 종류 용어 설명 그래프(Graph) 노드와 간선을 하나로 모아 놓은 자료 구조 정점(Vertex) 노드라고도 하며, 정점에는 데이터가 저장된다. 간선(Edge) 링크라고도 하며, 노드간의 관계를 나타낸다. 인접 정점 cm-me0410.tistory.com 위상정렬(Topology Sort)은 사이클이 없는 방향 그래프에서 노드간의 순서를 찾는 알고리즘이다. 노드의 수를 V, 에지의 수를 E라고 했을 때, 시간 복잡도는 O(V+E)이다. 위상정렬..

오늘은 저번시간에 이어서 분할정복 문제를 풀었다. 분할을 2개로 하는 것이 아닌 3개로 하는 것이기 때문에 조금 까다로울 수 있지만, 이전에 분할정복을 사용한 별찍기 문제를 한 번 풀어보았더니 이 문제는 비교적 쉽게 접근하여 풀 수 있었다. 이 문제를 풀이해보셨다면 아래의 문제도 풀어보시면 좋을 것 같다. basecase만 바꿔주면 된다. https://www.acmicpc.net/problem/2447 2447번: 별 찍기 - 10 재귀적인 패턴으로 별을 찍어 보자. N이 3의 거듭제곱(3, 9, 27, ...)이라고 할 때, 크기 N의 패턴은 N×N 정사각형 모양이다. 크기 3의 패턴은 가운데에 공백이 있고, 가운데를 제외한 모든 칸에 별이 www.acmicpc.net [ 문제 풀이 ] 종이에 적힌 ..