🔗 Algorithm

[Python] 백준 1208

구글링이 잘 안돼서...직접 쓰는 리뷰 😅 1182번 부분수열의 합과 같은 유형의 문제이지만 범위와 시간제한 등으로 다른 풀이 방법을 적용해야한다. n개의 원소를 가진 수열의 부분 수열을 구하는 방법은 2**n 이라고 한다. 이 문제의 최대 범위는 n==40이므로 최악의 경우 2**40의 복잡도를 가지게된다. 그래서 이 문제는 리스트를 반으로 나눠 반에 해당하는 부분 수열을 구할 것이다. 그럼 최악의 경우 (2**20)*2이다. (2**20)*2 = 2097152 VS 2**40 = 1099511627776 효율 ㅇㅈ? 나는 딕셔너리를 사용해서 부분 수열을 구했다. (이유는 뒤에) key : 부분 수열의 합 value : 해당 부분 수열의 합이 나온 횟수 예제를 예로 들어 코드 설명을 하자면 우선 l=[..

[Python] 백준 1167, 1967

입력값의 차이 외에는 똑같은 문제이다. 먼저 트리의 지름을 찾는데에는 rule이 있다. ✔ 트리에서 임의의 노드(A)를 선택해 가장 먼 노드를 찾는다. -> B ✔ B에서 가장 먼 노드를 찾는다. -> C ✔ 그러면 B와 C사이의 거리가 가장 멀다. (==지름) 이 규칙을 알면 쉽게 쉽게 풀 수 있겠다. 모르면 ㅠㅠ 삽질 하니까 알고있자... Answer 1167 import sys from collections import defaultdict from collections import deque n=int(sys.stdin.readline()) dic=defaultdict(list) for i in range(n): l=list(map(int,sys.stdin.readline().split())) a..

[Python] 백준 10917

어려웠던 문제는 스스로 솔브해도 다른 사람 풀이랑 비교하기 위해서 검색을 해보는데 푼 사람이 별로 없어서 검색해도 안나와서 슬펐당... 내 답이 최적인지는 모르겠으나 일단 풀었고 푼 사람이 별로 없어서 나라도 리뷰를 써놔야지,,😇 일단 나는 BFS + 우선순위Q로 풀었다. 딕셔너리를 만들고 x를 key로 y를 value로 두고, value는 우선순위Q 내림차순으로 저장했다. (꿈은 더 큰 수로 이동하고 N이 가장 크기 때문에 N을 가지고 있다면 바로 그만 할 수 있게하기 위함) 그리고 queue에 현재 위치와 현재 상황이 바뀐 횟수를 저장하며 BFS를 한다. N을 만나면 그만한다. (bfs니까 처음만날 때 최소) Result import sys from collections import defaultdi..

[Python] 백준 2089

덕분에 파이썬에서 a//b가 어떻게 동작하는지 정확히 알 수 있었다. 이렇게 동작한다고 한다. import sys n = int(sys.stdin.readline()) if n == 0: print(0) else: res = [] while n != 0: if n%(-2) == 0: res.append('0') n = n//(-2) else: res.append('1') n = n//(-2) +1 print(''.join(reversed(res)))

[Python] 백준 1442

solution은 간단하게 받은 수 중에서 가장 큰 수를 n-k개 더 만들어 주고 그 수들로 정렬하면 된다. 단, 정렬할 때 문제에서 준 예제와 같이 7 3 2 처럼 주어진 숫자가 같은 자리 숫자라면 상관 없지만 9 90 990 과 같은 숫자가 주어졌을 때 문제가 생긴다. 가장 큰 수 부터 정렬하면 990 90 9 이지만 실제로 가장 큰 수를 만들기 위해서는 9 990 90 와 같이 정렬되어야 한다. 예전에 풀었던 문제에서 해결 방법을 찾았다! num.sort(key = lambda x: x*10, reverse=True) num의 숫자들은 type이 문자열이다. 이 문제의 최대 범위가 1,000,000,000 이므로 숫자의 최대길이가 10이다. 그러므로 길이 10만큼만 비교하면 된다. 예를 들면, 20..

[Python] 백준 6549

교훈 : 플래라고 겁먹지 말자 stack을 이용해서 풀었다 stack 삽입 : index와 높이(h) 원리 : 현재 index보다 stack에 있는 index(나보다 왼쪽)의 h가 더 크면 현재 index의 h값으로 왼쪽도 포함할 수 있다. 더보기 여기서 오른쪽의 높이(2) 로 왼쪽을 포함하여 넓이가 4가 될 수 있다. 이 원리를 이용해 stack으로 풀 수 있었다! import sys while True: #마지막에 stack에 있는 값을들 다 꺼내기 위해 마지막 h값은 0 h = list(map(int, sys.stdin.readline().split())) + [0] if h[0] == 0: break n = h[0] stack = [(1,h[1])] res = 0 for i in range(2,n..

[Python] 백준 2606

BFS또는 DFS를 사용하는 그래프 탐색 문제다. 먼저, 입력받은 데이터는 딕셔너리로 구현하였다. 네트워크는 양방향 그래프 이므로 아래 코드와 같이 딕셔너리에 두 번 입력해야 한다. 그래프 구현 net = {} for i in range(n): a, b = map(int, input().split()) if a in net : net[a].append(b) else : net[a] = [b] if b in net : net[b].append(a) else : net[b] = [a] 같은 네트워크 상에 있는 컴퓨터를 검색하는 알고리즘은 BFS를 사용했다. visit에서 1을 빼면 1과 연결되어 있는 컴퓨터만 남게 되기 때문에 len(visit)-1을 결과로 출력했다. 전체코드 m = int(input())..

[Python] 백준 1260

단순히 DFS와 BFS를 구현하여 출력하면 된다. 그래프 구현 graph = [[0]*(N+1) for x in range(N+1)] for i in range(M): temp = list(map(int, input().split(' '))) graph[temp[0]][temp[1]] = 1 graph[temp[1]][temp[0]] = 1 그래프는 2차원 배열로 구현하였다. 두 정점을 연결하는 간선을 1로 바꿔준다. 양방향 그래프이기 때문에 두 번 바꿔주어야 한다. 예를들어 간선이 1과 2를 연결한다면, 2차원 배열은 다음과 같다. DFS 구현 탐색을 시작할 정점을 파라미터로 받아 dfs를 수행하는 함수이며, recursive로 구현하였다. graph에서 연결된 정점을 리스트로 만들고, 리스트에 해당하..

[Algorithm] 너비 우선 탐색 BFS / 깊이 우선 탐색 DFS

개인적으로 어려워 하는 알고리즘,, 알고리즘 BFS는 FIFO를 원칙으로 하는 Queue로 구현한다. 탐색을 시작하는 첫 노드(root)를 queue에 넣고 탐색을 시작한다. A. queue에서 노드를 꺼낸다. B. 꺼낸 노드와 연결된 노드 중 방문하지 않은 노드를 방문하고 queue에 넣는다. queue에 노드가 없어질 때 까지 AB반복 구현 def bfs(graph, root): visit = list() queue = [root] #AB반복 while queue: temp = queue.pop(0) if temp not in visit: print(temp) visit.append(temp) queue.extend(graph[temp]) 알고리즘 DFS는 LIFO를 원칙으로 하는 Stack으로 구현..

[Python] 백준 2231

완전탐색하는 brute force 문제이다. 먼저 1부터 N까지 모두 고려하는 방법이있다. 내가 처음으로 제출한 답이기도 하다. 예를들어 256의 생성자를 찾기위해 1부터 순차적으로 탐색해 생성자가 나오면 종료한다. import sys N = int(input()) def Constructor(M): result = M devide = list(str(M)) for i in devide: result += int(i) return result if N < 10 : print(0) else: num = 10 while M