1.
문제 : 택배 기사 민서
2.
알고리즘 : 수학, 구현
3.
성공 여부 : 실패
4.
풀이 : 보류
5.
복기 : 실버 2 문제라고 얕봤는데, 의외의 복병이었다. 좌표의 범위가 -10억 ~ 10억이기 때문에 좌표에 대한 각각의 거리를 전부 저장할 수 없다. 따라서 좌표에 따른 거리의 수 학적인 규칙을 찾아내야 하는 문제였다. 여기서 수학적인 테크닉이 필요했다. 등비수열의 합 까먹은 거 다시 한번 보기
1.
문제 : 가장 긴 증가하는 부분 수열 2
2.
알고리즘 : 이분 탐색, LIS
3.
성공 여부 : 성공 (5분)
4.
풀이 : 가장 긴 증가하는 부분 수열(LIS)
5.
복기 : 배열의 범위가 100만이라서 O(n^2) 풀이는 불가능하고 dp + 이분탐색을 이용한 O(n log n)풀이를 이용해야 한다.
1.
문제 : 트리의 지름
2.
알고리즘 : 그래프 이론, 그래프 탐색, 트리, DFS
3.
성공 여부 : 성공 (30분)
4.
풀이 : 보류
5.
복기 : 임의의 정점 x에서 가장 먼 y 정점을 구한 뒤, y정점으로부터 가장 먼 정점 z를 구하면 y와 z 사이의 거리가 트리의 지름이 된다.
1.
문제 : 친구 네트워크
2.
알고리즘 : 자료 구조, 해시를 사용한 집합과 맵, 분리 집합
3.
성공 여부 : 성공 (20분)
4.
풀이 : 보류
5.
복기 : 친구 네트워크의 수를 구하는 문제. 유니온-파인드의 정석 문제다. 유니온-파인드 최적화를 까먹어서 시간 제한에 걸쳐서 풀었다. 다시 복습해야겠다.
1.
문제 : 가장 긴 증가하는 부분 수열 3
2.
알고리즘 : 이분 탐색, LIS
3.
성공 여부 : 성공 (5분)
4.
풀이 : 가장 긴 증가하는 부분 수열(LIS)
5.
복기 : dp + 이분 탐색을 이용한 O(n log n)풀이
1.
문제 : 저울
2.
알고리즘 : 그리디, 정렬
3.
성공 여부 : 실패
4.
5.
복기 : 현재까지 만들 수 있는 무게 sum에서 새로운 추의 무게가 sum + 1보다 크다면 sum + 1를 만들 수 없다는 아이디어를 떠올렸어야 한다.
1.
문제 : 빵집
2.
알고리즘 : 그래프 이론, 그리디 알고리즘, 그래프 탐색, 깊이 우선 탐색
3.
성공 여부 : 성공 (25분)
4.
풀이 : 보류
5.
복기 : 빵집에서 다른 집의 가스를 훔치기 위해 R x C 배열에 가스관을 최대로 설치할 수 있는 개수를 구하는 문제. 일반적인 DFS 문제지만, 가지치기를 잘해야 한다. 근처 빵집의 가스관에서 출발해서 오른쪽 위 대각선, 오른쪽, 오른쪽 아래 대각선으로 훑도록 해 최대한 위에서부터 채워넣도록 하며, 한 시퀀스에서 연결이 불가능했다면, 다음 시퀀스에서 그 경로를 지나더라도 어차피 연결이 불가능할 것이므로 방문 배열을 초기화시키지 않는다. 백트래킹이 아니라 그리디하게 접근해야 함
1.
문제 : 공항
2.
알고리즘 : 자료 구조, 그리디 알고리즘, 분리 집합
3.
성공 여부 : 성공 (20분)
4.
풀이 : 공항
5.
복기 : 1부터 G까지의 번호를 가진 게이트가 있을 때, P개의 비행기가 순서대로 도착함. 이 때, i번째 비행기를 1번부터 gi(1 ≤ gi ≤ G) 번째 게이트 중 하나에 영구적으로 도킹하려고 함. 순서대로 도착하다가 더 이상 도킹할 수 없을 때, 공항이 폐쇄됨. 최대 몇 대를 도킹시킬 수 있는지 묻는 문제. 처음 단순하게 생각했을 때, 최대한 많은 비행기를 도킹하기 위해서는 최대한 큰 번호의 게이트에 도킹해야 함. 그러므로 gi부터 이전 번호들을 체크해서 비행기가 도킹하지 않은 게이트를 찾아 넣어주는 것. 하지만, 범위가 10만이기 때문에 매번 선형적으로 이전 번호를 체크할 수 없으므로 이전 범위에서 도킹 가능한 위치를 빠르게 찾아야 함.
1.
문제 : 벽 부수고 이동하기 4
2.
알고리즘 : 그래프 이론, 그래프 탐색, BFS, DFS
3.
성공 여부 : 성공 (50분)
4.
풀이 : 패스
5.
복기 : 너비 우선 탐색을 통해 각 위치에서 이동할 수 있는 위치를 모두 탐색하는 문제. 이동할 수 있는 위치를 먼저 구해놓고 그룹핑해놓은 뒤 벽의 위치를 탐색하는 방법으로 구할 수 있다.
1.
문제 : 까다로운 아이들과 선물 상자
2.
알고리즘 : 자료 구조, 세그먼트 트리
3.
성공 여부 : 성공 (4시간) & 사실상 실패
4.
풀이 : 보류
5.
복기 : Order Statistic Tree에 대해서 알아야 한다. 그리고 남아있는 상자 개수보다 더 크게 배려하고자 하는 배려심이 좋은 아이가 예외로 존재한다.
1.
문제 : 자동완성
2.
알고리즘 : Trie
3.
성공 여부 : 성공 (30분)
4.
풀이 : 패스
5.
복기 : Trie 자료구조를 공부할 수 있는 좋은 문제
1.
문제 : 랜덤 넘버 추측하기
2.
알고리즘 : 자료 구조, 세그먼트 트리
3.
성공 여부 : 성공 (1시간)
4.
풀이 : 패스
5.
복기 : 세그먼트 트리로 각 회원의 가중치의 합을 구하고 부분합으로 답을 구하는 문제. 1-index임을 유의해서 작성하면 풀린다.
1.
문제 : AB
2.
알고리즘 : 자료 구조, 문자열, 트리, 해싱, Trie
3.
성공 여부 : 성공 (30분)
4.
풀이 : 패스
5.
복기 : 두 개의 Trie 자료구조를 만들고 이를 이용해서 쿼리하는 문제. 차근차근 구현하면 풀린다. 메모이제이션을 통해 최적화 가능
1.
문제 : 버블 소트
2.
알고리즘 : 정렬
3.
성공 여부 : 성공 (30분)
4.
풀이 : 패스
5.
복기 : 무작위 배열이 주어졌을 때, 버블 소트를 몇 시퀀스해야 더 이상 원소를 바꾸지 않아도 되는지 묻는 문제. 오른쪽에 존재하는 작은 수가 왼쪽으로 이동하면서 자기 자리를 찾아들어가는 거리가 시퀀스 횟수임!
1.
문제 : 반도체 설계
2.
알고리즘 : 이분 탐색, LIS
3.
성공 여부 : 성공 (5분)
4.
풀이 : 패스
5.
복기 : 반도체 2개를 연결할 때, 양쪽 포트를 연결하는 선이 꼬이지 않도록 할 수 있는 최대 선의 개수를 구하는 문제. LIS를 사용할 수 있는 유명한 응용문제
1.
문제 : 정수 제곱근
2.
알고리즘 : 수학, 이분 탐색
3.
성공 여부 : 성공 (5분)
4.
풀이 : 패스
5.
복기 : n이 최대 2⁶³의 범위일 때 그 수의 정수 제곱근을 구하는 문제. (long) Math.ceil(Math.pow(n, 0.5))하면 풀리긴 함. 이분 탐색으로 풀 때는 n의 범위가 long의 양수 범위이므로 계산 과정에서 오버 플로우가 발생할 여지가 있음. 그러므로 자바에서는 BigInteger를 활용하거나 앞에 1L을 곱해줘서 명시적으로 long타입 연산임을 컴파일러에게 알려줄 것.
1.
문제 : 로봇 조종하기
2.
알고리즘 : DP
3.
성공 여부 : 성공 (30분)
4.
풀이 : 패스
5.
복기 : 왼쪽, 오른쪽, 아래 세 방향으로 움직일 수 있을 때, 최댓값을 구하는 문제. 일반적인 BFS, DFS 문제처럼 보일 수 있지만 조금 다르다. visited배열을 쓰기엔 오른쪽으로 갔다가 내려와서 다시 왼쪽으로 오는 경로가 더 클 수 있어서 visited배열을 쓸 수 없음. 방향이 왼쪽, 오른쪽, 그리고 아래로 내려오는 것 밖에 없음을 고려해 맨 윗 행부터 차례대로 메모이제이션을 해야 풀 수 있음. 각 행에서 왼쪽에서 오른쪽으로 가면서 leftToRight[j] = Math.max(dp[i - 1][j], dp[i][j - 1])을 저장. 각 행에서 오른쪽에서 왼쪽으로 가면서 rightToLeft[j] = Math.max(dp[i - 1][j], dp[i][j + 1])을 저장. 그리고 최종적으로 저장한 배열끼리 비교해 최종적으로 dp배열을 완성 dp[i][j] = Math.max(leftToRight[j], rightToLeft[j])
1.
문제 : LCS
2.
알고리즘 : DP, 문자열
3.
성공 여부 : 성공 (10분)
4.
풀이 : 패스
5.
복기 : LCS 기본 문제. 2차원 dp배열을 사용하며 각각 패딩을 집어넣음. LCS[i][j]에서 A[i - 1] == B[j - 1]라면 LCS[i - 1][j - 1] + 1, 다르면 Math.max(LCS[i - 1][j], LCS[i][j - 1])
1.
문제 : LCS 2
2.
알고리즘 : DP, 문자열
3.
성공 여부 : 성공 (10분)
4.
풀이 : 패스
5.
복기 : LCS의 길이를 구하고 LCS도 함께 구하는 문제. LCS[N][M]에서부터 위, 왼쪽에 같은 값이 있으면 LCS를 구할 때 같은 값이 없었다는 뜻이므로 같은 값이 있는 곳으로 이동. 같은 값이 없으면 해당 글자를 추가하고, LCS[i - 1][j - 1]로 이동. LCS[i][j] = 0일 때까지 반복한 뒤, 배열을 뒤집으면 LCS 출력 가능
1.
문제 : LCS 3
2.
알고리즘 : DP, 문자열
3.
성공 여부 : 성공 (10분)
4.
풀이 : 패스
5.
복기 : 3개의 문자열의 LCS을 구하는 변형 문제. 2개 의 문자열의 LCS를 구할 때 2차원 배열을 사용한 것처럼 3차원 배열을 사용하고, 3중 반복문으로 구하면 됨
1.
문제 : 정복자
2.
알고리즘 : 그래프 이론, 최소 스패닝 트리
3.
성공 여부 : 성공 (30분)
4.
풀이 : 패스
5.
복기 : N개의 도시와 M개의 도로로 이루어진 도시를 최소 비용으로 전부 정복하는 MST문제. 1번 도시에서 시작하는 것이 정해진 상태이므로 크루스칼이 아닌 프림 알고리즘을 사용해서 풀어야 한다. 크루스칼 알고리즘은 1번 도시가 고정되지 않은 상태의 MST를 만들어내기 때문에 1번 도시의 out-degree가 1개 임을 보장할 수 없음. 혹여나 MST의 중간이면 out-degree가 2개일 수도 있음. 따라서 MST는 맞더라도 1번 도시에서 뻗어나가서 전체를 정복해야 하는 문제 특성 상 out-degree가 2개가 되면 안됨. 따라서 그냥 프림 알고리즘으로 푸는 게 맞다
1.
문제 : DSLR
2.
알고리즘 : 그래프 이론, 그래프 탐색, 너비 우선 탐색
3.
성공 여부 : 성공 (20분)
4.
풀이 : 패스
5.
복기 : D, S, L, R 네 개의 연산을 구현하는 문제. 각 경우의 수를 탐색하면서 최소한의 명령어 나열을 출력해야 하므로 BFS가 적당함
1.
문제 : 뱀과 사다리 게임
2.
알고리즘 : 그래프 이론, 그래프 탐색, 너비 우선 탐색
3.
성공 여부 : 성공 (30분)
4.
풀이 : 패스
5.
복기 : 주사위를 굴려 100에 도착할 수 있는 최소 횟수를 구하는 문제. 간단한 BFS 문제다
1.
문제 : Alive or Dead?
2.
알고리즘 : 구현, 시뮬레이션
3.
성공 여부 : 성공 (1시간)
4.
풀이 : 패스
5.
복기 : 플레이어, 하급 좀비, 상급 좀비를 차례대로 움직이고 나서 플레이어와 좀비의 위치가 겹치면 죽는 문제. 하나하나 구현은 까다롭지 않지만, 워낙 코드 길이가 길어 실수할 여지가 많다. 헬퍼 메서드를 차근차근 실수없게 작성하는 습관 들이기
1.
문제 : 인공지능 테트리스 (Large)
2.
알고리즘 : 구현, 그래프 이론, 브루트포스 알고리즘, 그래프 탐색, 시뮬레이션, DFS, BFS
3.
성공 여부 : 실패
4.
풀이 : 패스
5.
복기 : 설명이 아주 부실한 문제. 최악의 문제였다. 결국 테트리스지만 좌우 이동이 몇 번 되는지는 상관없이 자유롭게 이동 가능하다. 블록을 돌리고 나서, 음수 좌표가 없도록 정규화를 해야 하고, 아래로 내려갈 수 없다면 그 위치에서 줄 수 계산해야한다.
1.
문제 : 컵라면
2.
알고리즘 : 자료 구조, 그리디 알고리즘, 정렬, 우선순위 큐
3.
성공 여부 : 성공 (1시간)
4.
풀이 : 패스
5.
복기 : 조건이 max N = 200,000일 때, 문제를 풀어서 받을 수 있는 컵라면의 개수를 구하는 문제다. 첫번째 접근 방식은 N이 꽤 커서 날짜를 인덱스로 한 1차원 dp를 사용할 수 있을까를 고민했는데, 해당 일자의 dp에 컵라면의 구성 정보가 사라진다는 점 때문에 사용할 수 없었다. 즉, 컵라면이 현재 어떻게 구성되어 있는지 정보를 유지되어야 했다. 결국, 이 문제는 우선순위 큐의 크기를 중요한 정보로 사용할 수 있는 문제로, 데드라인으로 오름차순 정렬한 문제 배열을 하나씩 읽으면서 우선순위 큐에 넣는다. 만약, 문제를 우선순위 큐에 넣었을 때, 데드라인보다 우선순위 큐의 크기가 커지면 가장 작은 하나를 뽑아서 데드라인과 우선순위 큐의 크기를 유지시키는 것이 핵심. 데드라인으로 오름차순했으므로 데드라인이 같거나 크다는 보장이 되므로 풀 수 있다.
1.
문제 : 트리의 높이와 너비
2.
알고리즘 : 그래프 이론, 그래프 탐색, 트리, 깊이 우선 탐색
3.
성공 여부 : 성공 (30분)
4.
풀이 : 패스
5.
복기 : 이진트리에서 각 레벨의 노드 사이의 길이가 가장 긴 것을 찾는 문제. 처음 보면 당황스러울 수 있지만, 찬찬히 생각하면 중위 순회(Inorder Traverse)로 풀면 된다. 가장 왼쪽 노드부터 x = 1이라고 하고 차례대로 숫자를 올리면서 오른쪽 까지 진행한다. 이 때, 각 노드의 depth도 함께 기록했다가 해당 depth에서 min, max 값을 기록하고 최종적으로 depth 별 min, max 값을 계산해서 풀면 된다. 예시에는 노드가 순서대로 들어오지만, 테스트 케이스에서는 뒤죽박죽으로 들어오니 이를 유의할 것
1.
문제 : 동전 2
2.
알고리즘 : DP
3.
성공 여부 : 성공 (20분)
4.
풀이 : 패스
5.
복기 : 유명한 DP 유형인 동전 문제. n가지 종류의 동전을 여러번 사용해서 가치의 합이 k가 되었을 때, 동전 개수의 최솟값을 구하는 문제. 최솟값을 구해야 하므로, 초기 dp 배열을 Infinity로 초기화하고 dp[0] = 0으로 둔다. dp[i] = Math.min(dp[i], dp[i - coin] + 1) 가치 i를 구성하는 최소한의 동전 개수를 구해가면 된다.
1.
문제 : 합분해
2.
알고리즘 : 수학, DP
3.
성공 여부 : 성공 (1시간)
4.
풀이 : 패스
5.
복기 : 200! 의 연산을 할 수 없으므로 dp 문제가 확실한데, 점화식을 구하기 까다로웠다. 결국, 이차원 배열로 풀 수 있었다.
1.
문제 : 보물섬
2.
알고리즘 : 그래프 이론, 브루트포스 알고리즘, 그래프 탐색, BFS
3.
성공 여부 : 성공 (10분)
4.
풀이 : 패스
5.
복기 : 간단한 BFS 문제. N, M ≤ 50이라 쉽게 풀 수 있었다. 만약 범위가 더 넓었다면 이대로는 못 풀었을 듯 하다.
Loading comments...
0
0
