# 알고리즘 문제해결 전략

27개의 포스트

알고리즘 문제해결 전략 Chapter 30 - ROUTING(C++)

예제: 신호 라우팅 >image.png >위 그림은 여러 개의 컴퓨터들과 각 컴퓨터들을 잇는 회선을 나타냅니다. 각 회선들은 각각 품질이 다르며, 각 회선을 지날 때마다 신호에 있던 노이즈가 증폭될 수 있습니다. 각 회선에 쓰여 있는 글자는 해당 회선을 지날 때 노이즈가 몇 배 증폭되는가를 보여줍니다. 특정 컴퓨터에서 다른 컴퓨터로 메시지를 보내고 싶습니다...

2020년 2월 9일
·
0개의 댓글

알고리즘 문제해결 전략 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...

2020년 2월 5일
·
0개의 댓글

알고리즘 문제해결 전략 Chapter 10 - MATCHORDER(C++)

예제: 출전 순서 정하기 >전세계 최대의 프로그래밍 대회 알고스팟 컵의 결승전이 이틀 앞으로 다가왔습니다. 각 팀은 n명씩의 프로 코더들로 구성되어 있으며, 결승전에서는 각 선수가 한 번씩 출전해 1:1 경기를 벌여 더 많은 승리를 가져가는 팀이 최종적으로 우승하게 됩니다. 각 팀의 감독은 대회 전날, 주최측에 각 선수를 출전시킬 순서를 알려 주어야 합니다...

2020년 2월 4일
·
0개의 댓글

알고리즘 문제해결 전략 Chapter 28 - WORDCHAIN(C++)

예제: 단어 제한 끝말잇기 >끝말잇기는 참가자들이 원을 그리고 앉은 뒤, 시계 방향으로 돌아가면서 단어를 말하는 게임입니다. 이 때 각 사람이 말하는 단어의 첫 글자는 이전 사람이 말한 단어의 마지막 글자와 같아야 합니다. 단어 제한 끝말잇기는 일반적인 끝말잇기와 달리 사용할 수 있는 단어의 종류가 게임 시작 전에 미리 정해져 있으며, 한 단어를 두 번 사...

2020년 2월 2일
·
0개의 댓글

알고리즘 문제해결 전략 Chapter 09 - NUMBERGAME(C++)

예제: 숫자 게임 >n개의 정수를 일렬로 늘어놓은 게임판을 가지고 현우와 서하가 게임을 합니다. 게임은 현우부터 시작해서 번갈아가며 진행하며, 각 참가자는 자기 차례마다 두 가지 일 중 하나를 할 수 있습니다. > >- 게임판의 왼쪽 끝에 있는 숫자나 오른쪽 끝에 있는 숫자 중 하나를 택해 가져갑니다. 가져간 숫자는 게임판에서 지워집니다. 게임판에 두 개 ...

2020년 1월 27일
·
0개의 댓글

알고리즘 문제해결 전략 Chapter 28 - DICTIONARY(C++)

예제: 고대어 사전 >아마추어 고고학자인 일리노이 존스는 시카고 근교에서 고대 문명의 흔적을 찾아냈습니다. 그 흔적 중에는 이 언어의 사전도 포함되어 있었는데, 이 사전에 포함된 단어들은 모두 영어의 소문자 알파벳으로 구성되어 있었지만 사전에 포함된 단어의 순서들이 영어와 서로 달랐습니다. 발굴팀은 단어들이 사전 순이 아닌 다른 순서대로 정렬되어 있는지, ...

2020년 1월 25일
·
0개의 댓글

알고리즘 문제해결 전략 Chapter 09 - TICTACTOE(C++)

예제: 틱택토 >틱택토는 3x3 크기의 게임판에서 하는 3목 게임입니다. 두 명이 번갈아가며 o와 x를 게임판의 빈 칸에 쓰되, 먼저 같은 글자를 가로, 세로 혹은 대각선으로 3개 쓰이도록 하는 쪽이 이깁니다. 예를 들어, 다음 게임판은 x가 이긴 게임판입니다. > 게임은 항상 x부터 시작합니다. > >틱택토 게임판의 현재 상태가 주어집니다. 두 사람 모두...

2020년 1월 21일
·
0개의 댓글

알고리즘 문제해결 전략 Chapter 23 - RUNNINGMEDIAN(C++)

예제: 변화하는 중간값 >한 수열의 중간값(median)은 이 수열을 정렬했을 때 가운데 오는 값입니다. 예를 들어 {3,1,5,4,2}를 정렬했을 때 가운데 오는 값은 3이지요. 수열의 길이가 짝수일 때는 가운데 있는 두 값 중 보다 작은 것을 수열의 중간값이라고 정의하도록 합시다. > >한 수열의 중간값은 수열에 새로운 수가 추가될 때마다 바뀔 수 있습...

2020년 1월 14일
·
0개의 댓글

알고리즘 문제해결 전략 Chapter 08 - SNAIL(C++)

예제: 장마가 찾아왔다 >깊이가 n 미터인 우물의 맨 밑바닥에 달팽이가 있습니다. 이 달팽이는 우물의 맨 위까지 기어올라가고 싶어하는데, 달팽이의 움직임은 그 날의 날씨에 좌우됩니다. 만약 비가 내리면 달팽이는 하루에 2미터를 기어올라갈 수 있지만, 날이 맑으면 1미터밖에 올라가지 못합니다. > >여름 장마가 찾아와, 앞으로 m 일간 각 날짜에 비가 올 확...

2020년 1월 9일
·
0개의 댓글

알고리즘 문제해결 전략 Chapter 21 - TRAVERSAL(C++)

예제: 트리 순회 순서 변경 >트리를 순회하는 알고리즘은 트리의 모든 노드들을 특정 순서에 맞춰 방문하지만, 트리는 배열처럼 1차원적인 구조가 아니기 때문에 단 한 가지의 당연한 순서가 존재하지 않습니다. 때문에 필요에 맞춰 순서를 정의해야 합니다. 이진 트리(binary tree)는 모든 노드에 왼쪽과 오른쪽, 최대 두 개의 자손이 있는 트리를 말하는데,...

2020년 1월 8일
·
1개의 댓글

알고리즘 문제해결 전략 Chapter 08 - TILING2(C++)

예제: 타일링 방법의 수 세기 >2xn 크기의 사각형을 2x1 크기의 사각형으로 빈틈없이 채우는 경우의 수를 구하는 프로그램을 작성하세요. > >예를 들어 n=5라고 하면 다음 그림과 같이 여덟 가지의 방법이 있습니다. (알고스팟 홈페이지에 그림이 없어서, 임의로 3개만 그렸다. 8개 그리기는 귀찮았다!!) > >image.png > >경우의 수는 n이 커...

2020년 1월 8일
·
0개의 댓글

알고리즘 문제해결 전략 Chapter 08 - PI(C++)

예제: 원주율 외우기 >문제 >(주의: 이 문제는 TopCoder 의 번역 문제입니다.) > >가끔 TV 에 보면 원주율을 몇만 자리까지 줄줄 외우는 신동들이 등장하곤 합니다. 이들이 이 수를 외우기 위해 사용하는 방법 중 하나로, 숫자를 몇 자리 이상 끊어 외우는 것이 있습니다. 이들은 숫자를 세 자리에서 다섯 자리까지로 끊어서 외우는데, 가능하면 55...

2020년 1월 6일
·
0개의 댓글

알고리즘 문제해결 전략 Chapter 08 - JLIS(C++)

예제: 합친 LIS >문제 >어떤 수열에서 0개 이상의 숫자를 지운 결과를 원 수열의 부분 수열이라고 부릅니다. 예를 들어 '4 7 6'은 '4 3 7 6 9'의 부분 수열입니다. 중복된 숫자가 없고 오름 차순으로 정렬되어 있는 부분 수열들을 가리켜 증가 부분 수열이라고 부르지요. 예를 들어 '3 6 9'는 앞의 수열의 증가 부분 수열입니다. > >두 개...

2020년 1월 5일
·
0개의 댓글

알고리즘 문제해결 전략 Chapter 20 - PALINDROMIZE(C++)

예제: 팰린드롬 만들기 >문제 >앞에서부터 읽었을 때와 뒤로부터 읽었을 때 똑같은 문자열을 팰린드롬(palindrome)이라고 합니다. 예를 들면 “noon”이나 “stats” 같은 단어들이 팰린드롬입니다. 주어진 문자열 S 뒤에 적절히 문자열을 붙여서 S 를 팰린드롬으로 만들려고 합니다. 예를 들어 S = “anon”이면 뒤에 “ona”를 붙여서 “an...

2020년 1월 5일
·
0개의 댓글

알고리즘 문제해결 전략 Chapter 08 - LIS(C++)

예제: 최대 증가 부분 수열 >문제 >어떤 정수 수열에서 0개 이상의 숫자를 지우면 이 수열의 부분 수열 (subsequence) 를 얻을 수 있다. 예를 들어 10 7 4 9 의 부분 수열에는 7 4 9, 10 4, 10 9 등이 있다. 단, 10 4 7 은 원래 수열의 순서와 다르므로 10 7 4 9 의 부분 수열이 아니다. > >어떤 부분 수열이 순...

2020년 1월 1일
·
0개의 댓글

알고리즘 문제해결 전략 Chapter 20 - NAMING(C++)

예제: 접두사/접미사 >문제 아주대에 사는 외수는 작명에 능하기로 유명해서 많은 부부들이 아주대로 몰려와서 태어나는 아이들의 이름을 지어달라고 한다. 부부들은 이름은 잘 짓는게 출세에 영향을 미친다고 생각을 하고 있으며, 따라서 좋은 이름을 지어 출세하기를 기원한다. 허나 게으른 외수에게 작명은 지루한 작업이다. 효율적으로 일을 하고자 궁리하던 차에 쉽지...

2020년 1월 1일
·
0개의 댓글

알고리즘 문제해결 전략 Chapter 08 - TRIANGLEPATH(C++)

예제: 삼각형 위의 최대 경로 >문제 > >위 형태와 같이 삼각형 모양으로 배치된 자연수들이 있습니다. 맨 위의 숫자에서 시작해, 한 번에 한 칸씩 아래로 내려가 맨 아래 줄로 내려가는 경로를 만들려고 합니다. 경로는 아래 줄로 내려갈 때마다 바로 아래 숫자, 혹은 오른쪽 아래 숫자로 내려갈 수 있습니다. 이 때 모든 경로 중 포함된 숫자의 최대 합을 찾...

2019년 12월 30일
·
0개의 댓글

알고리즘 문제해결 전략 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...

2019년 12월 30일
·
0개의 댓글

알고리즘 문제해결 전략 Chapter 08 - JUMPGAME(C++)

예제: 외발 뛰기 >문제 vue image 땅따먹기를 하다 질린 재하와 영훈이는 땅따먹기의 변종인 새로운 게임을 하기로 했습니다. 이 게임은 그림과 같이 n*n 크기의 격자에 각 1부터 9 사이의 정수를 쓴 상태로 시작합니다. 각 차례인 사람은 맨 왼쪽 윗 칸에서 시작해 외발로 뛰어서 오른쪽 아래 칸으로 내려가야 합니다. 이 때 각 칸에 적혀 있는 숫자만...

2019년 12월 30일
·
0개의 댓글

알고리즘 문제해결 전략 Chapter 18 - JOSEPHUS(C++)

예제: 조세푸스 문제 >문제 1세기에 살던 역사학자 조세푸스는 로마와의 전쟁에서 패해 N - 1명의 동료 병사들과 함께 출구가 없는 동굴에 포위당했다고 합니다. 동료 병사들은 로마에 항복하느니 차라리 자살하자고 결의했고, 포위당한 N명의 사람들이 모두 원형으로 둘러선 뒤 순서대로 자살하기로 했습니다. 한 사람이 자살하면, 다음에는 그 사람으로부터 시계 방...

2019년 12월 30일
·
0개의 댓글