구르미의 개발 이야기 구르미의 개발 이야기

책 "알고리즘 문제 해결 전략"에 나오는 algospot 문제 "CLOCKSYNC"에 대한 풀이입니다. 목차 문제 해결 전략 코드 전문 CLOCKSYNC 문제 URL은 다음과 같습니다. CLOCKSYNC URL 문제 해결 전략 제가 이 문제를 해결하기 위해서 체택한 방법은 "무식하게 풀기"입니다. 여기서 문제의 핵심은 시계는 3, 6, 9, 12 만을 가리킨다는 것입니다. 무슨 말이냐면, 첫 번째 테스트케이스를 살펴봅시다. 0~15번까지 시계의 상태는 다음과 같을 것입니다. 모든 시계를 12시를 가리키기 위해서 최소한의 스위치를 누르는 방법은 다음과 같이 1, 2, 3, 4, 5번 시계와 연결된 8번 스위치를 2번 누르는 것입니다. 순서로 쪼개보면 다음과 같이 서술할 수 있겠지요. 8번 스위치를 1번 누..

책 "알고리즘 문제 해결 전략"에 나오는 algospot 문제 "BOGGLE"에 대한 풀이입니다. 목차 문제 해결 전략 - 무작정 풀기 코드 전문 - 무작정 풀기 문제 해결 전략 - 동적 계획법 코드 전문 - 동적 계획법 BOGGLE 문제 URL은 다음과 같습니다. BOGGLE URL 문제 해결 전략 - 무작정 풀기 먼저 제가 접근한 문제 해결 전략은 "무작정 풀기"입니다. 문제의 입력 분석과 해결 조각 찾기 우리가 문제를 해결하기 위해선는, 5x5의 보드판 board, 길이 10 이하의 문자열 s라는 입력이 필요하다는 것을 알아야 합니다. 실제 테스트 케이스 1개당 문자열 N개를 받습니다만, 결국 이 문제의 핵심은 "보드판에서 인접한 위치만 이동함으로써 문자열을 만들 수 있느냐"입니다. main 함수의..

책 "알고리즘 문제 해결 전략"에 나오는 algospot 문제 "BOARDCOVER"에 대한 풀이입니다. 목차 문제 해결 전략 코드 전문 문제 해결 전략 BOARDCOVER 문제 URL은 다음과 같습니다. BOARDCOVER URL 제가 이 문제를 해결하기 위해서 체택한 방법은 "무식하게 풀기"입니다. 결론부터 말씀드리면 이 문제는 다음과 같이 풀 수 있습니다. 보드를 좌표 (0, 0) 부터 시작해서 보드 끝 좌표 (W-1, H-1)까지 다음을 반복합니다. 블럭을 넣을 수 있는 좌표 (x, y)를 찾습니다. (x, y)에 L자 블럭을 넣을 수 있으면 넣습니다. 계속 채워나가다, 좌표 끝에 도달했을 때, 보드판을 모두 채웠으면, 그 개수를 셉니다. 사실 이렇게 해결책을 제시해도 말이 쉽지 우리가 바로 알고..

책 "알고리즘 문제 해결 전략"에 나오는 algospot 문제 "PICNIC"에 대한 풀이입니다. 목차 문제 해결 전략 코드 전문 문제 해결 전략 PICNIC 문제 URL은 다음과 같습니다. 급하신 분들은 바로, 코드 전문으로 넘어가주세요! PICNIC URL 제가 이 문제를 해결하기 위해서 체택한 방법은 "무식하게 풀기"입니다. 먼저 이해를 위해서 3번째 입력에 대해서, 살펴보도록 하겠습니다. n = 6, m = 10 set = (0, 1), (0, 2), (1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4), (3, 5), (4, 5) 이것을 그림으로 나타내 봅시다. 먼저 (0, 1) 세트를 골랐을 때, 다음으로 고를 수 있는 친구의 셋은 (2, 3), (2, 4), (..

[알고스팟] 외계 신호 분석(ITES)목표 : 책 "알고리즘 문제 해결 전략 문제 풀이" 중 문제 외계 신호 분석(ITES)를 풀어보자문제 URL풀이외계 신호 분석(ITES) 문제는 큐와 온라인 알고리즘을 이용하여 푸는 문제입니다. 온라인 알고리즘이란 무엇이냐. 오프라인 알고리즘의 경우 입력의 값이 모두 나왔을 때, 알고리즘을 일괄적으로 적용하여 문제를 푸는 것을 말하고, 온라인 알고리즘은 입력이 생성될 때마다, 알고리즘을 적용하여 문제를 푸는 방식을 말합니다. 일반적으로 예를 들어서 어떤 배열의 누적합을 구하는 경우, 이미 만들어져 있는 배열을 토대로 다음과 같이 누적합 만들 수 있습니다. arr = [1, 2, 3] acc = 1 + 2 + 3 = 6 그런데, 이렇게 생각할 수도 있습니다. 배열의 원..

[알고스팟] 조세푸스 문제(JOSEPHUS)목표 : 책 "알고리즘 문제 해결 전략 문제 풀이" 중 문제 조세푸스 문제(JOSEPHUS)를 풀어보자문제 URL풀이조세푸스 문제는 대표적인 큐 시뮬레이션 문제입니다. 먼저 첫 번째 예제를 살펴보도록 할까요? N = 6, K = 3 병사들은 1~6번까지, 원 형태로 앉아 있습니다. 이제 1번부터 2명이 남을 때까지 차례대로 죽여 나갈 건데, 아래 표에서 죽인다면, X를 표시해보도록 하지요. 또한, O는 죽어야 하는 놈을 가리키는 인덱스라고 하겠습니다. 1명 쨰, | 1 | 2 | 3 | 4 | 5 | 6 | | X | | | | | | | O | | | | | | 1번은 안타깝게도 묻지도 따지지도 않고 죽여야 합니다. 2명 째, | 1 | 2 | 3 | 4 | ..

[알고스팟] 짝이 맞지 않은 괄호(BRACKETS2)목표 : 책 "알고리즘 문제 해결 전략 문제 풀이" 중 문제 "짝이 맞지 않는 괄호"를 풀어보자문제 URL풀이"짝이 맞지 않은 괄호" 같은 문제는 스택을 이용하는 대표적인 알고리즘 문제입니다. 이 문제의 경우 다음의 조건을 검사해야 합니다. 모든 괄호는 쌍이 맞아야 한다.모든 괄호는 먼저 열리고 그 후에 닫혀야 한다.어떠한 쌍도 교차될 수 없다. (ex : "({)}" ) 이 문제 역시 스위핑 알고리즘을 기반으로 짭니다. 문제의 핵심은 닫히는 괄호가 나올때 짝이 맞는 열리는 괄호가 있는가입니다. 알고리즘의 가장 큰 줄기는 다음과 같습니다. 입력 문자열을 다음과 같이 순회합니다.현재 문자가 괄호를 여는 문자들 "(", "{", "[" 중 하나라면, 스택에..

[알고스팟] 울타리 쳐내기(FENCE)목표 : 책 "알고리즘 문제 해결 전략 문제 풀이" 중 문제 "울타리 쳐내기"를 풀어보자문제 URL풀이이 문제를 푸는 열쇠는 스택과 스위핑 알고리즘입니다. 스위핑 알고리즘이란 간단히 말해서 이미 연산이 진행된 이전 공간에 대해서는 연산을 하지 않는다라고 생각하시면 됩니다. 개념 자체는 쉽습니다만... 굉장히 생각하기 어렵다는게 함정입니다. 이 문제를 예를 들어 설명하겠습니다. 이 문제에서 우리가 사각형을 구하기 위해 필요한 정보는 그 사각형의 왼쪽 끝과 오른쪽 끝 그리고 높이입니다. 높이가 오른쪽 끝점의 높이라고 했을 때, 왼쪽으로 연속된 판자들 중 이 높이를 포함하는 가장 낮은 지점이 왼쪽 끝 점이 되겠죠. 이 성질을 이용해서, 문제를 푸는 것이죠. 그래서 어떻게 ..