이지코딩

dp 문제에서 찾기 힘든 낮은 랭크의 문제. 초콜릿 자르기다. n*m인 초콜릿을 1*1 로 모두 자르는데 몇번을 쪼개야 하는지를 묻고 있다. 최소한으로 쪼개는 것이지만, 한번에 길게 자르는것을 생각하면 n*m 과 m*n 은 항상 같은 횟수를 가지게 된다. dp문제를 풀때 첫번째로 해야하는것. 초기값 설정이다. 이 문제에서 초기값은 1*m 또는 m*1 크기의 초콜릿을 자르는 횟수가 될것 이고, 이는 m-1회 일것이다. 이후 해야 하는것. 점화식 세우기. 3*3을 생각해보면 아래 그림처럼 나눌수 있을 것이다. 이렇게 잘라보면, 3*1 조각과 3*2 를 각각 최소한으로 자르는 횟수 +1 이 될것이다. dp[n][m]이 n*m을 최소한으로 자르는 횟수라고 가정하면, dp[n][m] = 1+dp[n][1] +dp..

dp를 푸는데 가장 중요한건 두개인 것 같다. 첫번째는 초기값 설정, 두번째는 점화식 세우기... 처음 이 문제를 풀때는 초기값과 점화식이 정확하지 않아 중복이 일어나는 현상이 일어났다... 문제는 중복값을 제거 해주는 숫자가 뭔가.. 규칙성이 없었다는것.... 그때 빨리 포기 하고 다른 방법을 찾았어야 하는데 뭔가 될듯 말듯 한 느낌에 붙들고 있다가 포기하고 찬찬히 보니 경우 규칙이 보였다. 처음 이 문제를 푸는 사람도 비슷할 것이라고 생각한다. 중복 제거 문제.... 오늘 또 한가지를 배웠다. 중복이 일정한 규칙이 없는것 같으면, 분명히 다른 방법이 있을 것이다..... 본론으로 돌아와서! 문제를 처음 읽었을때, "경우의 수"를 구하라는 것이 먼저 보인다. 그 말인 즉슨, dp 배열에 값이 아닌, 경..

문제가 어렵지는 않지만, 나름 함정이라고 생각 할 만한 여지가 있어 몇번 틀렸다. 두 터렛이 적의 위치를 계산 한 값은 같은 위치여야 하는거 아닌가.... 하는 생각에 틀렸었다. 두 터렛이 계산한 적의 위치가 각각 r1,r2 이므로, 각 x,y 좌표를 중심으로 한 두 원을 만들 수 있고, 조건에 따라 나눌 수 있다. 중심이 같을 경우. 1.1) r1 == r2 1.2) r1 != r2 중심이 다를 경우. 2.1) 큰 원 안에 작은 원의 중심이 포함 될 경우 2.2) 큰 원 밖에 작은 원의 중심이 있을 경우 그리고, 2번의 경우는 다시 세부적으로 나뉠 수 있다. 2.1 에서 각각 내접, 작은 원이 큰 원안에 완전히 귀속, 두 점이 만날 경우. 2.2 에서 외접, 안만날 경우, 두 점에서 만날 경우. 위 조..

문자열 처리는 역시 파이썬이 쉽다.... 갓이썬..... 1 2 3 4 arr = ["black","brown","red", "orange", "yellow", "green", "blue", "violet", "grey", "white"] res = [] for i in range(3): res.append(arr.index(input())) print(int(str(res[0])+str(res[1]))*(10**res[2])) http://colorscripter.com/info#e" target="_blank" style="color:#e5e5e5text-decoration:none">Colored by Color Scripter 문제 : https://www.acmicpc.net/problem/10..

N과 K가 주어졌을때, 0~N의 자연수를 중복선택 포함하여 K개 선택후, 합이 N이 되는 경우의 수를 구하는 문제이다. 즉, N = 2, K = 3 일 경우에는 (0,0,2), (0,1,1), (0,2,0), (1,0,1), (1,1,0), (2,0,0) 총 6개가 가능하다. 규칙을 찾기 위해 먼저 1개 선택시 부터 3개 선택시 N을 만들기 위한 경우의 수를 계산 해 보았으나, 3개 선택시 부터는 등차수열의 합에 대한 공식 들이 튀어나오면서... 수학같은 문제가 될 뻔 했으나, 컴퓨터 답게 푸는 방법은 아닌것 같아 패스.... 좀더 생각해 보니, N = 2, K = 2 일때, (0,2) 는 N=0, K=1 일때 N=2, K=1 일때 각 경우의 수의 곱과 같다. 즉, 앞의 계산값에 영향을 받는다.. 흠....

LCS (Longest Common Subsequence)알고리즘이다. 문자열을 쉽게 처리하기 위하여 python으로 코드를 구성하였다. 최장 공통 부분 수열 문제는, 두 수열에서 공통이 되는 가장 긴 수열을 찾아내는 문제이다. ACAYKP 와 CAPCAK 의 LCS는 ACAK가 될것 이다. 이 알고리즘을 이해하기 위해서 표를 그려보자면, 아래와 같다. 서로 같은 문자가 나올 경우, 대각선 위에서 점수를 더해준다. 서로 다른 문자가 나올 경우, 위와 왼쪽에서 큰 수를 가진다. 즉, (_str1[j-1] == _str2[i-1]) -> arr[i][j] = arr[i-1][j-1]+1 (_str1[j-1] != _str2[i-1]) -> max(arr[i-1][j], arr[i][j-1]) 이다. 1 2 ..

전신주 사이에 전선이 겹치지 않게 하려면 A전신주의 번호가 증가 할 때, 각 번호에 연결된 B전신주의 번호가 계속 증가해야 한다. A전신주의 1번을 보았을때, 1번은 8번과 연결 되있는데, 2번은 2와 연결 되어있으므로, 전깃줄이 교차하지만, 3번은 9번과 연결되어 겹치치 않는다. 이렇게 A 전신주 기준으로 각 번호에 연결된 B전신주의 번호가 증가하는 LIS를 찾는 문제이다. 또한, A전신주의 각 번호에 따라 LIS 가 작아지면 의미가 없기때문에 계속 큰 수를 업데이트 해야하기에 DP또한 사용된다. 위 설명을 표로 보면 아래와 같다. 최대 연결 개수는 같은 번호의 LIS 와 바로 전 최대 연결 개수의 최대값이다. 즉, res[n] = max(res[n-1], LIS[n]) 1 2 3 4 5 6 7 8 9..

문제의 입력이 정수들을 삼각형 형태로 받는 모양이라 2차원 배열로 받으려 했으나, 500층을 생각 하면, 맨 윗층은 정수가 1개 인데 500개의 int형 메모리를 할당하기 아까워서 1차원 배열로 해결해 보려 했으나... 너무 코드만 길어지기에 처음 생각했던 방식으로 해결 하였다. 맨 위의 3층만 예시로 살펴보자. 맨 위에부터 0층, 1층, 2층 이라고 하면, 각 층의 가장 왼쪽 정수는 윗층의 가장 왼쪽 정수만 더할 수 있고, 가장 오른쪽 정수 또한 윗 층의 가장 오른쪽 정수만 더 할 수 있다. 나머지 정수들은 윗층의 두 수에서 좀 더 큰 수만을 선택하면 된다. "층"을 표현하기 위해서는 이차원 배열이 가장 쉬워 사용하였다. 이 것을 점화식을 표현하면, if(j==0) : dp[i][j] += dp[i-1..