케이스윔의 개발 블로그

앞으로는 알고리즘문제들을 풀기 전에 이론에 대해서 좀 더 공부하고, 글로도 남겨서 차근차근 정리하려고 한다. 작년에 수강했던 알고리즘수업 때 필기와 인터넷 자료, 알고리즘 문제해결전략 책을 종합해서 공책에 필기로도 남기고 블로그에 글도 남길 것이다. 앞서서 공부했던 다이나믹프로그래밍, DFS, BFS에 대해서도 다시 정리를 하고 글로 남길 예정이다. 어제부터 다시 공부하기 시작한 알고리즘 분류는 Backtracking(백트래킹)이다. '백트래킹이란 무엇이다'라고 확실히 정의를 내리기는 어렵지만, 백트래킹은 가능한 모든 조합에 대해 전부 시도를 하는 것이다. 이 말을 자세히 다시 살펴보면 '가능한 모든 조합'이기 때문에 조건에 맞을 경우에 전부 시도를 한다. 알고리즘 교수님께서 해주신 필기에는 "DFS w..

문제 정의알파벳으로 이루어진 N개의 단어가 수학문제가 들어오면, 각 알파벳을 숫자에 대응시켜 합을 구했을 때 가장 큰 합이 나오도록 만들어야 한다.문제 출처: 백준 온라인 저지(https://www.acmicpc.net/problem/1339) 문제 풀이숫자는 0~9 까지 각 알파벳에 대응시킬 수 있으므로, 최대 대응을 시켜야하는 수는 10개의 알파벳이다.(입력자체도 모든 단어에 포함되어 있는 알파벳이 최대 10개이다.) 두줄에 걸쳐 입력되는 알파벳숫자들의 합이 최대가 되려면 일단 제일 앞자리에 있는 알파벳에 9,8,7... 순으로 큰 수를 대응시켜주면 된다. 문제는 하나의 알파벳이 두번 입력되어도 그 알파벳은 하나의 수로 대응되어야하니까 적절하게 대응시킬 수 있는 방법이 필요하다. 해결해야되는 부분들을..

문제 정의4종류의 사탕으로 이루어진 n*n에서 임의의 인접한 두 칸을 골라서 사탕을 교환한 후, 모두 같은 색으로 이루어져 있는 가장 긴 연속 부분을 고른다. 상근이가 먹을 수 있는 사탕의 최대 개수를 구해야 한다.문제 출처: 백준 온라인 저지(https://www.acmicpc.net/problem/3085) 문제 풀이인접한 두 칸을 골랐을 때, 가장 긴 연속부분이 될 수 있도록 만들어야 한다. 긴 연속부분을 찾을 때는 하나의 알파벳에 대해서 DFS를 하면 될 것 같은데 임의의 두 칸을 어떻게 바꿔야 할지 고민된다. 굳이 바꿀필요 없이 모든 좌표에 대해서 DFS를 하고, 만약 막혀서 더이상 못한다면 그 자리와 인접한 칸에 사탕이 이어지는지를 판단해서 가능하면 그 칸을 바꾼다 생각하고 시도해본다. DFS..

문제 정의 어떤 자연수 N이 있을 때, 그 자연수의 분해합은 N과 N을 이루는 각 자리수의 합을 의미한다. 어떤 자연수 M의 분해합이 N인 경우, M을 N의 생성자라 한다. 예를 들면 245의 분해합은 245+2+4+5=256이되고, 256의 생성자는 245가 된다. N이 주어졌을 때 가장 작은 생성자를 구해내는 프로그램을 작성해야한다. 문제 출처: 백준 온라인 저지(https://www.acmicpc.net/problem/2231) 문제 풀이어떤 수를 분해시켜 N과 N을 이루는 각 자리수의 합을 계산했을 때, 입력한 숫자가 나와야하고 그 어떤 수 중에서 가장 작은 수를 구해야한다. 만약 주어진 자연수 N을 만들기 위해서 모든 수를 다 분해합 시킨다고 생각하면, 1,000,000을 만들기 위해서는 약 9..

문제 정의총 9명 난장이들의 키가 주어지면 이들의 합이 100이 되는 일곱명의 난장이를 찾는 문제이다.문제 출처: 백준 온라인 저지(https://www.acmicpc.net/problem/2309) 문제 풀이입력되는 수는 항상 9개의 숫자이다. 이 숫자들의 합으로 100을 만들 수 있으면 탐색이 끝난다. N이 작기때문에 모든 경우를 다 계산해보는 완전탐색으로도 해결할 수 있는 문제이다. 9개의 숫자 중 7개의 숫자를 골라서 계산을 해보아야한다. 9개의 숫자 중에서 7개의 숫자를 어떻게 고를지 생각을 해봐야 한다.사실 첫번째 생각부터 막혀서 9명 중에 어떻게 7명을 고르지 생각하다가 푼 사람의 리뷰를 봤는데 틀린 사람을 제거하면 되니까 9명 중에 제거를 할 2명을 고르면 된다. 9명 중에서 2명을 고르는..

문제 정의평소에 일반적으로 푸는 스도쿠와 같은 문제이다. 채워지지 않은 칸은 0으로 주어지면 모든 빈 칸이 채워진 스도쿠의 최종 모습을 출력하는 문제이다. 스도쿠에서 각각 세로와 가로 한줄씩은 1~9의 숫자가 하나씩 들어가야하고, 3*3의 칸으로 나눈 총 9개의 3*3 정사각형 안에서도 1~9의 숫자는 하나씩 존재해야한다.문제 출처: 백준 온라인 저지(https://www.acmicpc.net/problem/2580) 문제 풀이빈칸이 발견될 때마다 백트래킹 함수를 호출해서 빈칸에 알맞는 숫자를 찾아야 한다. 만족해야하는 조건은 3가지이므로 차례대로 체크를 하고 만약 조건에 만족하지 못할경우 다시 돌아가서 새로운 수를 채워넣고 다시 조건을 검사한다. 즉, 채우는 수는 1~9 로 차례대로 시도하고 가로, 세..

문제숫자 1, 2, 3으로만 이루어지는 수열이 있다. 임의의 길이의 인접한 두 개의 부분 수열이 동일한 것이 있으면, 그 수열을 나쁜 수열이라고 부른다. 그렇지 않은 수열은 좋은 수열이다.다음은 나쁜 수열의 예이다.3332121323123123213다음은 좋은 수열의 예이다.232321231232123길이가 N인 좋은 수열들을 N자리의 정수로 보아 그중 가장 작은 수를 나타내는 수열을 구하는 프로그램을 작성하라. 예를 들면, 1213121과 2123212는 모두 좋은 수열이지만 그 중에서 작은 수를 나타내는 수열 1213121이다. 입력과 출력 입력은 숫자 N하나로 이루어진다. (1

문제세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다.말은 상하좌우로 인접한 네 칸 중의 한 칸으로 이동할 수 있는데, 새로 이동한 칸에 적혀 있는 알파벳은 지금까지 지나온 모든 칸에 적혀 있는 알파벳과는 달라야 한다. 즉, 같은 알파벳이 적힌 칸을 두 번 지날 수 없다.좌측 상단에서 시작해서, 말이 최대한 몇 칸을 지날 수 있는지를 구하는 프로그램을 작성하시오. 말이 지나는 칸은 좌측 상단의 칸도 포함된다.문제 출처: 백준 온라인 저지(https://www.acmicpc.net/problem/1987) 입력과 출력첫째 줄에 R과 C가 빈칸을 사이에 두고 주어진다. (1= C) continue; ..