R+7

문제n x n 격자 벽면에 기둥과 보를 설치하거나 삭제하면서, 매 작업 후 남아 있는 모든 구조물이 조건을 만족해야 하는 문제. 기둥은 바닥 위에 있거나, 아래에 기둥이 있거나, 보의 한쪽 끝 위에 있어야 한다. 보는 한쪽 끝이 기둥 위에 있거나, 양쪽 끝이 다른 보와 연결되어 있어야 한다. 명령은 [x, y, a, b] 형태로 주어지고, a는 기둥/보, b는 설치/삭제를 의미한다. 최종적으로 남은 구조물을 x 오름차순, y 오름차순, 기둥 먼저 정렬해서 반환해야 한다. 조건 자체가 복잡해서, 설치와 삭제 각각의 경우를 미리 전부 따지려 하면 코드가 쉽게 꼬이는 구현 문제다.회고처음에는 명령을 그대로 따라가면서 모든 경우의 수를 직접 나누려고 했는데 (먼저 b가 1이면 설치, 0이면 삭제로 나누고, 그..

문제링크 (문제 설명이 말로 하기가 까다로워서, 직접 문제에 들어가 GIF를 보는 것이 이해가 더 빠르다) n x n 크기의 2차원 배열을 특정 규칙에 따라 채운 뒤, 이를 1차원 배열로 펼쳤을 때 left부터 right까지의 구간만 반환하는 문제. n은 최대 10^7까지 주어지고, right - left는 10^5 미만으로 제한된다. 처음 보면 2차원 배열을 직접 만들어야 할 것 같지만, n^2 크기의 배열을 만드는 순간 시간과 메모리 양쪽에서 바로 터지는 문제로, 결국 전체 배열을 만드는 것이 아니라 특정 인덱스가 원래 2차원 배열의 몇 행 몇 열인지 계산해서 값을 바로 구해야 하는 문제다. 회고솔직히 처음에는 '설마 바로 값을 찍어야 하는 문제는 아니겠지'라고 생각했는데, 그게 정답이었다. 제한 조..

문제N x N 격자의 시계들(0:12시, 1:3시, 2:6시, 3:9시)이 상하좌우 연동되어 돌 때, 모든 시계를 12시(0)로 맞추기 위한 최소 조작 횟수를 구하는 문제. 시계 하나를 돌리면 본인 및 상하좌우 시계가 함께 90도(1칸)씩 돌아가고, 0(12시), 1(3시), 2(6시), 3(9시) 이며, 4번에 1바퀴 회전. 제한 조건은 N이 2 이상 8 이하.회고풀다가 막혔다. 처음에는 주변 시계가 0이 아닌 곳을 찾아 돌리는 탐욕적(Greedy) 방식을 사용했지만, 너무 많은 경우의 수가 존재하는데다 애초에 돌려서 상하좌우가 0이 아닌 상태가 되더라도 전체를 맞추기 위해 돌려야 하는 경우가 존재했다. 이러한 문제를 푸는데는 정석적인 방법으로 라이츠 아웃(Lights Out) 퍼즐의 해결 방법을 도입..

문제출발 지점부터 도착 지점까지 놓인 바위 중 n개를 제거해 각 지점 사이 거리 최솟값 중 가장 큰 값을 구하는 문제. 도착 지점까지의 거리 (distance)는 1부터 10억. 바위 개수는 5만 개로 조건이 주어진다. 각 바위가 [2, 14, 11, 21, 17] 로 주어지고 n이 2라고 가정하면, [2, 14]를 제거했을 때 각 바위 사이 거리는 [11, 6, 4, 4]가 되고, 거리의 최솟값은 4가 된다. 다른 값과 비교했을 때 이 값이 제일 크므로 답은 4. 회고이게 왜 이분 탐색인가..? 생각이 가장 먼저 들었고, 어떻게 접근해야 문제를 풀 수 있을지 한참 고민. 도착 지점까지의 거리가 10억이라는 부분에서 힌트를 얻었어야 하는 문제였다. 애초에 바위 개수가 5만 개인 상황에서 n개를 전부 빼보..

앞으로 알고리즘 관련 문제 풀이 모음 + 개념 포스팅을 한눈에 찾기 위한 메인 인덱스 페이지. 새 글 작성할 때마다 이 곳에 링크와 간단 팁을 업데이트할 예정이다.1. 개념 정리그래프 문제 해결 방안2. 문제 풀이No.문제명주요 알고리즘바로가기001징검다리이분 탐색보러가기002고고학 최고의 발견완전 탐색보러가기

분기 설정알고리즘 문제 중 그래프가 나왔을 때, 우리가 생각해 볼 접근법을 설정한다면 다음과 같다.1. 이동: 최단 거리나 최소 비용을 구하는가?간선 비용이 모두 같음(또는 비용 없음): BFS간선 비용이 다름모두 양수: 다익스트라음수 포함됨: 벨만-포드한 지점이 아니라 '모든 지점 간'의 거리: 플로이드-워셜2. 연결: 모든 노드를 하나로 묶거나 그룹화하는가?최소 비용으로 전체를 하나로 연결: MST (크루스칼, 프림) 필수 조건: 무방향 그래프이어야 하며, 사이클이 없어야 함같은 그룹/네트워크인지 확인하거나 두 그룹을 합침: 유니온-파인드 (얘는 여기 뿐 아니라 여러 군데 사용됨)3. 작업의 선후 관계가 있거나 사이클을 찾아야 하는가?순서 정하기, 선수 과목, 선행 조건: 위상 정렬 필수 조건: 방향..