이지코딩

문제가 어렵지는 않지만, 나름 함정이라고 생각 할 만한 여지가 있어 몇번 틀렸다. 두 터렛이 적의 위치를 계산 한 값은 같은 위치여야 하는거 아닌가.... 하는 생각에 틀렸었다. 두 터렛이 계산한 적의 위치가 각각 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..

바이토닉 부분 수열이란, 수열 S가 어떤 수 Sk를 기준으로 S1 Sk+1 > ... SN-1 > SN을 만족 하는 수열이다. 예를 들면 {10, 20, 30, 10} 은 30을 기준으로 위 식을 만족하기에 바이토닉 부분수열 이라고 할 수 있지만, {10, 20, 30, 10, 20}은 20으로 인해 바이토닉 부분 수열이 아니다. 자 이제 가장 긴 바이토닉 부분 수열을 찾기 위한 작업을 알아보자. 가장 긴 바이토닉 부분 수열을 찾기 위해서는 첫번째, 자기 자신까지 증가하는 가장 긴 증가수열의 길이. 두번째,자기 자신부터 감소하는 가장 긴 감소수열의 길이. 를 알아야 할 것이다. 이를 모두 구한 후, 자기 자신이 중복 되므로, 두 수열의 길이의 합에서 1을 빼주면 ..