1.
문제 : 연구소
2.
알고리즘 : 구현, 그래프 이론, 브루트포스 알고리즘, 그래프 탐색, BFS
3.
성공 여부 : 성공(20분)
4.
풀이 : 보류
5.
복기 : 이차원 배열에 벽이 세워져있고, 바이러스가 위치해 있고 세 개의 벽을 추가로 세웠을 때 바이러스로부터 안전한 지역의 크기가 가장 큰 것을 찾는 문제. 세 개의 벽을 무조건 세워야 하므로 dfs로 모든 벽을 세울 수 있는 경우의 수로 place한 다음에 바이러스를 bfs로 퍼뜨려서 정답을 찾았다. dfs 대신 아예 입력받을 때 벽을 세울 수 있는 위치만 저장해 뒀다가 조합으로 푸는 게 더 빠를 것 같긴 하다
1.
문제 : 불켜기
2.
알고리즘 : 그래프 이론, 그래프 탐색, BFS
3.
성공 여부 : 성공 (30분)
4.
풀이 : 보류
5.
복기 : 방에 불을 켤 수 있는 최대 개수를 구하는 문제. 방에 불이 켜진 것, 그리고 방문 여부를 잘 고려해서 문제를 풀어야 한다. 간단한 BFS 문제인 줄 알고 대충 풀었다가 한번 틀렸다. 어떤 방에 불을 새로 켰다면 다시 주변에 이미 방문한 노드를 찾아서 큐에 넣어주어야 한다. 그리고 아직 방문하지 않은 노드도 큐에 넣어주어야 한다. 따라서 큐에 넣을 위치를 찾는 반복문이 두 번 필요하다.
1.
문제 : 테트로미노
2.
알고리즘 : 구현, 브루트포스
3.
성공 여부: 성공 (50분)
4.
풀이 : 보류
5.
복기 : 테트리스 블록을 회전하고 대칭시켜서 최대값을 찾는 노가다 구현 문제. 회전하고 대칭한 뒤에 normalize할 때, x, y 최소값을 회전 전의 값으로 넣어서 계속 틀렸다. 코드 작성할 때 집중하기
1.
문제 : 아기 상어
2.
알고리즘 : 구현, 그래프 이론, 그래프 탐색, 시뮬레이션, 너비 우선 탐색
3.
성공 여부 : 성공 (30분)
4.
풀이: 패스
5.
복기 : BFS를 사용한 구현 문제. 조건에 따라 차근차근 풀면 풀리지만 조건에 맞는 물고기를 리스트로 저장했다가 최종적으로 가장 맞는 물고기를 선택해서 먹어야 한다. BFS 특성 상 가장 거리가 가까운 물고기를 먼저 찾긴 하지만 다른 반례가 나올 수도 있음
1.
문제 : 청소년 상어
2.
알고리즘 : 구현, 시뮬레이션, 백트래킹
3.
성공 여부 : 성공 (1시간)
4.
풀이 : 패스
5.
복기 : 코드를 잔뜩 짜야 하는 구현 문제. 맵 크기가 4 x 4로 고정되어 있고 작아서 조건을 하나하나 빠뜨리지 않고 차근차근 풀면 된다. TreeMap과 3차원 int를 사용해서 풀었다. 모든 경우의 수를 시뮬레이션해야 하기 때문에 깊은 복사하는 것을 빠뜨리지 말 것
1.
문제 : 구슬 탈출 2
2.
알고리즘 : 구현, 그래프 이론, 그래프 탐색, 시뮬레이션, 너비 우선 탐색
3.
성공 어부 : 성공 (1시간)
4.
풀이 : 패스
5.
복기 : 빡구현 문제. 빨간 공과 파란 공이 각각 하나만 있음을 고려해 해당 공들의 좌표로 4차원 visited배열 관리
1.
문제 : 현대모비스와 함께하는 편안한 주행
2.
알고리즘 : 그래프 이론, 기하학, 최단 경로, 데이크스트라
3.
성공 여부 : 성공 (1시간)
4.
풀이 : 풀이
5.
복기 : 다익스트라를 기하학적으로 접근하는 문제. 간만에 되게 재미있는 문제였다.
1.
문제 : 멍멍이 쓰다듬기
2.
알고리즘 : 수학
3.
성공 여부 : 성공 (30분)
4.
풀이 : 패스
5.
복기 : 원숭이가 멍멍이의 키를 따라잡기 위해 필요한 최소 일수를 구하는 문제. 하루에 늘릴 수 있는 키의 양을 1cm밖에 조절할 수 없으므로 우주 비행이랑 비슷한 문제. 등차수열의 합을 응용하면 됨.
1.
문제 : ZOAC
2.
알고리즘 : 구현, 문자열, 재귀
3.
성공 여부 : 성공 (30분)
4.
풀이 : 패스
5.
복기 : 규칙은 어렵지 않게 찾아낼 수 있었는데, 이걸 어떻게 구현할 수 있을까 고민했던 문제. 재귀적으로 푸는데 문자열의 범위를 나눠서 풀면 된다. 찾아낸 다음 문자를 기준으로 뒤, 앞 순서로 재귀적으로 호출해야 한다.
1.
문제 : 무빙워크
2.
알고리즘 : 그래프이론, 최단경로, 데이크스트라
3.
성공 여부 : 성공 (1시간)
4.
풀이 : 패스
5.
복기 : 무빙워크를 작동시키거나 작동시키지 않으면서 각 도시로 가는 최단 경로의 합을 구하는 문제. 최종 경로에 대해서 무빙워크의 작동 상태까지 출력해야 하는 문제다 보니 조금 난해했다. 각 간선이 작동 여부 속성을 가지고 있도록 한 뒤, 노드로 인바운드되는 부모 간선을 기록하고 최종적으로 각 간선의 작동 여부를 파악하면 된다.
1.
문제 : 두 용액
2.
알고리즘 : 정렬, 이분 탐색, 두 포인터
3.
성공 여부 : 성공 (10분)
4.
풀이 : 패스
5.
복기 : 투 포인터를 사용하는 대표적인 문제. 범위도 N ≤ 100,000라서 O(N)의 시간 복잡도이므로 투 포인터로 풀면 된다.
1.
문제 : 멀티탭 스케줄링
2.
알고리즘 : 그리디
3.
성공 여부 : 성공 (30분)
4.
풀이 : 패스
5.
복기 : 운영체제 페이지 교체 알고리즘 중 OPT 알고리즘을 구현하는 문제. 전기용품의 사용 순서가 정해져 있으므로 가장 나중에 사용될 전기용품의 플러그를 찾아서 빼는 방식으로 구현하면 된다.
1.
문제 : 다리 만들기 2
2.
알고리즘 : 구현, 그래프 이론, 브루트포스 알고리즘, 그래프 탐색, BFS, DFS, MST
3.
성공 여부 : 성공 (1시간 30분)
4.
풀이 : 패스
5.
복기 : 각 섬을 연결하는 다리를 만드는 최소한으로 만드는 구현 문제. Flood Fill 알고리즘을 통해 각 섬을 찾고 각 섬에서 연결될 수 있는 다리를 찾아서 MST로 풀면 된다.
1.
문제 : 수열과 쿼리 17
2.
알고리즘 : 자료 구조, 세그먼트 트리
3.
성공 여부 : 성공 (1시간)
4.
풀이 : 패스
5.
복기 : 세그먼트 트리의 update, query 쿼리를 구현하는 문제. query의 left, right 범위를 어떻게 잡아야 하는지 까먹어서 기억에 의존해 다시 구현하느라 시간이 오래 걸림. 양쪽 범위를 다 포함하도록 구현하는 게 편하다는 것을 기억하기
1.
문제 : 알 수 없는 문장
2.
알고리즘 : DP
3.
성공 여부 : 성공 (30분)
4.
풀이 : 패스
5.
복기 : 초기 그냥 DFS로 풀었더니 메모리 초과가 떴다. 그래서 곰곰히 생각하던 도중 메모이제이션 할 수 있는 방법이 떠올라 풀 수 있었다.
1.
문제 : 우수 마을
2.
알고리즘 : DP, 트리, 트리에서의 DP
3.
성공 여부 : 성공 (30분)
4.
풀이 : 패스
5.
복기 : 트리 구조의 마을에서 우수 마을의 인구수를 최대한으로 하는 방법을 찾는 문제. 우수 마을이 인접하지 않도록 하면서, 우수 마을이 아닌 마을은 우수 마을에 인접하도록 해야 하므로 퐁당퐁당 느낌으로 해야 최대한의 인구수를 찾을 수 있음. 또 2차원 배열을 이용해 메모이제이션하면 됨
1.
문제 : 게임
2.
알고리즘 : DP, 그래프 이론, 그래프 탐색, DFS
3.
성공 여부 : 성공 (30분)
4.
풀이 : 패스
5.
복기 : DP + 사이클 감지 문제. 처음에는 BFS + 이전 좌표와 다음 좌표가 같으면 사이클로 판단하는 전략을 생각했는데, 반례가 생김. 따라서 visited 배열을 사용해 사이클을 감지하는 것으로 전략을 변경했더니 풀렸다.
1.
문제 : 퍼즐
2.
알고리즘 : 자료구조, 그래프 이론, 그래프 탐색, BFS, 해시를 사용한 집합과 맵
3.
성공 여부 : 성공 (30분)
4.
풀이 : 패스
5.
복기 : BFS와 집합(set)을 사용한 캐싱으로 풀 수 있는 가벼운 문제. 하지만 몇 번 틀린 이유는 초기에 퍼즐이 제대로 정렬되어 있을 때도 일단 큐에 넣어서 결과가 2로 나왔다. 항상 문제를 풀 때, 반례를 잘 생각해봐야겠다.
29
0
