1987번: 알파벳 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으 www.acmicpc.net IDEA 모든 가능성을 탐색하고 최적의 결과를 얻어내는 문제다. 처음에는 아무 생각 없이 BFS를 시도했다. 이 문제는 탐색 과정에 문자를 계속 붙여나가고 이걸 String으로 관리한다면 쓸모없는 메모리가 엄청 늘어날 것이다. 그래서 나는 StringBuilder로 경로를 저장하고 이걸 큐에 돌려 BFS를 실행하기로 했다. 너무 짧은 생각이었다. 문자 형식 데이터는 16바이트를 차지한다. 만약 한 지점에서 모든 방향이 가능했고 1회 탐색을 시도했다면 32..

20162번: 간식 파티 서울이는 입맛이 까다로운 고양이다. 입맛이 까다로운 서울이는 전에 먹었던 간식보다 더 맛있는 간식만 먹는다. 서울이는 간식의 평점이 높을수록 맛있다고 느낀다. 집사는 서울이에게 N 일 www.acmicpc.net IDEA 이 문제는 아주 오래전 시도했다가 틀린 문제다. 입출력만 겨우겨우 하던 당시에는 너무 어렵다고 생각해서 취침 시간을 12분 남겨놓고 포기했던 모양이다. 문제를 간단히 정리하면 이렇다. 1. 서울이는 N일 동안 이어지는 간식 파티에서 간식을 골라 먹는다. 2. 서울이는 이전에 먹었던 간식보다 더 평점이 높은 간식만 먹는다. 3. 간식 파티가 끝날 때까지 서울이가 먹은 간식의 평점 총합의 최고치는? 오늘이 i일이고 오늘 주어지는 간식의 평점을 snack[ i ], ..

12100번: 2048 (Easy) 첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2 www.acmicpc.net IDEA 브루트포스 문제는 복잡한 생각을 할 필요가 없어서 좋다. 한 때 재밌게 하던 2048 게임을 구현하는 문제다. 모든 가능성을 탐색해서 원하는 결과를 뽑아내면 된다. 탐색 과정에서 이전 과정을 기억해두고 되돌아가 다른 경로를 탐색할 수 있도록 하는 것이 관건이다. N * N 크기의 배열을 스택에 담아 탐색 과정을 관리하도록 했다. 처음에는 N * N 배열을 매개변수로 하는 재귀 호출로 구현했다. 그런데 매개변수로 받아온 데이터는..

9184번: 신나는 함수 실행 입력은 세 정수 a, b, c로 이루어져 있으며, 한 줄에 하나씩 주어진다. 입력의 마지막은 -1 -1 -1로 나타내며, 세 정수가 모두 -1인 경우는 입력의 마지막을 제외하면 없다. www.acmicpc.net IDEA 코드가 문제에 그대로 제시되어있어서 그대로 해봤다. w(11,11,11)만 해도 구하는데 몇분 걸린다. 이런 재귀호출의 경우 똑같은 매개변수로 호출된 메소드가 엄청나게 많다. 그럼 첫 호출에 어떤 값에 대한 정보를 기억해두면 두번째부터 불필요한 호출은 줄일 수 있다. 이렇게 여러번 호출될 값을 미리 저장해놓고 다음 호출에 저장된 값을 바로 출력해주는 방법을 메모이제이션 이라고 한다. 간단히 3차원 배열로 구현했다. CODE using System; clas..

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로 바꿀 수 있다. 가장 큰 숫자를 만들기는 이렇게 간단히 ..

입력에 따라 분기를 나누어 처리할 때 분기마다 번호를 부여해주는 방법을 주로 사용했다. 예를 들어 체스 프로그램을 만든다고 하면 백은 양수, 흑은 음수로 킹은 1, 퀸은 2, 비숍은 3, 나이트는 4, 룩은 5, 폰은 6 이런식으로. 체스 정도면 어느정도 가독성을 유지할 수 있겠지만 만약 더 다양한 분기를 나누는 경우엔 코드를 한참 짜다 돌아봤을 때 1번이 뭔지, 5번이 뭔지, 27번이 뭐였는지 알아보기 힘들 수 있다. 이런 불편함을 막고 개발자의 편의를 보장하기 위해 enum 자료형이 있다. 열거형 자료는 enum 키워드로 선언하고 항상 정수 기반이기 때문에 사용할 수 있다. 그럼 체스 기물들은 이런 식으로 표현할 수 있다. using System; class Program { enum Pieces :..

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