나만의 개발블로그

dictionary로 연결된 컴퓨터의 종류를 추가 후 방문했는지를 visit로 체크하며 방문하지 않았다면 결과에 +1하는 형식으로 문제 해결 import sys from collections import deque input = sys.stdin.readline com = int(input()) dic = {i:[] for i in range(1, com+1)} visit = [0]*(com+1) visit[1] = 1 result = 0 for _ in range(int(input())): s,e = map(int,input().split()) dic[s].append(e) dic[e].append(s) q = deque([1]) while q: s = q.popleft() for i in dic[s]..

코드는 빨리 작성이 되었는데 계속 시간 초과가 발생해서 찾아본 결과... BFS는 `원소를 넣기 전에 방문 처리를 해야 한다`라는 것을 확인 후 회로를 돌려보니 맞는 말이었다. 예를 들어 아래와 같은 미로가 있다고 했을 때 11 11 q를 통해 (0,0)부터 넣게 된다면 0,0 = [ [1, 0], [0, 1] ] 1,0 = [ [0, 1], [1, 1] ] 0,1 = [ [1, 1], [1, 1] ] 위와 같이 되는데 이 때 0,1의 경우에 보면 [1,1] 방문 처리를 미리하지 않았기에 중복으로 들어가게 되는 것을 확인할 수 있다. 이유는 한 길로만 쭉 가는게 아니라 갈 수 있는 곳은 다 탐색하면서 가기에 그렇다. import sys from collections import deque input = ..

냅색 알고리즘은 배낭에 담을 수 있는 무게의 최댓값이 정해지고, 일정 가치와 무게를 가진 짐을 배낭에 넣을 때 가치의 합이 최대가 되도록 짐을 고르는 방법 그래서 푸는 과정으로는 x축으로는 가방의 무게, y축으로는 짐의 개수로 생각하고 이전의 값을 참조하는 dp 문제로 모두 n+1, k+1로 배열과 반복문을 실행 이때 x축으로도 0의 무게에 대한 배낭, y축으로도 [0,0]을 따로 추가한 이유는 x축에 해당하는 0의 무게에 대한 배낭 값도 사용이 되기에 추가를 했음. ex) 배낭의 무게 j = 6, 실제 짐의 무게 6의 경우 6-6 = 0으로 0의 무게를 더하는 식이 되어야하는데 위의 식을 생각하지 못하면 -1인 k-1번째 무게를 가지기 때문. 이후 현재 반복문으로 탐색하는 가방의 현재 무게 j 보다 탐..

처음 접근해본 풀이 방법으로 분할과 정복 문제는 처음 배울때 재귀로 배웠어서 아래와 같이 접근했는데 아직 알고리즘을 쉽게 푸는 방식에 대해 깨닫지 못했는지 코드도 길고 시간도 꽤나 걸렸다. def CTP(li): global k, n if len(li) == 1: return li mid = len(li)//2 left, right = CTP(li[:mid]), CTP(li[mid:]) if k == n//mid: result.append(left+right) return sorted(left+right) import sys input = sys.stdin.readline n = int(input()) li = list(map(int,input().split())) k = int(input()) resu..

답이 잘 나왔는데 에러가 나길래 확인해보니... 파일의 끝에서 입력을 멈춘다를 잊고 있었다... 그래서 EOF(End of File) 예외처리를 통해 해결 그리고 처음에는 배열을 이용해서 풀어보려고 파라미터로 n과 해당 함수가 가질 수 있는 가장 큰 인덱스 값도 함께 넣어줬는데 그냥 이렇게 푸는게 더 편해서 ㅎㅎ def cantoer(n): if n == 1: return '- -' else: return cantoer(n-1) + ' '*(3**(n-1)) + cantoer(n-1) while True: try: n = int(input()) if n == 0: print('-') else: print(cantoer(n)) except EOFError:break

가장 단순히 1보다 작거나 같을 경우에 return 하는 재귀 풀이 def fectorial(n): if 1>=n: return 1 return n*fectorial(n-1) print(fectorial(int(input()))) 배열에 값을 추가하면서 해당 값이 존재하다면 바로 return 하는 재귀 풀이 def fectorial(n): if li[n]: return li[n] li[n] = n*fectorial(n-1) return li[n] n = int(input()) li = [0]*(n+1) li[0] = 1 fectorial(n) print(li[n])

for i in range(int(input())): # TC cnt n,m,l = map(int,input().split()) li = list(map(int,input().split())) for _ in range(m): idx,num = map(int,input().split()) li = li[:idx]+[num]+li[idx:] print('#%d %d'%(i+1,li[l]))

아래 코드는 2차원 배열을 활용해 푸는 방법 아직도 dp를 활용하여 누적합을 만들어 내는 로직을 구현하는데에 많은 어려움이 있어서 여러 방법을 찾아보려고 노력중. 우선 아래 코드에서 else 구문에 dp[i][j-1] 을 추가하여 max로 값을 찾는 이유에 대한 의문을 제기할 수 있다. 결과적으로는 저 코드를 추가함으로서 이전에 나온 값이 이만큼 나온적이 있다라는 의미가 되는데 ACAYKP CAPCAK 예시를 들어보자면 i가 2의 경우 a = 'C' j = 1일 땐 b = 'C' 가 될 때는 같기에 이전까지의 누적 합에 해당하는 dp[i-1][j-1] 에서 +1 해주고 j = 2일 땐 b = 'A' 가 될 때는 다르니 현재의 dp 값에는 i-1 층에 해당하는 현재 j 값과, j 가 1이었을 때의 값 중 ..

해당 문제는 그냥 손수 n = 5 까지 아니면 n = 6 까지만 손수 해봐도 규칙이 나오기에 dp를 활용해 누적해서 나아가는 풀이로 해결 주의할 점으로는 출력문에도 조건이 더 붙어서 나올 수 있으니 확인하기! n = int(input()) a, b = 1, 2 for _ in range(2, n): a, b = (b)%15746, (a+b)%15746 if n == 1: print(a) else: print(b)

우선 문제 이해에 대한 어려움이 컷다 dp를 저장할 배열을 어떻게 만들어야하는지에 대한 어려움도 크게 다가왔다. 그래서 n+1의 수만큼 배열을 만들어 n+1차원 배열을 만들어 문제를 해결 이후 n = 1의 경우엔 1~9까지 모두 1개만 만들어지니 for i in range(1, 10): dp[1][i] = 1 로 빠르게 해결 후 n = 2부터 실행하게 해서 j = 0의 경우엔 갈 수있는 경로가 1밖에 없기에 dp[i-1][1] 로 이전 배열의 1번의 dp 값을 그대로 가져오기 마찬가지로 j = 9 또한 경로가 8밖에 없기에 dp[i-1][8] 로 이전 배열의 8번의 dp 값을 그대로 가져오기 다른 수의 경우엔 위아래로 갈 수 있기에 두 개의 dp값을 더한 값을 누적하여 풀기 n = int(input())..