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

책 "알고리즘 문제 해결 전략"에 나오는 algospot 문제 "FENCE"에 대한 풀이입니다. 목차 문제 해결 전략 - 무작정 풀기 코드 전문 - 무작정 풀기 문제 해결 전략 - 분할 정복 코드 전문 - 분할 정복 FENCE 문제 URL은 다음과 같습니다. FENCE 문제 문제 해결 전략 - 무작정 풀기 먼저, 이 문제를 풀기 위해서 "무작정 풀기" 전략을 선택해 봅시다. 제일 쉬운 방법은 모든 인덱스를 돌면서, 그 높이를 가진 울타리 영역의 최대치를 구하면 됩니다. 무슨 소리냐면, 첫 번째 입력을 예로 살펴봅시다. 이런 울타리에서 첫 번째 판자의 높이로 울타리를 잘라낸다고 하면, 오른쪽 판자의 높이가 자신보다 낮습니다.따라서 다음 영역의 울타리를 잘라낼 수 있습니다. 영역의 너비는 7(7 * 1)이 ..

책 "알고리즘 문제 해결 전략"에 나오는 algospot 문제 "QUADTREE"에 대한 풀이입니다. 목차 문제 해결 전략 코드 전문 QUADTREE 문제 URL은 다음과 같습니다. QUADTREE 문제 문제 해결 전략 제가 이 문제를 해결하기 위해서 체택한 방법은 "분할 정복"입니다. 보통 알고리즘 문제를 해결할 때는 "무식하게 풀기"를 적용한 이후, 문제를 최적화하기 위한 패러다임을 차차 적용하는 것이 좋습니다. 하지만, 위 문제에서는 "분할 정복"을 적용하라는 문구가 이미 적혀져 있습니다. "주어진 공간을 항상 4개로 분할해 재귀적으로 표현하기 때문에 쿼드 트리라는 이름이 붙었는데, (이하 생략)" 4개로 분할해서 재귀적으로 표현한다. 이것은 4군데로 각기 나누어 문제를 해결하라는 소리와 일치합니다..

책 "알고리즘 문제 해결 전략"에 나오는 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), (..

CH 04 스택(Stack)목표자료구조 스택에 대해 알아보고, C/C++ 프로그래밍 언어로 구현해봄으로써 스택의 이해의 깊이를 늘려보세요 목차1. 스택이란 무엇인가? 2. 스택 ADT 3. C로 구현하기 4. C++로 바꿔보기 5. 결론 1. 스택이란 무엇인가? 스택이란 마치, 프링글스 통과 같습니다. 그림처럼, 프링글스는 맨 위의 과자를 꺼내지 않는한, 그 밑의 과자는 먹을 수가 없지요. 즉, 가장 나중에 들어온 과자가 가장 먼저 나가게 됩니다. 이를 LIFO (Last In First Out) 구조라고 합니다. 바꿔서 스택이란 자료구조라도 말합니다. 자 지금부터 본격적으로 스택에 대해 알아봅시다. 2. 스택 ADT 스택의 ADT는 다음과 같습니다. ADT Stackcharacters:arr: T[]데..

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