K

이진 탐색을 이용한 문제 # 수 찾기 # N개의 정수가 주어져 있으 ㄹ때, 이 안에 X라는 정수가 존재하는지 알아내는 프로그램을 작성하시오. # 첫째 줄에 자연수 N이 주어진다. 다음 줄에는 N개의 정수가 주어진다. # 다음 줄에ㅔ는 M이 주어진다. 다음 줄에는 M개의 정수가 주어진다. # M개의 수들이 N개의 수 안에 존재하는지 알아내시오. # M개의 줄에 답을 출력하시오. 존재하면 1, 존재하지 않으면 0을 출력하시오. n = int(input()) A = list(map(int, input().split())) A.sort() m = int(input()) X = list(map(int, input().split())) for i in X: find = False start = 0 end = n -..

Do it! 알고리즘 코딩 테스트 - 파이썬 편 (김종관) 책을 이용하여 알고리즘 공부 중입니다 😃 https://www.youtube.com/watch?v=1vZijMmhGNw&list=PLFgS-xIWwNVX-zm4m6suWC9d7Ua9z7fuT&index=22 이진 탐색(Binary Serch) 데이터가 정렬되어 있는 상태에서 원하는 값을 찾아내는 알고리즘 대상 데이터의 중앙값과 찾고자 하는 값을 비교해 데이터의 크기를 절반씩 줄이면서 대상을 찾음 기능 특징 시간 복잡도 타겟 데이터 탐색 중앙값 비교를 통한 대상 축소 방식 O(logn) 정렬 데이터에서 원하는 데이터를 탐색할 때 사용하는 가장 일반적인 알고리즘 구현 및 원리가 비교적 간단하기때문에 부분 문제로 요구하는 영역임 현재 데이터셋의 중앙값..

너비 우선 탐색을 이용한 문제 # 트리의 지름 # 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고(2 ≤ V ≤ 100,000), 둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 주어진다. # 두 점 사이의 거리 중 가장 긴 것을 출력하시오. # 너비 우선 탐색 함수 def BFS(v): visited[v] = True queue.append(v) while queue: a = queue.popleft() for i in A[a]: if visited[i[0]] == False: visited[i[0]] = True queue.append(i[0]) distance[i[0]] = distance[a] + i[1] import sys from collections import deque sys.setrec..

너비 우선 탐색을 이용한 문제 # 미로 탐색 # 미로에서 1은 이동할 수 있는 칸을 나타내고, 0은 이동할 수 없는 칸을 나타낸다. 이러한 미로가 주어졌을 때, (1, 1)에서 출발하여 (N, M)의 위치로 이동할 때 지나야 하는 최소의 칸 수를 구하는 프로그램을 작성하시오. # 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. # 첫째 줄에 지나야 하는 최소의 칸 수를 출력한다. # 너비 우선 탐색 함수 def BFS(i, j): visited[i][j] = True queue.append((i, j)) # 큐가 비기 전까지 반복 while queue: a = queue.popleft() for k in range(4): x = a..

깊이 우선 탐색과 너비 우선 탐색을 이용한 문제 처음엔 아래와 같이 제출했다가 런타임 에러 인덱스 오류를 만났다. 답을 출력할 범위에서 실수가 발생했다. 정점의 개수는 많지만 연결이 안되어 있는 경우를 생각하지 않은 것이다. 간선의 개수로 출력한다면, 한 점에서 간선이 여러 개 이어진 경우에서 걸린다. # 깊이 우선 탐색 함수 def DFS(v): visited[v] = True answer_DFS.append(v) for i in A[v]: if visited[i] == False: DFS(i) # 너비 우선 탐색 함수 def BFS(v): visited[v] = True queue.append(v) # 큐가 비기 전까지 반복 while queue: a = queue.popleft() answer_BF..

Do it! 알고리즘 코딩 테스트 - 파이썬 편 (김종관) 책을 이용하여 알고리즘 공부 중입니다 😃 https://www.youtube.com/watch?v=Cs8DaupoSPM&list=PLFgS-xIWwNVX-zm4m6suWC9d7Ua9z7fuT&index=21 너비 우선 탐색, BFS(Breadth First Serch) 그래프 완전 탐색 기법 중 하나 시작 노드를 기준으로 가까운 노드를 먼저 방문하면서 탐색하는 알고리즘 기능 특징 시간 복잡도(노드 수: V, 엣지 수: E) 그래프 완전 탐색 - FIFO 탐색 - Queue 자료구조 이용 O(V + E) 선입선출 방식으로 탐색하므로 큐를 이용해 구현함 탐색 시작 노드와 가까운 노드를 우선하여 탐새갛므로 목표 노드에 도착하는 경로가 여러 개일 때 최..

깊이 우선 탐색을 이용한 문제 # ABCDE # 깊이가 5 이상 내려가는 노드가 존재하는지 찾으시오. # 첫째 줄에 노드의 수 N, 엣지의 수 M이 주어진다. # 5 이상인 노드가 존재하면 1, 존재하지 않으면 0을 출력하시오. def DFS(v, cnt): global arrive if cnt == 5: arrive = True return visited[v] = True for i in A[v]: if visited[i] == False: DFS(i, cnt + 1) visited[v] = False import sys sys.setrecursionlimit(10000) input = sys.stdin.readline n, m = map(int, input().split()) A = [[] for _..

깊이 우선 탐색을 이용한 문제 # 신기한 소수 # 왼쪽부터 1자리, 2자리, ..., N자리 수 모두 소수인 수를 찾아라. # 첫째 줄에 N이 주어진다. N자리 수 중에서 해당하는 소수를 찾아 오름차순으로 정렬해서 한 줄에 하나씩 출력한다. # 소수 판단 함수 def isPrime(num): for i in range(2, int(num / 2 + 1)): if num % i == 0: return False return True # 깊이 우선 탐색 함수 def DFS(num): if len(str(num)) == N: print(num) else: for i in range(1, 10): # 현재 수에 i를 붙였을 때 홀수 && 소수인 경우만 출력 if (num*10 + i) % 2 == 1 and i..

깊이 우선 탐색을 이용한 문제 sys.setrecursionlimit(10000) 재귀 횟수 제한을 안걸었더니 런타임 에러가 났다 .. # 연결 요소의 개수 # 방향 없는 그래프가 주어졌을 때, 연결 요소 (Connected Component)의 개수를 구하는 프로그램을 작성하시오. # 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주어진다. # 첫째 줄에 연결 요소의 개수를 출력한다. import sys sys.setrecursionlimit(1000) input = sys.stdin.readline n, m..

Do it! 알고리즘 코딩 테스트 - 파이썬 편 (김종관) 책을 이용하여 알고리즘 공부 중입니다 😃 https://www.youtube.com/watch?v=lFtQnOhKnr0&list=PLFgS-xIWwNVX-zm4m6suWC9d7Ua9z7fuT&index=20 깊이 우선 탐색, DFS(Depth First Serch) 그래프 완전 탐색 기법 중 하나 그래프의 시작 노드에서 출발하여 탐색할 한 쪽 분기를 정하여 최대 깊이까지 탐색을 마친 후 다른 쪽 분기로 이동하여 다시 탐색을 수행하는 알고리즘 기능 특징 시간 복잡도(노드 수: V, 엣지 수: E) 그래프 완전 탐색 - 재귀 함수로 구현 - 스택 자료구조 이용 O(V + E) 실제 구현 시 재귀 함수를 이용하므로 스택 오버플로우에 유의해야 함 단절점..