![]()
문제 https://www.acmicpc.net/problem/17136 17136번: 색종이 붙이기 과 같이 정사각형 모양을 한 다섯 종류의 색종이가 있다. 색종이의 크기는 1×1, 2×2, 3×3, 4×4, 5×5로 총 다섯 종류가 있으며, 각 종류의 색종이는 5개씩 가지고 있다. 색종이를 크 www.acmicpc.net 문제 풀이 모든 좌표에 대해서 종이를 계속 바꿔가면서 붙이고, 최소한의 종이 개수를 구하면 될 것이라고 판단했다. 이유는 배열의 크기가 그렇게 크지 않다. 10*10이므로 n^2이더라도 넉넉하다고 생각했다. 종이의 종류가 많지 않다. 즉 하나의 좌표에서 종이의 종류대로 붙여가면서 확인을 하더라도 크게 시간이 오래 걸리지 않을 것 같았다. 따라서 나는 종이가 들어갈 수 있는 좌표에 대..
![]()
문제 https://www.acmicpc.net/problem/1062 1062번: 가르침 첫째 줄에 단어의 개수 N과 K가 주어진다. N은 50보다 작거나 같은 자연수이고, K는 26보다 작거나 같은 자연수 또는 0이다. 둘째 줄부터 N개의 줄에 남극 언어의 단어가 주어진다. 단어는 영어 소문 www.acmicpc.net 문제 풀이 최적화에 신경 쓰지 않는다면 엄청난 시간초과를 맛볼 수 있는 문제이다. 최대한 경우의 수를 줄여서 최소한의 탐색으로 해결해야 한다. 학생들은 K개의 글자를 배우고, K개의 글자로 이루어진 단어만 읽을 수 있다. 즉 우리는 N개의 단어 중에서 K개의 글자를 골라서 주어진 N개의 단어들 중에서 최대한 많이 읽어야 한다. 문제에서는 친절하게 반드시 배워야 할 글자들을 제시해 준다..
![]()
문제 https://www.acmicpc.net/problem/2661 2661번: 좋은수열 첫 번째 줄에 1, 2, 3으로만 이루어져 있는 길이가 N인 좋은 수열들 중에서 가장 작은 수를 나타내는 수열만 출력한다. 수열을 이루는 1, 2, 3들 사이에는 빈칸을 두지 않는다. www.acmicpc.net 문제 풀이 전형적인 백트래킹 문제의 예시라고 할 수 있다. 백트래킹에 대해 간단히 얘기하자면 사전적 정의는 되추적 알고리즘이라고 불린다. 결과를 찾는 도중 막히면 다시 되돌아가서 결과를 찾고, 모든 노드를 탐색해서 만드는 DFS와 비슷하다. DFS와 다른 점은 노드를 탐색하기 전에 특정한 조건을 걸고 해당 조건에 부합하지 않는다면 탐색을 진행하지 않는다. 해당 문제에서 특정한 조건이 이제 인접한 두 개의..
![]()
문제 2580번: 스도쿠 스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루 www.acmicpc.net 🔎문제 해석 해당 칸에서 숫자를 넣고, 가로줄, 세로줄, 3*3 사각형 범위 검사를 해서 통과하면 다음 단계를 진행하는 문제이다. 만약 막혔다면 이전단계에서 다른 숫자를 선택하는 백트래킹 알고리즘을 사용하면 된다. 해당 좌표에서 포함되는 사각형의 범위는 어떻게 구하면 될까? 만약 x, y 좌표가 0,0이라면 사각형은 첫 번째 범위일 것이다. 가로 범위에서 3개의 구분이 있고, 세로 범위에서 3개의 구분이 있다. 따라서 (x좌표 /3 , y좌표/3)이 해당 ..
![]()
문제 두 종류의 부등호 기호 ‘’가 k개 나열된 순서열 A가 있다. 우리는 이 부등호 기호 앞뒤에 서로 다른 한 자릿수 숫자를 넣어서 모든 부등호 관계를 만족시키려고 한다. 예를 들어, 제시된 부등호 순서열 A가 다음과 같다고 하자. A ⇒ 부등호 기호 앞뒤에 넣을 수 있는 숫자는 0부터 9까지의 정수이며 선택된 숫자는 모두 달라야 한다. 아래는 부등호 순서열 A를 만족시키는 한 예이다. 3 1 7 0 이 상황에서 부등호 기호를 제거한 뒤, 숫자를 모두 붙이면 하나의 수를 만들 수 있는데 이 수를 주어진 부등호 관계를 만족시키는 정수라고 한다. 그런데 주어진 부등호 관계를 만족하는 정수는 하나 이상 존재한다. 예를 들어..
![]()
문제 교재와 강의자료를 참고하여 0-1 배낭 문제를 해결하는 Algorithm 5.7을 완성하시오. 단, 문제의 입력은 단위무게당 이익순으로 정렬되어 있지 않음에 유의하시오. 또한, 알고리즘의 출력은 알고리즘의 실행 단계별로 상태 공간 트리의 각 노드에서의 상태를 출력해야 함에 주의하시오. 입력 첫번째 줄에 아이템의 개수 n과 배낭의 무게 W가 주어진다. 두 번째 줄에 n개의 아이템 무게 w [i]가 주어진다. 세 번째 줄에 n개의 아이템 이익 p [i]가 주어진다. 출력 첫 번째 줄부터 한 줄에 하나씩 상태공간트리를 방문하는 노드의 상태를 출력하시오. 노드 상태는 다음과 같은 순서로 출력한다. i weight profit bound maxprofit 상태를 출력하는 순서는 Algorithm 5.7의 노..
