아이테킨의 끄적끄적

n = int(input()) li = list(map(int,input().split())) #증가하는 수열 - LIS dp = li[:] for i in range(n): for j in range(i): if li[i] > li[j]: dp[i] = max(dp[i],dp[j]+li[i]) print(max(dp)) 11054번에서 만든 증가하는 부분수열 구하는 알고리즘에서 부분수열의 개수를 구하는 것이 아니라 부분수열의 합을 구해서 dp리스트에 업데이트를 해주면 된다. 아래 코드는 증가하는 부분수열의 개수를 구하는 알고리즘이다. 비교를 해보면 위의 dp[j]+li[i]는 부분수열의 합을 구하기 위한 계산이고 dp[j]+1은 부분수열의 개수를 구하기 위한 계산이다. n = int(input()) l..

LCS는 임의의 두 문자열에서 가장 긴 subsequence의 길이를 구하는 문제다. 처음 접해보는 개념이라 2시간정도 혼자서 고민하다가 다른 사람의 정리된 블로그를 보면서 이해하였다. 이미 만들어 놓은 결과위에 새로운 문제들을 이어서 푼다는 DP의 특징을 기억하고 있을 필요가 있다. 위의 표에서 (2,3), (2,6), (3,2), (3,5), (4,3), (4,6), (6,7)은 모두 행과 열의 문자가 같다. 이렇게 행과 열의 문자가 같은 셀의 값은 왼쪽 대각선 위에 있는 수에서 1을 더한 값이 되는 규칙을 찾을 수 있다. 1. 각각의 문자열에서 가장 최근에 추가된 문자가 같을 경우 왼쪽 대각선 위의 셀에서 각각 같은 문자열이 추가되었으므로 +1을 해준다. 예) (3,5)셀 : CAP와 A에서 C가 ..

조합 공식을 이용해서 풀 수 있는 문제였다. 고등학교때 이후로 머리속에서 꺼내보지 않았던 개념이라 인터넷으로 다시 조합공식을 찾아보기도 했다....하핳 펙토리얼(fac)함수를 정의하고 정의한 함수를 이용해서 조합 공식을 만들어서 풀었다. # 1010번 : 다리놓기 # 조합(Combination)공식을 이용해서 쉽게 풀 수 있다. t = int(input()) def fac(n): num = 1 for i in range(1,n+1): num *= i return num for _ in range(t): m,n = map(int,input().split()) bridge = fac(n) // (fac(m)*fac(n-m)) print(bridge)

입력값만큼 키가 큰 사람을 앞에 두고 줄을 세우는 문제이다. 왼쪽부터 숫자 0의 개수를 기준으로 위치를 찾아 줄을 세우면 된다. 예를 들어 2,1,1,0 이면 [0,0,1,0] -> 0을 2개 지나친 이후 1 위치 [0,2,1,0] -> 0을 1개 지나친 이후 2 위치 [0,2,1,3] -> 0을 1개 지나친 이후 3 위치 [4,2,1,3] -> 0을 0개 지나친 이후 4 위치 # 1138번 : 한 줄로 서기 n = int(input()) li = list(map(int,input().split())) ans = [ 0 for i in range(n)] for i in range(n): cnt = 0 for j in range(n): if cnt == li[i] and ans[j] == 0: ans[j]..

DFS알고리즘을 알고 있어야 풀 수 있는 문제다. R,C로 행과 열의 값 pipe에 파이프라인 visited에 파이프가 이미 설치되어 있는 곳인지 확인하기 위해 False로 초기화 리스트 이런 변수들을 입력 및 선언하고 왼쪽부터 시작해서 맨 오른쪽이 원웅이네 가게 파이프라인까지 최대한 많은 선을 연결해야 하므로 첫번째 열 에서 파이프라인이 있는 지점 pipe[i][0] == '.' 에서 부터 탐색을 시작한다. solve함수를 호출하여 건물이 있는 지점을 피하며 오른쪽으로 이동하고, 방문했던 지점은 True로 흔적을 남긴다. solve함수 종료조건인 j == C - 1 까지 도착하게 되면 True를 반환하여 cnt를 증가시킨다. # 3109번 : 빵집 def solve(i,j): # 원웅이네 파이프로 무사..

문제를 풀기위해 생각해낸 방법은 "테이프로 막은 부분을 표시해두자" 이다. 표시를 하기 위해서 사용한 방법은 리스트를 넉넉한 크기로 만들어준 뒤 테이프로 막은 부분은 1로 표시하는 것이다. 그래서 변수 명도 flag 로 정했다. (항상 변수명을 정할 때 가장 고민을 많이 하는 것 같다...ㅎㅎ) # 1449번: 수리공 항승 N,L = map(int,input().split()) tape = list(map(int,input().split())) tape.sort() flag = [0 for i in range(10000)] cnt = 0 for i in tape: if flag[i] == 0: cnt += 1 for j in range(L): flag[i+j] = 1 print(cnt)

# 1543번: 문서 검색 doc = input() word = input() length = len(word) flag = [0 for i in range(len(doc))] cnt = 0 for i in range(len(doc)): if flag[i] == 1: continue if word == doc[i:i+length]: cnt += 1 for idx in range(i,i+length): flag[idx] = 1 print(cnt) 중복 값을 어떻게 처리하면 좋을지 생각하다가 리스트를 사용해서 한번 본 문자의 인덱스에 표시를 해두는 것으로 구현해보았다. 다행히 한 번에 통과가 되었다. 그런데 이번 문제를 풀면서 새롭게 알게 된 부분은 리스트 슬라이스 작업에는 index out of range..

피보나치 수열을 구하는 대표적은 다이나믹 프로그래밍 문제이다. 그러나 이번 문제는 단순히 문제를 해결하는 것 뿐만 아니라 더 빨리 효율적으로 풀 수 있는 알고리즘을 물어보고 있다. 문제의 답은 반복문 또는 메모이제이션을 이용해서 풀면 된다. (메모이제이션을 이용한 코드는 아래 있다.) # 반복문으로 푼 피보나치 n = int(input()) dp = [0]*100 dp[1] = 1 for i in range(2,n+1): dp[i] = dp[i-1] + dp[i-2] print(dp[n]) 이번 기회에 피보나치 수열을 구하는데 사용되는 3가지 방법에 대해서 정리해보았다. 반복문, 재귀, 메모이제이션 총 세가지 방법으로 피보나치 수열을 풀 수 있지만 각각 시간복잡도, 메모리를 사용하는 정도가 다르다. 1...

다이나믹 프로그래밍 문제는 점화식을 풀어서 해결해야 하는 경우가 많다는 것을 기억하자. 이 문제도 점화식을 사용해보면 해결할 수 있다. i번째 포도주를 시음한다고 하면 생각할 수 있는 경우의 수는 1. i-2번째 포도주를 마신 경우 2. i-3번째 i-1번째 포도주를 마신 경우 또한 i번째 포도주를 마시지 았았을 경우 생각할 수 있는 경우의 수는 3. i-1번째 포도주를 마신 경우이다. 이 세가지 경우의 수 에서 가장 큰 값을 출력해내면 된다. 이를 점화식으로 표현해보면 dp[i] = max(dp[i-2]+w[i], dp[i-3]+w[i-1]+w[i], dp[i-1]) # 2156번: 포도주 시식 # dp문제는 점화식을 만들어봐야 한다. # 다시 풀어보기!! 아 실력이 안느냐 왜 ㅠㅠ n = int(in..

그리디문제로 나는 행렬이 들어가기만 하면 어렵다 ㅠㅠ # 1080번: 행렬 # 다시풀기 n,m = map(int,input().split()) graph1 = [] graph2 = [] cnt = 0 def convertgraph(i,j): for x in range(i,i+3): for y in range(j,j+3): graph1[x][y] = 1- graph1[x][y] for i in range(n): graph1.append(list(map(int,input()))) for i in range(n): graph2.append(list(map(int,input()))) for i in range(n-2): for j in range(m-2): if graph1[i][j] != graph2[i][j..