2580번: 스도쿠 스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루 www.acmicpc.net IDEA 아주 오래전 군복무 중에 도전했던 문제다. 한창 재귀호출에 대해 (어설프게) 공부하고 있을 때 였는데 백트래킹이라는 것을 연습해보려 몇문제 덤벼들었다가 뼈도 못추린 적이 있었다. 그 때는 대강 이런 알고리즘을 생각했던 것 같다. 1. 입력을 받는다. 동시에 빈칸의 수를 센다. 2. 모든 칸을 순차적으로 확인한다. 3. 빈칸이라면 경우의 수를 파악한다. 4. 만약 한 가지 경우의 수만 있다면 그 칸을 채운다. 5. 아니라면 다음 칸을 확인한다. 6. 끝까..

3687번: 성냥개비 각 테스트 케이스에 대해서 입력으로 주어진 성냥개비를 모두 사용해서 만들 수 있는 가장 작은 수와 가장 큰 수를 출력한다. 두 숫자는 모두 양수이어야 하고, 숫자는 0으로 시작할 수 없다. www.acmicpc.net IDEA 성냥개비는 2개부터 주어진다. 1개의 성냥개비로는 만들 수 있는 숫자가 없다. 각 숫자를 만드는데 필요한 성냥개비의 수는 다음과 같다. 1 2 3 4 5 6 7 8 9 0 2개 5개 5개 4개 5개 6개 3개 7개 6개 6개 큰수를 만들기 위해서는 가능한 자릿수를 많게, 앞자리를 크게 해주면 된다. 단 2개의 성냥개비만 있으면 자릿수를 하나씩 늘려버릴 수 있다. 한개만 더 있으면 맨 앞자리를 1에서 7로 바꿀 수 있다. 가장 큰 숫자를 만들기는 이렇게 간단히 ..

1655번: 가운데를 말해요 첫째 줄에는 백준이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 백준이가 외치는 정수가 차례대로 주어진다. 정수는 -1 www.acmicpc.net IDEA 자료를 입력 받음과 동시에 정렬을 해내야하는 문제다. 중앙값을 입력과 동시에 최신화 해주어야하기 때문에 자료는 항상 중앙값에 한해 정렬된 상태를 유지한다. "어떤 자료 구조를 사용하고 어떻게 입력을 받아 정렬 상태를 유지해낼 것이냐"가 이 문제의 빡센 0.1초의 시간 제한을 뚫을 수 있냐 없냐를 결정하는 문제다. 먼저 일반적인 배열을 떠올렸다. 가장 작은 값이 맨 앞으로 오는 오름차순 정렬을 유지한다. 매 N번째 입력마다 Binary S..

1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 숨바꼭질 1번부터 시작해야겠다. 모든 정점 V가 범위 내의 정점 V + 1, V - 1, V * 2 와 연결되어있고 가중치는 1이다. BFS로 탐색을 시작해서 찾는대로 시간을 출력하게 하면 될 것 같다. using System; using System.Collections.Generic; class Program { static int n, k; static int[] time = new int[100001]; static bool[]..

1261번: 알고스팟 첫째 줄에 미로의 크기를 나타내는 가로 크기 M, 세로 크기 N (1 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 미로의 상태를 나타내는 숫자 0과 1이 주어진다. 0은 빈 방을 의미하고, 1은 벽을 의미 www.acmicpc.net IDEA 9376번 탈옥 문제를 보다가 난 아직 준비가 덜 된 것 같아서 분류되어있는 더 쉬운 문제를 찾다 풀게 되었다. 다익스트라 알고리즘의 한 종류인데 특이하게 가중치가 0, 1 밖에 없다. '0-1 너비우선 탐색' 문제다. 이건 BFS로 해결할 수 있다. 정석적인 풀이를 찾아보려고 고수님들의 설명을 찾아보다 justicehui님의 깃허브 페이지에 있는 글을 발견했다. 요약하면 그래프 G에 V개의 정점, E개의 간선이 있고 가중치는 0,..

높은 정확도의 자료 처리를 위해 float, double과 같은 부동소수점 자료형과 decimal 자료형을 사용할 수 있다. 그런데 소수점 아래의 정확도가 아닌 큰 수의 정확한 처리는 어떨까. 자주 사용하는 정수형 int보다 더 큰 값은 long, 더 큰 값은 ulong, 그보다 더 큰 값은 어떻게 처리할까. 한 때는 오버플로우 되는 값을 미리 처리하기 위해 최대값의 절반 범위에서 넘어간 값을 다른 변수에 옮겨담아 자리올림 같은 개념으로 구현한 적이 있다. A0 = 1,073,741,823 ( int.Maxvalue / 2 )일 때 A0 값이 1 증가하면 A1 = 1, A0 = 0 이 되는 식 이렇게 하면 물론 간단한 덧셈 뺄셈은 쉽게 구현 가능하지만 곱셈은? 나눗셈은? 답이 안나온다. 심지어 저런 식으..

1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net IDEA 두 알고리즘은 이름에서 나타내는 것처럼 탐색의 우선순위가 다르다. 최초 탐색 지점에서 연결된 곳들을 순차적으로 확인하는 너비우선탐색(BFS)은 한 계층의 정점을 모두 확인하고 다음 계층으로 내려가기 때문에 최단거리를 찾는 탐색에서 유리하다. 깊이우선탐색(DFS)은 탐색 경로를 기억해둬야할 때 유리하다. 모든 정점을 탐색해야하는 문제에서는 어떤 알고리즘을 선택해도 시간복잡도 상의 차이는 없다. 이 문제는 모든 정점을 탐색해야하는 문제이기 때문에 너비우선탐색, 깊이우선..

11051번: 이항 계수 2 첫째 줄에 \(N\)과 \(K\)가 주어진다. (1 ≤ \(N\) ≤ 1,000, 0 ≤ \(K\) ≤ \(N\)) www.acmicpc.net IDEA 이항 계수를 구하는 문제다. 간단한 다음 공식을 사용하면 바로 해결 가능하다. 그런데 여기서 간단하지 않은 것은 주어진 N의 최댓값이 1,000이다. 20!만 계산해도 long의 표현 범위를 넘어가버린다. 그래서 이 문제에도 분할 정복을 사용해야한다. 그리고 값을 10,007로 나눈 나머지를 출력해야한다. 연산을 모두 끝내고 한꺼번에 나머지를 출력하기엔 너무 큰 숫자를 처리하기 어려울 것 같다. 모듈러 연산을 이용하면 좋겠지만 나눗셈에 대한 모듈러 연산은 없다. 페르마의 소정리에 따르면 어떤 수 a가 정수이고 p가 소수일 때..