D.JOUNG

문제 : https://www.acmicpc.net/problem/2573 시간 제한메모리 제한난이도알고리즘 분류1초256 MBGold 4BFS  문제  풀이 보자마자 bfs를 사용해야겠다고 생각하게되는 나름 직관적인 문제다. 하지만 풀이법이 대강 생각나도, 실제 구현하는 부분에서 자잘한 오류가 발생하는 등 어려움이 있었다. 막막함을 조금이라도 줄여보고자 문제 풀이를 글로 작성하는 것 부터 시작했다.  1. 1년 후의 빙산 상태를 계산하여 저장한다.2. 1년 후 빙산들이 두 조각 이상으로 분리되었는 지, 완전히 녹아 없어졌는 지, 아직 한 덩이인 상태인 지 체크한다.3-1. 완전히 녹아 없어졌거나 두 조각 이상으로 분리되었다면 반복문을 탈출한다.3-2. 아직 한 덩이인 상태라면 1-3번을 다시 실행한다...

문제 : 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/1722 1722번: 순열의 순서첫째 줄에 N(1 ≤ N ≤ 20)이 주어진다. 둘째 줄의 첫 번째 수는 소문제 번호이다. 1인 경우 k(1 ≤ k ≤ N!)를 입력받고, 2인 경우 임의의 순열을 나타내는 N개의 수를 입력받는다. N개의 수에는 1부터 Nwww.acmicpc.net 시간 제한메모리 제한난이도알고리즘 분류2초128 MBGold 5조합, 수학, 구현  문제  풀이 소문제 1과 소문제 2로 나뉘어있지만 비슷한 방법으로 풀 수 있다. 무식하게 수열을 생성해 풀이하기에는 시간도 메모리도 부족할 것이라 계산해서 풀어야 한다.  핵심은 i 번째 숫자가 바뀌기 위해서는 (N-i)! 개의 순열을 지나야 한다는 법칙에 있다. 예를 들어 순열..

문제 : 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인 사람부..