K

깊이 우선 탐색을 이용한 문제 # 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) 실제 구현 시 재귀 함수를 이용하므로 스택 오버플로우에 유의해야 함 단절점..

계수 정렬을 이용한 문제 # 수 정렬하기 3 # N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오. # 첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다. # 첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다. import sys input = sys.stdin.readline n = int(input()) A = [0] * 10001 for i in range(n): num = int(input()) A[num] += 1 for i in range(1, 10001): if A[i] != 0: for j in range(A[i]): prin..

Do it! 알고리즘 코딩 테스트 - 파이썬 편 (김종관) 책을 이용하여 알고리즘 공부 중입니다 😃 https://www.youtube.com/watch?v=6tz6oD6ZFvM&list=PLFgS-xIWwNVX-zm4m6suWC9d7Ua9z7fuT&index=19 정렬 알고리즘 정의 버블 bubble 데이터의 인접 요소끼리 비교하고, swap 연산을 수행하며 정렬하는 방식 선택 selection 대상에서 가장 크거나 작은 데이터를 찾아가 선택을 반복하면서 정렬하는 방식 삽입 insertion 대상을 선택해 정렬돈 영역에서 선택 데이터의 적절한 위치를 찾아 삽입하면서 정렬하는 방식 퀵 quick pivot 값을 선정해 해당 값을 기준으로 정렬하는 방식 병합 merge 이미 정렬된 부분 집합들을 효율적으로..

병합 정렬을 이용한 문제 기존 병합 정렬 코드에 아래 부분만 추가된다. # 뒷 그룹의 요소가 선택되는 경우에만 역전이 일어나므로 cnt++ cnt = cnt + index2 - k # 버블 소트 # N개의 수로 이루어진 수열에 대해서 버블 소트를 수행할 때, 총 몇 번의 swap이 발생하는지 알아내시오. # 첫째 줄에 N이 주어진다. 둘째 줄에 N개의 수가 주어진다. 총 swap 횟수를 출력하시오. # 병합 정렬 함수 def merge(s, e): global cnt # 그룹의 개수가 2개 미만이면 종료 if e - s < 1: return # 그룹 나눌 위치 설정 m = int(s + (e - s) / 2) # 나눈 위치 기준으로 앞 뒤 그룹 각각 병합 정렬 merge(s, m) merge(m + 1,..

def merge(s, e): if e - s < 1: return m = int(s + (e - s) / 2) merge(s, m) merge(m + 1, e) for i in range(s, e + 1): tmp[i] = A[i] k = s index1 = s index2 = m + 1 while index1

Do it! 알고리즘 코딩 테스트 - 파이썬 편 (김종관) 책을 이용하여 알고리즘 공부 중입니다 😃 https://www.youtube.com/watch?v=KNKj8QSbRXE&list=PLFgS-xIWwNVX-zm4m6suWC9d7Ua9z7fuT&index=18 정렬 알고리즘 정의 버블 bubble 데이터의 인접 요소끼리 비교하고, swap 연산을 수행하며 정렬하는 방식 선택 selection 대상에서 가장 크거나 작은 데이터를 찾아가 선택을 반복하면서 정렬하는 방식 삽입 insertion 대상을 선택해 정렬돈 영역에서 선택 데이터의 적절한 위치를 찾아 삽입하면서 정렬하는 방식 퀵 quick pivot 값을 선정해 해당 값을 기준으로 정렬하는 방식 병합 merge 이미 정렬된 부분 집합들을 효율적으로..

# K번째 수 # 수 N개가 주어진다. 오름차순 정렬했을 때, 앞에서부터 K번째에 있는 수를 구하시오. # 첫째 줄에 수의 개수 N과 수의 위치 K가 주어진다. 둘째 줄에 N개의 수가 주어진다. K번째 수를 출력하시오. N, K = map(int, input().split()) A = list(map(int, input().split())) # 위치 변경 함수 def swap(i, j): global A tmp = A[i] A[i] = A[j] A[j] = tmp # pivot 값과 위치 구하는 함수 def partition(S, E): global A # 요소가 2개라면 바로 정렬 if E - S == 1: if A[S] > A[E]: swap(S, E) return E # 중앙값을 pivot으로 설정..