나만의 개발블로그

해당 문제는 일반적인 그래프 문제로 방문 여부에 대한 체크를 하며 카운팅을 해 푼 풀이법 import sys from collections import deque input = sys.stdin.readline n = int(input()) arr = [list(map(int,input().strip('\n'))) for _ in range(n)] visit = [[0]*n for _ in range(n)] stack = deque([]) result = [] r_cnt = 0 for i in range(n): for j in range(n): if arr[i][j] and not visit[i][j]: cnt, r_cnt = 1, r_cnt + 1 visit[i][j] = 1 stack.append([..

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..

문제 해결 방법으로는 시작 시간과 종료 시간을 기준으로 화물차 작업 시간을 담은 배열을 내림차순 정렬 그리고 가장 중요했던 포인트로 오름차순 정렬을 한 뒤 종료 시간과 현재 시작 시간을 비교하며 나아가보니 중간에 시간을 많이 차지하는 경우가 있더라도 그냥 체크를 하고 넘어가서 문제가 되기에 내림차순 정렬을 해서 조사를 하는 것이 포인트가 되는 것 같다. for tc in range(1, int(input())+1): n = int(input()) form = [list(map(int,input().split())) for _ in range(n)] form.sort(key=lambda x:(x[0], x[1]), reverse=True) result = 0 for x in range(n): s,e = f..

문제 해결 방법으로는 화물의 무게와 트럭 적재용량을 내림 차순 정렬 후 추가된 개수만큼 idx를 증가시키며 찾도록 했다. for tc in range(1,int(input())+1): n,m = map(int,input().split()) w_li = sorted(list(map(int,input().split())), reverse=True) # 화물 무게 t_li = sorted(list(map(int,input().split())), reverse=True) # 트럭 적재 용량 cnt, hap = 0, 0 # 적재된 횟수. 누적 합 for i in range(n): if t_li[cnt]>=w_li[i]: cnt, hap = cnt +1, hap+w_li[i] if cnt == m: break pr..

흠... 너무 오래걸렸다.. 오래 걸린 이유는 아래와 같은 tc의 경우에 [0,1]인 18부터 시작할 경우 우선 48,55 이렇게 두 가지 경로로 갈 수가 있는데 48로 가는 순간 다시 0번째 행으로 가게 되어서 34를 조회하게 되는 경우가 발생하게 되는 것 때문에 너무 오래 걸렸다... 0 18 34 48 0 55 18 7 0 그래서 1로 가지 않게 for문을 1, n으로 두고 마지막에 cnt 가 n-2의 경우에 s행의 0번째 인덱스 값을 더해줘 해결하도록 했음. def search(s, hap, cnt): global mx_hap if cnt == n-2: mx_hap = min(mx_hap, hap+arr[s][0]) return if hap >= mx_hap: return for i in rang..

주의점으로는 elif 문을 추가해 hab이 현재 result 값 보다 큰 값일 경우엔 더 이상 조사하지 않도록 해주기! for tc in range(1, int(input())+1): n = int(input()) arr = [list(map(int,input().split())) for _ in range(n)] result = 11*n*n # dfs 사용 stack = [[0, 0, arr[0][0]]] while stack: x,y,hab = stack.pop() if x == n-1 and y == n-1: if result > hab: result = hab continue elif hab >= result: continue # 오른쪽, 아래만 탐색 for i,j in [[0, 1], [1, 0..

답이 잘 나왔는데 에러가 나길래 확인해보니... 파일의 끝에서 입력을 멈춘다를 잊고 있었다... 그래서 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