Ikjo's Technology blog

문제 설명 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net 접근 방법 해당 문제는 너비 우선 탐색을 이용하여 해결할 수 있었습니다. 2차원 그래프상 특정 지점들간 최단 거리는 보통 너비 우선 탐색을 적용하는데, 깊이 우선 탐색의 경우 말그대로 깊이 탐색하기 때문에 해당 경로가 '최단' 경로인지 구분하기가 어려움 점이 있습니다. 일단 벽을 부수는 것을 제외하면 일반적인 너비 우선 탐색 문제입니다. 벽을 하나 부숴야 함으로써 난이도가 꽤나 상승했습니다. 벽을 하나 부숴야 하기 때문에 특정..

문제 설명 2110번: 공유기 설치 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 www.acmicpc.net 접근 방법 해당 문제는 이분 탐색을 이용하여 해결할 수 있었습니다. 여기서 이분 탐색을 찾고자 하는 것은 가장 인접한 두 공유기 사이의 최대 거리입니다. 이때 이분 탐색을 위한 시작점(start)을 1로 두었는데, 이는 인접한 두 공유기 간의 거리가 최소일 경우이기 때문입니다. 또한 끝점(end)을 첫번째 집과 마지막 집 사이의 거리(좌표 차)로 두었는데, 이는 인접한 두 공유기 간의 거리가 최대일 ..

문제 설명 20159번: 동작 그만. 밑장 빼기냐? 카드의 개수 N (2 ≤ N ≤ 100,000)이 주어진다. 단, N은 짝수이다. 둘째 줄에 카드의 윗장부터 밑장까지 카드의 값 X (1 ≤ X ≤ 10,000)이 정수로 주어진다. www.acmicpc.net 접근 방법 우선 문제에서 주어진 예시를 기준으로, 정훈이가 얻을 수 있는 카드 값의 합의 경우의 수는 다음과 같습니다. 이때, 각 경우의 수를 '밑장을 빼서 자신한테 분배한 경우'와 '밑장을 빼서 상대한테 분배한 경우'로 나누어 생각해볼 수 있겠습니다. 우선 밑장을 빼서 자신한테 분배한 경우를 살펴보겠습니다. 이 경우 당연히 정훈이의 카드 패에는 밑장(카드 패 맨 마지막 순서)이 항상 포함됩니다. 그리고 1번째 및 3번째 카드와 2번째 4번째 카..

프로그램에서 발생할 수 있는 3가지 에러 예외 처리를 다루기 앞서 우선 프로그램에서 발생할 수 있는 3가지의 에러에 대해 알아보자. 첫 번째는 컴파일 에러이다. 이는 컴파일러가 소스코드를 컴파일할 경우 오타, 자료형 체크 등의 기본적인 검사를 수행함으로써 프로그램이 실행되기 전에 에러가 발생한다. 두 번째는 런타임 에러이다. 이는 프로그램이 실행 중에 발생하는 에러로 이로 인해 잘못된 결과를 얻거나 프로그램이 비정상적으로 종료될 수 있다. 마지막으로 논리적 에러이다. 이는 컴파일 에러나 런타임 에러는 없지만, 개발자가 원래 의도한 것과 다르게 동작하는 것을 말한다. 예외(Exception)란? 앞서 프로그램에서 발생할 수 있는 3가지 에러에 대해 간단히 살펴보았는데, 자바에서는 런타임 에러를 '에러(Er..

병합 정렬이란? 병합 정렬은 퀵 정렬과 마찬가지로 분할 정복 알고리즘으로서 주어진 데이터를 두 개의 균등한 크기로 분할하고 분할된 영역을 정렬한 후 병합해 나가는 방식으로 정렬한다. 이때 분할하고 병합하는 과정에서 기존 데이터 전체 크기와 동일한 추가적인 자료구조를 사용하므로 O(n)의 공간 복잡도를 가진다. 그림으로 병합 정렬 이해하기 아래와 같이 최초 정렬되지 않은 크기 10의 정수형 배열이 있다고 가정했을 때, 병합 정렬을 통해 오름차순으로 정렬해보자. 우선, 주어진 배열의 영역을 절반씩 분할해나가는데, 영역의 크기가 2개 이하가 될 때까지 분할해나간다. 이때 분할해나가는 과정은 마치 깊이 우선 탐색과도 같다. 분할을 해나가는 중 영역의 크기가 2개 이하가 됐을 경우 즉, 더 이상 분할할 게 없는 ..