문제https://www.acmicpc.net/problem/11729 어떻게 풀 것인가?컴퓨터 공학부 전공자라면 자료구조 혹은 알고리즘 수업 시간에 재귀를 공부하면서 항상 자주보는 문제였을 것 이다. 나는 사실 과거에 기억에 의존하여 문제를 풀었기때문에 굉장히 쉬웠지만 그래도 한번 차근차근 문제를 뜯어보자. 우선 하노이의 탑문제를 살펴보자.일단, 하노이탑의 가장 큰 규칙은 "작은 원판 위에 큰 원판은 올 수 없다" 이다. 세 개의 기둥(A, B, C)과 여러 개의 크기가 다른 원판이 있다.처음에는 원판들이 가장 큰 것부터 가장 작은 것까지 차례대로 한 기둥(A)에 쌓여 있다.이 원판들을 다른 기둥(C)으로 모두 옮겨야 한다.단, 다음과 같은 규칙을 반드시 지켜야 한다.한 번에 하나의 원판만 이동할 수 ..
문제https://www.acmicpc.net/problem/2133 어떻게 풀 것인가?처음 문제를 풀었을 때 우선적으로는 DP가 떠올랐다.DP 정리는 아래에 있다.https://superohinsung.tistory.com/198 [Algorithm] 동적 계획법(Dynamic Programming)동적 계획법(Dynamic Programming) 동적 계획법(Dynamic Programming, DP)란 컴퓨터 프로그래밍 기법 중 하나로, 주로 최적화 문제나 중복되는 부분 문제를 효율적으로 해결하는 데 사용되는 알고리즘 설계superohinsung.tistory.com 세로 3칸의 크기는 고정되었다. 즉, 주어지는 N에 따라서 타일을 채울 수 있는 경우의 수가 달라진다.그래서 간단하게도 이 문제는 N..
문제https://www.acmicpc.net/problem/11758 어떻게 풀 것인가?문제 분석 : 큰 알고리즘 사용성에 대해서 보이지 않았다.-> 그래서 우선 내가 알고 있는 수학과 구현이라는 관점에서 접근하였다. 방향을 알기위해서는 각도가 필요하다고 생각했다. (이 부분은 다른분의 해설을 참고하였다.) 이 과정에서 기하학 입문에서 다루어지는 신발끈 공식에 대해서 알게 되었다. 세 점이 주어졌을 때, 신발끈 공식을 사용하여 결과값이 0보다 크면 반시계 방향, 0이면 일직선, 0보다 작으면 시계 방향으로 구할 수 있다고 한다. 좀 더 자세하게 알아보자 .신발끈 공식(또는 "shoelace theorem")은 주어진 점들이 이루는 다각형의 넓이를 구하는 방법으로 알려져 있지만, 이를 사용해서 세 점의 ..
문제https://www.acmicpc.net/problem/15486 어떻게 풀 것인가?주어진 날짜와 수익 배열을 통해서 최대 수익을 낼 수 있는 경우를 찾으면 되는 문제였다. 해당 문제는 Bottom-up 방식으로 1일부터 차례대로 최댓값을 갱신해주도록하면서 풀었다. 1일차 (N==1)dp[1] = 0, // 1일에 얻을 수 있는 최대 금액 (max) // 다음날 nxt = 1 + T1 = 4 dp[4] = Math.max( dp[4], dp[1] + P1) = 10 // 1일을 마치고 4일에 얻은 최대 금액 10 저장 2일차 (N==2)dp[2] = 0, // 2일에 얻을 수 있는 최대 금액 (max) // 다음날 nxt = 2 + T2 = 7 dp[7] = Math.max( dp[7], dp..
문제 https://www.acmicpc.net/problem/17837 17837번: 새로운 게임 2 재현이는 주변을 살펴보던 중 체스판과 말을 이용해서 새로운 게임을 만들기로 했다. 새로운 게임은 크기가 N×N인 체스판에서 진행되고, 사용하는 말의 개수는 K개이다. 말은 원판모양이고, 하 www.acmicpc.net 어떻게 풀 것인가? 이번 문제도 빡 구현이었다. 사실 문제를 처음에 읽었을 때는 그다지 어렵지않다고 생각을 하였으나, 이번에도 생각보다 조건이 까다롭다고 느꼈다. 특히나 2번 빨간색일때, 빨간색인 경우에는 이동한 후에 A번 말과 그 위에 있는 모든 말의 쌓여있는 순서를 반대로 바꾼다. 이 부분을 해결하기 위해서 전체적으로 자료구조를 뒤엎어야만 했다. 그 외 부분은 읽으면서 코드로 옮긴다면..
문제 https://www.acmicpc.net/problem/17779 17779번: 게리맨더링 2 재현시의 시장 구재현은 지난 몇 년간 게리맨더링을 통해서 자신의 당에게 유리하게 선거구를 획정했다. 견제할 권력이 없어진 구재현은 권력을 매우 부당하게 행사했고, 심지어는 시의 이름도 www.acmicpc.net 어떻게 풀 것인가? 사실 문제 자체가 길고, 너무 난해해서 어려웠던 문제 하지만, 문제를 이해하고 시키는 조건들을 코드로 바꾼다면 그리 어려운 알고리즘은 없는 그런 문제였다. 즉, 정말 빡센 브루트포스 + 구현 문제였다. 경계선을 구하기 위해서 단지 모든 경우의 수를 계산해야하만 한다. 즉, X,Y,D1,D2 모두를 4중 For문을 통해서 계속해서 경우의 수 모두를 검증하고 답을 찾는 문제였다...
문제 https://www.acmicpc.net/problem/13335 13335번: 트럭 입력 데이터는 표준입력을 사용한다. 입력은 두 줄로 이루어진다. 입력의 첫 번째 줄에는 세 개의 정수 n (1 ≤ n ≤ 1,000) , w (1 ≤ w ≤ 100) and L (10 ≤ L ≤ 1,000)이 주어지는데, n은 다리를 건너는 트 www.acmicpc.net 어떻게 풀 것인가? 구현은 너무나도 어렵다. 특정 알고리즘은 외우면 된다지만, 구현은 생각해야할 것들이 너무나도 많다. 이번 문제는 큐를 이용한 구현 문제였다. 내가 푼 문제의 코드를 뜯어보자. 다리는 Queue로 선언해 준고 여기에 다리의 길이만큼 0을 넣어준다. 다리의 길이만큼 이동하면서 Queue를 계산하게 된다 Queue bridge =..
문제 https://www.acmicpc.net/problem/2110 2110번: 공유기 설치 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 www.acmicpc.net 어떻게 풀 것인가? 처음에 감조차도 못잡았던 문제였다. 대략 1시간정도의 고민 끝에 다른 분의 풀이를 참고했다. 아마 이번 포스팅은 풀이보다는 회고 느낌으로 작성을 해야할 것 같다. 이 문제는 "이분탐색"을 물어보는 문제였다. 그렇다면 이러한 이분탐색을 어디에 활용할 수 있었을까? '최소 거리에 대해 설치 가능한 공유기'가 문제에서 주어지는..
