# 알고리즘 문제해결 전략
알고리즘 문제해결 전략 Chapter 30 - ROUTING(C++)
예제: 신호 라우팅 >image.png >위 그림은 여러 개의 컴퓨터들과 각 컴퓨터들을 잇는 회선을 나타냅니다. 각 회선들은 각각 품질이 다르며, 각 회선을 지날 때마다 신호에 있던 노이즈가 증폭될 수 있습니다. 각 회선에 쓰여 있는 글자는 해당 회선을 지날 때 노이즈가 몇 배 증폭되는가를 보여줍니다. 특정 컴퓨터에서 다른 컴퓨터로 메시지를 보내고 싶습니다...
알고리즘 문제해결 전략 Chapter 10 - LUNCHBOX(C++)
예제: 도시락 데우기 >After suffering from the deficit in summer camp, Ainu7 decided to supply lunch boxes instead of eating outside for Algospot.com winter camp. > >He contacted the famous packed lunch compan...
알고리즘 문제해결 전략 Chapter 10 - MATCHORDER(C++)
예제: 출전 순서 정하기 >전세계 최대의 프로그래밍 대회 알고스팟 컵의 결승전이 이틀 앞으로 다가왔습니다. 각 팀은 n명씩의 프로 코더들로 구성되어 있으며, 결승전에서는 각 선수가 한 번씩 출전해 1:1 경기를 벌여 더 많은 승리를 가져가는 팀이 최종적으로 우승하게 됩니다. 각 팀의 감독은 대회 전날, 주최측에 각 선수를 출전시킬 순서를 알려 주어야 합니다...
알고리즘 문제해결 전략 Chapter 28 - WORDCHAIN(C++)
예제: 단어 제한 끝말잇기 >끝말잇기는 참가자들이 원을 그리고 앉은 뒤, 시계 방향으로 돌아가면서 단어를 말하는 게임입니다. 이 때 각 사람이 말하는 단어의 첫 글자는 이전 사람이 말한 단어의 마지막 글자와 같아야 합니다. 단어 제한 끝말잇기는 일반적인 끝말잇기와 달리 사용할 수 있는 단어의 종류가 게임 시작 전에 미리 정해져 있으며, 한 단어를 두 번 사...
알고리즘 문제해결 전략 Chapter 09 - NUMBERGAME(C++)
예제: 숫자 게임 >n개의 정수를 일렬로 늘어놓은 게임판을 가지고 현우와 서하가 게임을 합니다. 게임은 현우부터 시작해서 번갈아가며 진행하며, 각 참가자는 자기 차례마다 두 가지 일 중 하나를 할 수 있습니다. > >- 게임판의 왼쪽 끝에 있는 숫자나 오른쪽 끝에 있는 숫자 중 하나를 택해 가져갑니다. 가져간 숫자는 게임판에서 지워집니다. 게임판에 두 개 ...
알고리즘 문제해결 전략 Chapter 28 - DICTIONARY(C++)
예제: 고대어 사전 >아마추어 고고학자인 일리노이 존스는 시카고 근교에서 고대 문명의 흔적을 찾아냈습니다. 그 흔적 중에는 이 언어의 사전도 포함되어 있었는데, 이 사전에 포함된 단어들은 모두 영어의 소문자 알파벳으로 구성되어 있었지만 사전에 포함된 단어의 순서들이 영어와 서로 달랐습니다. 발굴팀은 단어들이 사전 순이 아닌 다른 순서대로 정렬되어 있는지, ...
알고리즘 문제해결 전략 Chapter 09 - TICTACTOE(C++)
예제: 틱택토 >틱택토는 3x3 크기의 게임판에서 하는 3목 게임입니다. 두 명이 번갈아가며 o와 x를 게임판의 빈 칸에 쓰되, 먼저 같은 글자를 가로, 세로 혹은 대각선으로 3개 쓰이도록 하는 쪽이 이깁니다. 예를 들어, 다음 게임판은 x가 이긴 게임판입니다. > 게임은 항상 x부터 시작합니다. > >틱택토 게임판의 현재 상태가 주어집니다. 두 사람 모두...
알고리즘 문제해결 전략 Chapter 23 - RUNNINGMEDIAN(C++)
예제: 변화하는 중간값 >한 수열의 중간값(median)은 이 수열을 정렬했을 때 가운데 오는 값입니다. 예를 들어 {3,1,5,4,2}를 정렬했을 때 가운데 오는 값은 3이지요. 수열의 길이가 짝수일 때는 가운데 있는 두 값 중 보다 작은 것을 수열의 중간값이라고 정의하도록 합시다. > >한 수열의 중간값은 수열에 새로운 수가 추가될 때마다 바뀔 수 있습...
알고리즘 문제해결 전략 Chapter 08 - SNAIL(C++)
예제: 장마가 찾아왔다 >깊이가 n 미터인 우물의 맨 밑바닥에 달팽이가 있습니다. 이 달팽이는 우물의 맨 위까지 기어올라가고 싶어하는데, 달팽이의 움직임은 그 날의 날씨에 좌우됩니다. 만약 비가 내리면 달팽이는 하루에 2미터를 기어올라갈 수 있지만, 날이 맑으면 1미터밖에 올라가지 못합니다. > >여름 장마가 찾아와, 앞으로 m 일간 각 날짜에 비가 올 확...
알고리즘 문제해결 전략 Chapter 21 - TRAVERSAL(C++)
예제: 트리 순회 순서 변경 >트리를 순회하는 알고리즘은 트리의 모든 노드들을 특정 순서에 맞춰 방문하지만, 트리는 배열처럼 1차원적인 구조가 아니기 때문에 단 한 가지의 당연한 순서가 존재하지 않습니다. 때문에 필요에 맞춰 순서를 정의해야 합니다. 이진 트리(binary tree)는 모든 노드에 왼쪽과 오른쪽, 최대 두 개의 자손이 있는 트리를 말하는데,...
알고리즘 문제해결 전략 Chapter 08 - TILING2(C++)
예제: 타일링 방법의 수 세기 >2xn 크기의 사각형을 2x1 크기의 사각형으로 빈틈없이 채우는 경우의 수를 구하는 프로그램을 작성하세요. > >예를 들어 n=5라고 하면 다음 그림과 같이 여덟 가지의 방법이 있습니다. (알고스팟 홈페이지에 그림이 없어서, 임의로 3개만 그렸다. 8개 그리기는 귀찮았다!!) > >image.png > >경우의 수는 n이 커...
알고리즘 문제해결 전략 Chapter 08 - PI(C++)
예제: 원주율 외우기 >문제 >(주의: 이 문제는 TopCoder 의 번역 문제입니다.) > >가끔 TV 에 보면 원주율을 몇만 자리까지 줄줄 외우는 신동들이 등장하곤 합니다. 이들이 이 수를 외우기 위해 사용하는 방법 중 하나로, 숫자를 몇 자리 이상 끊어 외우는 것이 있습니다. 이들은 숫자를 세 자리에서 다섯 자리까지로 끊어서 외우는데, 가능하면 55...
알고리즘 문제해결 전략 Chapter 08 - JLIS(C++)
예제: 합친 LIS >문제 >어떤 수열에서 0개 이상의 숫자를 지운 결과를 원 수열의 부분 수열이라고 부릅니다. 예를 들어 '4 7 6'은 '4 3 7 6 9'의 부분 수열입니다. 중복된 숫자가 없고 오름 차순으로 정렬되어 있는 부분 수열들을 가리켜 증가 부분 수열이라고 부르지요. 예를 들어 '3 6 9'는 앞의 수열의 증가 부분 수열입니다. > >두 개...
알고리즘 문제해결 전략 Chapter 20 - PALINDROMIZE(C++)
예제: 팰린드롬 만들기 >문제 >앞에서부터 읽었을 때와 뒤로부터 읽었을 때 똑같은 문자열을 팰린드롬(palindrome)이라고 합니다. 예를 들면 “noon”이나 “stats” 같은 단어들이 팰린드롬입니다. 주어진 문자열 S 뒤에 적절히 문자열을 붙여서 S 를 팰린드롬으로 만들려고 합니다. 예를 들어 S = “anon”이면 뒤에 “ona”를 붙여서 “an...
알고리즘 문제해결 전략 Chapter 08 - LIS(C++)
예제: 최대 증가 부분 수열 >문제 >어떤 정수 수열에서 0개 이상의 숫자를 지우면 이 수열의 부분 수열 (subsequence) 를 얻을 수 있다. 예를 들어 10 7 4 9 의 부분 수열에는 7 4 9, 10 4, 10 9 등이 있다. 단, 10 4 7 은 원래 수열의 순서와 다르므로 10 7 4 9 의 부분 수열이 아니다. > >어떤 부분 수열이 순...
알고리즘 문제해결 전략 Chapter 20 - NAMING(C++)
예제: 접두사/접미사 >문제 아주대에 사는 외수는 작명에 능하기로 유명해서 많은 부부들이 아주대로 몰려와서 태어나는 아이들의 이름을 지어달라고 한다. 부부들은 이름은 잘 짓는게 출세에 영향을 미친다고 생각을 하고 있으며, 따라서 좋은 이름을 지어 출세하기를 기원한다. 허나 게으른 외수에게 작명은 지루한 작업이다. 효율적으로 일을 하고자 궁리하던 차에 쉽지...
알고리즘 문제해결 전략 Chapter 08 - TRIANGLEPATH(C++)
예제: 삼각형 위의 최대 경로 >문제 > >위 형태와 같이 삼각형 모양으로 배치된 자연수들이 있습니다. 맨 위의 숫자에서 시작해, 한 번에 한 칸씩 아래로 내려가 맨 아래 줄로 내려가는 경로를 만들려고 합니다. 경로는 아래 줄로 내려갈 때마다 바로 아래 숫자, 혹은 오른쪽 아래 숫자로 내려갈 수 있습니다. 이 때 모든 경로 중 포함된 숫자의 최대 합을 찾...
알고리즘 문제해결 전략 Chapter 19 - BRACKETS2(C++)
예제: 짝이 맞지 않는 괄호 >문제 Best White is a mathematics graduate student at T1 University. Recently, he finished writing a paper and he decided to polish it. As he started to read it from the beginning, he r...
알고리즘 문제해결 전략 Chapter 08 - JUMPGAME(C++)
예제: 외발 뛰기 >문제 vue image 땅따먹기를 하다 질린 재하와 영훈이는 땅따먹기의 변종인 새로운 게임을 하기로 했습니다. 이 게임은 그림과 같이 n*n 크기의 격자에 각 1부터 9 사이의 정수를 쓴 상태로 시작합니다. 각 차례인 사람은 맨 왼쪽 윗 칸에서 시작해 외발로 뛰어서 오른쪽 아래 칸으로 내려가야 합니다. 이 때 각 칸에 적혀 있는 숫자만...
알고리즘 문제해결 전략 Chapter 18 - JOSEPHUS(C++)
예제: 조세푸스 문제 >문제 1세기에 살던 역사학자 조세푸스는 로마와의 전쟁에서 패해 N - 1명의 동료 병사들과 함께 출구가 없는 동굴에 포위당했다고 합니다. 동료 병사들은 로마에 항복하느니 차라리 자살하자고 결의했고, 포위당한 N명의 사람들이 모두 원형으로 둘러선 뒤 순서대로 자살하기로 했습니다. 한 사람이 자살하면, 다음에는 그 사람으로부터 시계 방...