코드first_string = input()second_string = input()h,w = len(first_string), len(second_string)cache = [[0]*(w+1) for _ in range(h+1)]for i in range(1, h+1): for j in range(1, w+1): if first_string[i-1] == second_string[j-1]: cache[i][j] = cache[i-1][j-1]+1 else: cache[i][j] = max(cache[i][j-1], cache[i-1][j])print(cache[-1][-1]) 설명두 개의 string을 2차원 배열로 비교하는 것으로..
자료구조&알고리즘
배경아따 포도주를 저렇게 많이 먹을 수 있는게 부럽다시식이라면 꽁짜겠지 포도주로 취해보고 싶다초록병 이스 마이 라이프 https://www.acmicpc.net/problem/2156 코드n=int(input())drink = []for _ in range(n): drink.append(int(input()))dy=[0]*10001drink.insert(0,0)dy[1] = drink[1]dy[2] = drink[1]+drink[2]dy[3] = max(drink[3]+drink[1], drink[3]+drink[2], dy[2])for i in range(4, n+1): dy[i] = max(dy[i-3]+drink[i]+drink[i-1], drink[i]+dy[i-2], dy[i-1])..
배경 https://www.acmicpc.net/problem/14889 14889번: 스타트와 링크 예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다. www.acmicpc.net 코드 def DFS(L, idx): global res if L==n//2: A=0 B=0 for i in range(n): for j in range(n): if visited[i] and visited[j]: A += board[i][j] elif not visited[i] and not visited[j]: B += board[i][j] res=min(res, abs(A-B)) return for i in ..
배경 https://www.acmicpc.net/problem/2580 2580번: 스도쿠 스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루 www.acmicpc.net 코드 def row(a, n): for i in range(9): if a == sudoku[n][i]: return False return True def colum(a, n): for i in range(9): if a == sudoku[i][n]: return False return True def square(x,y,a): for i in range(3): for j in range(..
배경 https://www.acmicpc.net/problem/9663 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 코드 def attack(x): for i in range(x): if row[x]==row[i]: return True if abs(row[x]-row[i]) == abs(x-i): return True return False def dfs(start): global cnt if start==n: cnt +=1 else: for i in range(n): row[start] = i if not attack..
문제 인프런 저작권 문제 코드 n,m = map(int,input().split()) Line=[] def Count(len): cnt = 1 endpoint = Line[0] for i in range(1, n): if Line[i]-endpoint >= len: cnt +=1 endpoint = Line[i] return cnt for _ in range(n): tmp=int(input()) Line.append(tmp) Line.sort() rt = Line[n-1] lt=1 while lt= m: #배치 할 수 있는 마리 수 res=mid lt=mid+1 else: rt=mid-1 print(res) 접근법 이분 탐색으로 접근해서 가장 좋은 수를 찾는 방법이다 배운 점 이분 탐식 시 lt에 마냥 ..
문제 코드 n = int(input()) ls = [list(map(int,input().split())) for _ in range(n)] lt = rt = n//2 cnt = 0 for i in range(n): for j in range(lt, rt+1): cnt +=ls[i][j] if i < n//2: lt -=1 rt +=1 else: lt +=1 rt -=1 print(cnt) 접근법 List의 진하게 칠해진 부분에 접근 하는 알고리즘이 중요하였다 배운 점 row에 따라 하나 씩 양 옆으로 커져가는 2중 list의 원소에 접근하는 방법을 배웠다.
문제 코드 from itertools import permutations def is_prime(num): if num < 2: return False for i in range(2, int(num**0.5) + 1): if num % i == 0: return False return True def solution(numbers): answer = set() # 가능한 모든 숫자를 생성하여 집합에 추가 for i in range(1, len(numbers) + 1): perms = permutations(numbers, i) for perm in perms: num = int(''.join(perm)) if is_prime(num): answer.add(num) return len(answer) per..
