백준4 [알고리즘] 백준 1043 거짓말 백준 1043 거짓말문제의 키포인트는 진실을 아는 사람들의 리스트를 계속 갱신을 해줘야 하는데 그것을 어떻게 하느냐이다. 이러한 알고리즘에 최적인 유니온 파인드를 쓸 수 있다.유니온 파인드 알고리즘이란? 그래프 알고리즘의 일종으로서 상호 배타적 집합이라고 한다. 여러 노드가 존재할 때 어떤 두 개의 노드를 같은 집합으로 묶어주고, 다시 어떤 두 노드가 같은 집합에 있는지 확인하는 알고리즘이다.import sysfrom collections import dequeimport heapqdef find(a): if a == parents[a]: return a return find(parents[a])def union(x,y): x = find(x); y = find(y) if x 1:.. 2024. 10. 16. [알고리즘] 백준 13023 ABCDE 백준 13023 ABCDE 모든 시작점을 훑어야 하기 때문에 DFS문제라고 생각했다.그러나 문제는 "어떻게 메모리를 줄여야 하냐?" 인 것이다.import sysdef DFS(x,start): if x == 4: print(1) sys.exit() for i in range(n): if f_ship[start][i] == 1 and res[i] == 0: res[i] = 1 DFS(x+1,i) res[i] = 0n,m = map(int,sys.stdin.readline().split())f_ship = [[0]*n for _ in range(n)]for _ in range(m): a,b = .. 2024. 10. 16. [알고리즘] 백준 13549 숨바꼭질 3 백준 13549 숨바꼭질 3 이 문제는 단순 BFS문제라고 생각했다.import sysimport collectionsfrom collections import dequen,m = map(int,sys.stdin.readline().split())MAX = 100000res = [0]*(MAX+1)res[n] = 1dq = deque()dq.append(n)while dq: ex = dq.popleft() if ex == m: print(res[ex]-1) break for num in (ex+1,ex-1,ex*2): if 0 📌 처음 이러한 풀이로 제출했지만 틀렸다. 그래서 30분 정도를 애 먹었다.키 포인트는 ex의 두 배와 (ex+1,ex-1)의 가.. 2024. 10. 14. [알고리즘] 백준 1107 리모컨 백준 1107 리모컨 단순히 100만의 수만 보면 되기 때문에 단순 브루트포스 문제라고 생각했다.그러나 어떠한 수가 입력됐을 때 무작정 100만의 수만 보면 메모리 낭비라고 생각했다.📌N이 입력됐을 때 범위를 어떻게 설정해줘야 할까?기본 채널이 100번으로 설정되어 있기 때문에 임의의 N과의 최댓값은 +만 사용했을 때N-100이라고 볼 수 있다. 따라서 N의 두 배인 2N이상의 값에서는 앞에서의 최댓값보다 크기 때문에 구할 필요가 없다. 정답📌 범위를 N*2+1가 아닌 이유는 0이 입력됐을 때 0~100의 수를 조사할 수 없기 때문에 N*2+101를 썼다.import sysn = int(sys.stdin.readline())num = int(sys.stdin.readline())if num == 0.. 2024. 10. 14. 이전 1 다음