electronicprogrammer

문제 : www.acmicpc.net/problem/2580 2580번: 스도쿠 스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루 www.acmicpc.net 문제는 다음과 같습니다. 문제의 핵심은 스도쿠에서 몇 칸이 0으로 변경된 입력이 주어지면 해당 입력을 적절한 값으로 채워서 스도쿠를 완성하는 것입니다. 여기서 스도쿠가 만들어질 수 있는 경우만 입력이 되므로 저희는 백트랙킹 즉 모든 경우를 하나하나 검사하면서 경우를 충족하지 못하면 해당 경우를 삭제하도록 하는 방법을 생각해볼 수 있습니다. 경우를 삭제하는 것은 스도쿠의 규칙 , 열, 행 그리고 주위 구..

문제 : www.acmicpc.net/problem/16197 16197번: 두 동전 N×M 크기의 보드와 4개의 버튼으로 이루어진 게임이 있다. 보드는 1×1크기의 정사각형 칸으로 나누어져 있고, 각각의 칸은 비어있거나, 벽이다. 두 개의 빈 칸에는 동전이 하나씩 놓여져 있고, www.acmicpc.net 문제는 다음과 같습니다. 핵심은 2개의 동전은 같이 이동하면서 1개의 동전만이 배열에 남아있어야 문제의 조건이 만족하며 이러한 경우 중에서 최솟값을 구해야 한다는 것입니다. 또한 10번 이하에 문제의 조건을 충족하지 못하면 -1을 출력해야 합니다. 이동가능한 경우가 상, 화 , 좌 , 우 이고 2개의 동전이 같이 이동하므로 가능한 모든 경우를 파악하면서 이동하는 각각의 경우에 대해서 이동 횟수를 기록..

문제 : www.acmicpc.net/problem/14888 14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, www.acmicpc.net 문제는 다음과 같습니다. 문제에서 요구하는 것은 주어진 수에서 연산자의 위치를 변경함으로써 얻을 수 있는 최대 최소 값을 구하는 것입니다. 핵심은 수는 고정이 되어있고 연산자의 위치를 변경하는 것입니다. 따라서 저희는 연산자가 주어지면 이에 대한 갯수를 파악해서 인덱스를 기준으로 순열을 진행하겠습니다. 그렇게 되면 저희는 연산자의 위치를 변경하면서..

문제 : www.acmicpc.net/problem/14500 14500번: 테트로미노 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변 www.acmicpc.net 문제는 다음과 같습니다. 문제에서 요구하는 것은 주어진 배열에서 어떠한 테트로미노를 1개만 설치하였을 때 가장 큰 값을 가지는가 입니다. 먼저 모든 테트로미노를 좌우 및 상하로 회전한 모든 경우를 배열에서 검사하기에는 코드가 너무 복잡하고 힘들 것 같습니다. 여기서 아래의 테트로미노를 제외하면 테트로미노를 상하좌우 회전 및 뒤집은 경우를 생각하면 그냥 상, 하 , 좌 , 우 로 1칸씩 이동하는 모든 경..

문제 : www.acmicpc.net/problem/1339 1339번: 단어 수학 첫째 줄에 단어의 개수 N(1 ≤ N ≤ 10)이 주어진다. 둘째 줄부터 N개의 줄에 단어가 한 줄에 하나씩 주어진다. 단어는 알파벳 대문자로만 이루어져있다. 모든 단어에 포함되어 있는 알파벳은 최대 www.acmicpc.net 문제는 다음과 같습니다. 문제에서 요구하는 것은 대문자 알파벳으로 이루어진 문자열의 갯수가 주어지면 알파벳을 0에서 9 사이의 값으로 설정해서 더한 값에서 최댓값을 구하는 것입니다. 여기서 입력의 조건을 보시면 모든 단어에 포함되어 있는 알파벳은 최대 10개로 하였으므로 저희는 주어진 알파벳을 0 ~ 9 사이로 중복없이 배정하고 값을 더해주면 됩니다. 따라서 순열을 이용해서 구현해보도록 하겠습니다..

문제 : www.acmicpc.net/problem/1182 1182번: 부분수열의 합 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net 문제는 다음과 같습니다. 문제의 조건은 주어진 수열에서 부분 수열을 뽑아서 합이 S가 되는 경우를 모두 찾는 것입니다. 모든 경우를 검사하는 것으로 제귀적인 방법을 이용해서 구현을 해보았습니다. 경우는 해당 수를 선택하는가? , 선택하지 않는가? 로 2가지로 나누어서 진행을 하며 합이 S가 되면 경우를 증가시키도록 하였습니다. 전체적인 코드는 다음과 같습니다. imp..

문제 주소 : www.acmicpc.net/problem/11066 11066번: 파일 합치기 소설가인 김대전은 소설을 여러 장(chapter)으로 나누어 쓰는데, 각 장은 각각 다른 파일에 저장하곤 한다. 소설의 모든 장을 쓰고 나서는 각 장이 쓰여진 파일을 합쳐서 최종적으로 소설의 완성본 www.acmicpc.net 문제는 다음과 같습니다. 문제에서 구하고자 하는 것은 각 케이스에 따라서 한 행을 출력하는데 모든 장을 합치는데 필요한 최소 비용을 구하고자 하는 것입니다. 문제의 방향은 다음과 같습니다. 먼저 전체 파일을 비용을 합치는데 있어서 다양한 경우가 존재한다는 것을 예시를 통해서 파악을 할 수 있었습니다. 근데 여기서 전체경우를 알아보는 브루트포스를 이용해서 최소비용을 탐색한다면 문제의 시간제..

www.acmicpc.net/problem/2293 2293번: 동전 1 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. www.acmicpc.net 문제는 다음과 같습니다. 문제의 목표는 문제의 조건에 맞는 경우의 수가 얼마나 되는가에 대해서 구하는 것입니다. 여기에다가 시간 제한이 매우 적으니 메모리제이션을 활용해서 동적계획법으로 구현을 해보겠습니다. 방향은 다음과 같습니다. 정리하자면 각각의 코인을 이용해서 만들 수 있는 경우를 계산한는데 다음 코인의 경우를 파악할 때는 이전 경우에서 시작함으로써 코인들의 조합들도 알아서 따질 수 있도록 해줍니다. 전체적..

문제 : www.acmicpc.net/problem/1987 1987번: 알파벳 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으 www.acmicpc.net 이번 포스팅에서는 백준 알고리즘에 있는 1987 문제 , 알파벳 문제에 대해서 풀어보고 과정을 정리해보도록 하겠습니다. 먼저 문제 내용입니다. 목표는 왼쪽 위 에서의 시작점에서 최대한 얼마나 이동할 수 있는지입니다. 또한 제한 조건은 같은 알파벳의 칸으로는 이동이 불가하다는 것입니다. 저는 이 문제를 제귀를 이용하여서 특히 백트랙킹을 이용하서 풀었는데 그 이유는 다음과 같습니다. 문제에서 이동할..

먼저 matplotlib을 이용해서 2개의 그래프를 동시에 그려보겠습니다. plt.figure(figsize=(18,10)) plt.title('Price Prediction & Real Comparison' , fontsize=20) plt.ylabel('Price Scaled' , fontsize=15) plt.xlabel('Index' , fontsize=15) plt.plot(idx_List , Y_test , color = 'blue' , alpha=0.5 , label = 'Real Price') plt.plot(idx_List , preds , color = 'red' , alpha=0.5 , label = 'Predicted Price') plt.legend(fontsize=15) plt...