K

그리디 알고리즘을 이용한 문제 # 동전 0 # 준규가 가지고 있는 동전은 총 N종류이고, 각각의 동전을 매우 많이 가지고 있다. # 동전을 적절히 사용해서 그 가치의 합을 K로 만들려고 한다. 이때 필요한 동전 개수의 최솟값을 구하는 프로그램을 작성하시오. # 첫째 줄에 N, K가 주어진다. 둘째 줄부터 N개의 줄에 동전의 가치가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수) # 첫째 줄에 K원을 만드는데 필요한 동전 개수의 최솟값을 출력한다. n, k = map(int, input().split()) A = [] for i in range(n): A.append(int(input())) # 리스트의 뒤부터 탐색하며 k보다 큰 동전..

Do it! 알고리즘 코딩 테스트 - 파이썬 편 (김종관) 책을 이용하여 알고리즘 공부 중입니다 😃 https://www.youtube.com/watch?v=8V2zw6Qxarc&list=PLFgS-xIWwNVX-zm4m6suWC9d7Ua9z7fuT&index=23 그리디 알고리즘 현재 상태에서 보는 선택지 중 최선의 선택지가 전체 선택지 중 최선의 선택지라고 가정하는 알고리즘 최적의 해를 보장하지는 않음 해 선택: 현재 상태에서 가장 최선이라고 생각되는 해를 선택한다. 적절성 검사: 현재 선택한 해가 전체 문제의 제약 조건에 벗어나지 않는지 검사한다. 해 검사: 현재까지 선택한 해 집합이 전체 문제를 해결할 수 있는지 검사한다. 전체 문제를 해결하지 못한다면 1로 돌아가 같은 과정을 반복한다.

간단하게 푸는 방법 그러나 n^2의 시간 복잡도를 가지기 때문에 실패한다. n = int(input()) k = int(input()) A = [[] for _ in range(n)] B = [] for i in range(n): for j in range(n): A[i].append((i + 1) * (j + 1)) x = (i + 1) * (j + 1) B.append(x) print(B[k]) 이 문제를 푸는 핵심은 이진 탐색을 이용하는 것 이진 탐색을 이용하여 중앙값보다 작은 값의 개수가 k-1개일 때 멈추면 된다. # K번째 수 # 크기가 N×N인 배열 A를 만들었다. 배열에 들어있는 수 A[i][j] = i×j 이다. 이 수를 일차원 배열 B에 넣으면 B의 크기는 N×N이 된다. B를 오름차순..

이진 탐색을 이용한 문제 문제 해석이 너무 어렵다..;; # 기타 레슨 # 첫째 줄에 강의의 수 N (1 ≤ N ≤ 100,000)과 블루레이의 개수 M (1 ≤ M ≤ N)이 주어진다. 다음 줄에는 강토의 기타 강의의 길이가 강의 순서대로 분 단위로(자연수)로 주어진다. # 첫째 줄에 가능한 블루레이 크기중 최소를 출력한다. n, m = map(int, input().split()) A = list(map(int, input().split())) start = 0 end = 0 for i in A: if start < i: start = i end += i while start mid: # 블루레이 1개 증가 cnt += 1 sum = 0 sum += A[i] if sum != 0: cnt += 1 i..

이진 탐색을 이용한 문제 # 수 찾기 # 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) 선입선출 방식으로 탐색하므로 큐를 이용해 구현함 탐색 시작 노드와 가까운 노드를 우선하여 탐새갛므로 목표 노드에 도착하는 경로가 여러 개일 때 최..