D.JOUNG

문제 : https://www.acmicpc.net/problem/12852 시간 제한메모리 제한난이도알고리즘 분류0.5초512 MBSilver 1다이나믹 프로그래밍  문제  풀이0.5초의 시간제한이 있는 문제다. N의 범위는 1부터 10의 6승까지이므로 반복문 중첩을 피할 수 있는 방법으로 풀이를 생각해봐야 한다. 특정 숫자 N이 주워졌을 때 최단 횟수로 1로 만들어지는 과정을 직접 샤프로 써가며 정리해본다. N = 1010 → 9 → 3 → 1 N = 99 → 3 → 1  N = 88 → 4 → 2 → 1 N = 77 → 6 → 3 → 1 (이하 생략..) 숫자 네 개를 정리했을 뿐인데도 벌써 규칙이 보인다. 예를 들어 10의 경우, N이 9인 경우에서 맨 앞에 10이 붙었을 뿐이다. 이처럼 각 숫자..

문제 : https://www.acmicpc.net/problem/1707 1707번: 이분 그래프 입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V와 간선의 개수 E가 빈 칸을 사이에 www.acmicpc.net 시간 제한 메모리 제한 난이도 알고리즘 분류 2초 256 MB Gold 4 그래프, 문제 풀이 이분 그래프인지 판별하려면 시작 노드를 하나 정하고, 근처 노드를 지나가며 두 가지 색을 차례대로 칠해나가면 된다. 그 과정을 반복하다보면 마지막 노드에 도착할 때까지 무탈한 그래프가 있고, 중간에 같은 색을 칠해야하는 모순이 발생하는 그래프가 있다. 모순이 발생하지 않고 무사히 순회가 종료된다..

문제 : https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 시간 제한 메모리 제한 난이도 알고리즘 분류 1초 192 MB Silver 1 그래프, BFS 문제 풀이 그래프 경로 탐색에서 최단 거리를 구하는 문제이다. 목표 지점까지 도달하는 경우의 수를 구하는 문제라면 한 라인을 끝까지 검사하는 DFS가 적합하겠지만, 해당 문제는 최단 거리를 요구하고 있으므로 모든 가능 경로를 한 노드씩 번갈아가며 점검해나가는 BFS가 시간복잡도 측면에서 훨씬 적합하다. 게다가 시간 제한을 1초..

문제 : https://www.acmicpc.net/problem/2023 2023번: 신기한 소수 수빈이가 세상에서 가장 좋아하는 것은 소수이고, 취미는 소수를 가지고 노는 것이다. 요즘 수빈이가 가장 관심있어 하는 소수는 7331이다. 7331은 소수인데, 신기하게도 733도 소수이고, 73도 소수 www.acmicpc.net 시간 제한 메모리 제한 난이도 알고리즘 분류 2초 4 MB Gold 5 수학, 정수론, 백트래킹 문제 풀이 소수 구하는 문제를 마주쳤을 때 가장 먼저 떠오르는 풀이법은 에라토스테네스의 체이다. 하지만 소수인지 판별해야하는 수의 최대값은 99,999,999 이므로, 에라토스테네스의 체로 1부터 99,999,999 까지의 판별 정보를 저장하기 위해서는 4MB가 넘는 크기의 배열이 ..

문제 : https://www.acmicpc.net/problem/2447 2447번: 별 찍기 - 10 재귀적인 패턴으로 별을 찍어 보자. N이 3의 거듭제곱(3, 9, 27, ...)이라고 할 때, 크기 N의 패턴은 N×N 정사각형 모양이다. 크기 3의 패턴은 가운데에 공백이 있고, 가운데를 제외한 모든 칸에 별이 www.acmicpc.net 시간 제한 메모리 제한 난이도 알고리즘 분류 1초 256 MB Gold 5 분할정복, 재귀 문제 풀이 3을 N으로 줬을 때 출력되는 패턴이 재귀적으로 반복되고 있다. 패턴을 분석해보면 아래와 같다. 1. 한 변의 출력 개수는 N개이다. (* or ' ') 2. N*N 개의 출력으로 이루어진 크기 N의 패턴을 한 줄에 3 부분 씩 9 부분으로 나누면, 각 부분에서..

문제 : https://www.acmicpc.net/problem/1074 1074번: Z 한수는 크기가 2N × 2N인 2차원 배열을 Z모양으로 탐색하려고 한다. 예를 들어, 2×2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다. N > 1인 경우, 배열을 www.acmicpc.net 시간 제한 메모리 제한 난이도 알고리즘 분류 0.5초 512 MB Silver1 분할정복, 재귀 문제 풀이 문제에서 주어진 예제를 들여다보면 z 모양을 그리며 이동하는 재귀적 패턴을 찾을 수 있다. 표의 한 변에 있는 숫자의 개수를 noc(NumOfCells)라고 했을 때, 문제는 noc*noc 개의 칸으로 이루어진 표를 균등하게 4분면으로 나눈 후, 2사분면 → 1사분면 → 3..

문제 : https://www.acmicpc.net/problem/11729 11729번: 하노이 탑 이동 순서 세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로 www.acmicpc.net 시간 제한 메모리 제한 난이도 알고리즘 분류 1초 256 MB Gold 5 재귀 문제 풀이 재귀함수의 대표격 사례인 하노이의 탑이다. 사실 나는 재귀함수를 아직도 많이 어려워하는 편이다. 쉬운 문제들은 간단히 풀리기도 하지만, 문제가 복잡해질 수록 종료조건과 재귀호출 매개변수를 어떻게 구성해야할 지 감도 안잡힐때가 많았다. 원판의 변화를 손으로 그려가보며 재귀의 구조를 설계해..

문제 : https://www.acmicpc.net/problem/1138 1138번: 한 줄로 서기 첫째 줄에 사람의 수 N이 주어진다. N은 10보다 작거나 같은 자연수이다. 둘째 줄에는 키가 1인 사람부터 차례대로 자기보다 키가 큰 사람이 왼쪽에 몇 명이 있었는지 주어진다. i번째 수는 0보다 www.acmicpc.net 시간 제한 메모리 제한 난이도 알고리즘 분류 2초 128 MB Silver 2 구현 문제 풀이 4명의 사람이 줄을 선다면 각 사람들의 키는 1부터 4까지이고, 5명의 사람이 줄을 선다면 각 사람들의 키는 1부터 5까지이다. 이런 식으로 1부터 N까지의 키를 가진 N명의 사람이 문제에서 주어진 규칙에 따라 줄을 섰을 때 왼쪽부터 순서대로 출력하는 문제이다. 문제에서는 키 1인 사람부..

문제 : https://www.acmicpc.net/problem/1654 1654번: 랜선 자르기 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 www.acmicpc.net 시간 제한 메모리 제한 난이도 알고리즘 분류 2초 128 MB Silver 2 이분 탐색 문제 풀이 문제의 내용을 요약하자면, 주어진 K개의 랜선을 잘라 N개 이상의 (동일한 길이의) 랜선을 만들어야 하는데, 그 때 만든 랜선의 길이가 가장 긴 경우의 길이를 구하는 문제이다. 예제의 경우 길이가 차례대로 802, 743, 457, 539 인 네 개의 랜선이 주..

문제 : https://www.acmicpc.net/problem/1913 1913번: 달팽이 N개의 줄에 걸쳐 표를 출력한다. 각 줄에 N개의 자연수를 한 칸씩 띄어서 출력하면 되며, 자릿수를 맞출 필요가 없다. N+1번째 줄에는 입력받은 자연수의 좌표를 나타내는 두 정수를 한 칸 띄어서 www.acmicpc.net 시간 제한 메모리 제한 난이도 알고리즘 분류 2초 128 MB Silver 3 구현 문제 풀이 수열을 구성해 출력하는 종류의 문제를 푸는 방법은 일반적으로 두 가지다. 하나는 수열 크기 만큼의 배열을 구성해 각 인덱스에 알맞는 수를 채워넣은 후 배열을 출력하는 것이고, 다른 하나는 수열의 각 인덱스 자리마다의 규칙을 파악해 수열의 앞 숫자부터 계산하여 출력하는 것이다. 해당 문제에서도 잘 ..