지속 가능한 꾸준함

www.acmicpc.net/problem/17825 17825번: 주사위 윷놀이 주사위 윷놀이는 다음과 같은 게임판에서 하는 게임이다. 처음에는 시작 칸에 말 4개가 있다. 말은 게임판에 그려진 화살표의 방향대로만 이동할 수 있다. 말이 파란색 칸에서 이동을 시작하면 � www.acmicpc.net 본문에 앞서 해당 문제는 다른 분들의 솔루션을 참고하고 풀었음을 밝힙니다. 솔루션을 참고하여 풀었으나 완전히 이해하고 푸는데 이틀씩이나 걸린 문제입니다. 해당 문제는 총 10차례동안 나온 주사위 값을 토대로 4마리의 말을 움직여 문제 규칙에따라 얻을 수 있는 점수의 최댓값을 출력하는 문제입니다. 저는 브루트 포스 알고리즘을 이용하여 해당 문제를 풀었습니다. 즉, 각 차례별로 나온 주사위 값에따라 4마리의 말..

www.acmicpc.net/problem/4796 4796번: 캠핑 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, L, P, V를 순서대로 포함하고 있다. 모든 입력 정수는 int범위이다. 마지막 줄에는 0이 3개 주어진다. www.acmicpc.net 본 문제는 입력받은 휴가 일수 V 와 캠핑장의 연속 운영 일수 P, 캠핑장의 사용 가능 일수 L 간의 관계성을 찾으면 쉽게 모델링하여 해결할 수 있는 문제였습니다. 강산이가 캠핑장을 최대로 이용할 수 있는 일수를 Y 라 할때, Y 는 아래의 수식으로 부터 계산될 수 있습니다. Y = (V / P) x L + min(V % P, L) (1) (V / P) 의 결과는 정수형이다. 예시로 들어 설명하면 강산이의..

www.acmicpc.net/problem/1793 1793번: 타일링 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있으며, 숫자 0 ≤ n ≤ 250이 주어진다. www.acmicpc.net 간단한 DP 알고리즘으로 풀리는 문제입니다. 그런데, C++ 의 기본 정수 자료형(int, long long, unsigned long long 등)을 사용하여 다룰 수 있는 값보다 처리되는 값의 크기가 크다는 문제가 있었습니다. 이러한 큰 수를 처리할 수 있도록 string 자료형을 사용하였고, 연산 과정은 string 으로 표현된 10진 숫자를 Digit 단위로 접근하여 더하는 식으로 구현하였습니다. 주의할 점으로 2x0 직사각형을 채우는 방법의 수를 1로 두고 문제를..

www.acmicpc.net/problem/3197 3197번: 백조의 호수 입력의 첫째 줄에는 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1500. 각 R줄 동안 C만큼의 문자열이 주어진다. '.'은 물 공간, 'X'는 빙판 공간, 'L'은 백조가 있는 공간으로 나타낸다. www.acmicpc.net 본문에 앞서 해당 문제는 다른 분들의 솔루션을 참고하고 풀었음을 밝힙니다. 알고리즘 구현시 최적화를 굉장히 많이 신경써야 하는 문제였습니다. 알고리즘은 다음과 같습니다. 1. 두 백조 중, 한 백조를 고정시키고 나머지 한 백조를 이동시키며 방문할 수 있는 지역을 방문한다. 이 때, 고정된 백조가 있는 지역에 방문하면 현재 일자를 정답으로 출력한다. 2. 호수의 상태를 업데이트 한다. 3. 일자를 업데이..

www.acmicpc.net/problem/1562 1562번: 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 본문에 앞서 해당 문제는 다른 분들의 솔루션을 참고하고 풀었음을 밝힙니다. 이제껏 푼 문제 중 가장 어려웠습니다... 다른 분들의 솔루션을 참고해도 이해가 잘 안될정도 였습니다... 먼저, n 자리 계단수의 수(큰 문제)는 n-1 자리 계단수의 수(작은 문제)로 계산될 수 있습니다(다이나믹 프로그래밍 기법을 이용하기에 적합함). 그런데, 문제에서는 단순히 n 자리 계단수의 수를 묻지 않고 n 자리 계단수 중에서 0, 1, 2, ..., 9 를 모두 포함하는 계단수의 수를 묻고있습니다. 이는 문제를 복잡하게 만드는 요소로 이를 계산하기..

https://programmers.co.kr/learn/courses/30/lessons/43238 코딩테스트 연습 - 입국심사 n명이 입국심사를 위해 줄을 서서 기다리고 있습니다. 각 입국심사대에 있는 심사관마다 심사하는데 걸리는 시간은 다릅니다. 처음에 모든 심사대는 비어있습니다. 한 심사대에서는 동시에 한 � programmers.co.kr 본문에 앞서 해당 문제는 다른 분들의 솔루션을 참고하고 풀었음을 밝힙니다. 본 문제는 문제가 속한 카테고리를 보면 알 수 있듯이 이분탐색 기법을 사용하여 해결할 수 있는 문제입니다. 이분탐색 기법을 사용하여 문제를 풀라고 힌트를 주었지만, 이분탐색 기법을 어떻게 적용해야할지 도저히 감을 잡을 수 없었습니다. 다른 분들의 솔루션을 곰곰히 읽어보니 이분탐색에 대한..

https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 본 문제는 주어진 수열로부터 가장 긴 증가하는 부분 수열의 크기를 계산하는 문제입니다. 해당 문제는 Longest Increasing Subsequence Problem 이라는 영명으로 존재하는 굉장히 유명한 알고리즘 문제였습니다. 저는 다이나믹 프로그래밍 기법을 사용하여 해당 문제를 풀었습니다. 예시를 들어 설명드리도..

https://www.acmicpc.net/problem/11437 11437번: LCA 첫째 줄에 노드의 개수 N이 주어지고, 다음 N-1개 줄에는 트리 상에서 연결된 두 정점이 주어진다. 그 다음 줄에는 가장 가까운 공통 조상을 알고싶은 쌍의 개수 M이 주어지고, 다음 M개 줄에는 정� www.acmicpc.net 본문에 앞서 해당 문제는 다른 분들의 솔루션을 참고하고 풀었음을 밝힙니다. LCA 는 Lowest Common Ancestor 의 축약어로써 트리에서 특정 두 노드의 공통 조상(Ancestor) 노드 중에서 Depth 가 가장 큰 노드를 찾는 문제입니다. 이와 관련하여 정리가 잘된 글이 있어 링크를 첨부합니다. https://jason9319.tistory.com/90 저는 아래와 같이 알..

https://www.acmicpc.net/problem/1766 1766번: 문제집 첫째 줄에 문제의 수 N(1 ≤ N ≤ 32,000)과 먼저 푸는 것이 좋은 문제에 대한 정보의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 둘째 줄부터 M개의 줄에 걸쳐 두 정수의 순서쌍 A,B가 빈칸을 사이에 두고 주 www.acmicpc.net 본문에 앞서 해당 문제는 다른 분들의 솔루션을 참고하고 풀었음을 밝힙니다. 본 문제는 조건에 따라 작업의 순서를 구하는 문제입니다. 순서가 정해져있는 작업을 풀때 우리는 위상 정렬(Topology Sort) 알고리즘을 사용할 수 있습니다. 문제를 풂에 앞서 저는 나동빈님의 위상 정렬 강의를 수강하였습니다. 먼저, 문제에 맞게 그래프를 구성해야합니다. 예제를 기준으로 ..