6장 정렬연속된 데이터를 기준에 따라 정렬하기 위한 알고리즘- 선택 정렬 : 처리되지 않은 데이터 중 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸는 것- 삽입 정렬 : 처리 되지 않은 데이터를 하나씩 골라 적절한 위치에 삽입- 퀵 정렬 : 기준 데이터를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾸는 방법- 계수 정렬 : 특정한 조건이 부합할 때만 사용할 수 있지만, 매우 빠르게 동작하는정렬 알고리즘1. 선택 정렬처리되지 않은 데이터 중 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸는 것- 시간 복잡도 : N번 만큼 가장 작은 수를 찾아서 맨 앞으로 보내야 하므로, $N + (N - 1) + (N - 2) + ... + 2$ 이므로 $(N^2 + N - 2) / 2 = ..

DFS/BFS그래프를 탐색하기 위한 대표적인 두 가지 알고리즘탐색 (Search) : 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정코딩 테스트에서 매우 자주 등장하는 유형필요 자료구조 : 스택, 큐, 재귀함수 DFS (깊이 우선 탐색)깊은 부분을 우선적으로 탐색하는 알고리즘스택 혹은 재귀 함수를 이용 [동작 과정]1. 탐색 시작 노드를 스택에 넣고 방문 처리를 한다.2. 스택의 최상단 노드에 방문하지 않은 인접 노드가 1개라도 있으면, 그 노드를 스택에 넣고 방문 처리한다.3. 방문하지 않은 인접 노드가 없으면, 스택에서 최상단 노드를 꺼낸다.4. 더 이상 2번 과정을 수행할 수 없을 때까지 반복 (방문 기준 : 번호가 낮은 순서) 시작 노드 : 1 # DFS 메서드 정의def dfs(graph..

`onCreate()` : 앱의 진입점. 다른 함수를 호출하여 사용자 인터페이스를 빌드함. ex) Kotlin의 main() 함수`setContent()` : 레이아웃을 정의하는데 사용`@Composable` : 이 주석으로 표시된 모든 함수는 `setContent()` 함수 또는 다른 구성 가능한 함수에서 호출할 수 있다. 아무것도 반환하지 않는다.주석은 Jetpack Compose에서 이 함수가 UI를 생성하는 데 사용된다고 Kotlin 컴파일러에게 알리는 역할을 한다. 1. 구성 가능한 함수몇 가지 입력을 받아 화면에 표시되는 내용을 생성하는 함수 구성 요소ex)`Greeting()` 함수 : 위에 `@Composable` 주석이 있으므로 구성 가능한 함수이다.@Composablefun Gre..

문제 준규가 가지고 있는 동전은 총 N종류이고, 각각의 동전을 매우 많이 가지고 있다. 동전을 적절히 사용해서 그 가치의 합을 K로 만들려고 한다. 이때 필요한 동전 개수의 최솟값을 구하는 프로그램을 작성하시오. 입력 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수) 출력 첫째 줄에 K원을 만드는데 필요한 동전 개수의 최솟값을 출력한다. 예제 입력 1 10 4200 1 5 10 50 100 500 1000 5000 10000 50000 예제 출력 1 6 예제 입력 2 10 4790 1 5 10 50 ..

Greedy(탐욕법) 사전에 외우고 있지 않아도 풀 수 있을 가능성이 높은 문제 유형 현재 상황에서 지금 당장 좋은 것만 고르는 방법 기준에 따라 좋은 것을 선택하는 알고리즘 가장 큰 순서대로, 가장 작은 순서대로 같은 기준을 제시해줌 → 정렬과 짝을 이뤄 같이 출제 최소한의 아이디어를 떠올리고, 이 아이디어가 정당한 지 검토할 수 있어야 한다. [예제1] 거스름돈 당신은 음식점의 계산을 도와주는 점원이다. 카운터에는 거스름돈으로 사용할 500원, 100원, 50원, 10원짜리 동전이 무한히 존재한다고 가정한다. 손님에게 거슬러 줘야 할 돈이 N원일 때 거슬러 줘야할 동전의 최소 개수를 구하라. 단, 거슬러 줘야 할 돈 N은 항상 10의 배수이다. 아이디어 : 가장 큰 화폐 단위부터 돈을 거슬러 준다. ..

풀이 # 연산자는 앞에서부터 # 나눗셈은 정수 나눗셈으로 몫만 취함 # 음수를 양수로 나눌 때, 양수로 바꾼뒤 몫을 구하고 음수로 변환 from itertools import permutations N = int(input()) num = list(map(int, input().split())) sign_list = list(map(int, input().split())) sign = ['+', '-', '*', '/'] op = [] for i in range(len(sign_list)): for j in range(sign_list[i]): op.append(sign[i]) result = [] for i in permutations(op, N-1): calc = num[0] for j in rang..

문제 자연수 M과 N이 주어질 때 M이상 N이하의 자연수 중 소수인 것을 모두 골라 이들 소수의 합과 최솟값을 찾는 프로그램을 작성하시오. 예를 들어 M=60, N=100인 경우 60이상 100이하의 자연수 중 소수는 61, 67, 71, 73, 79, 83, 89, 97 총 8개가 있으므로, 이들 소수의 합은 620이고, 최솟값은 61이 된다. 입력 입력의 첫째 줄에 M이, 둘째 줄에 N이 주어진다. M과 N은 10,000이하의 자연수이며, M은 N보다 작거나 같다. 출력 M이상 N이하의 자연수 중 소수인 것을 모두 찾아 첫째 줄에 그 합을, 둘째 줄에 그 중 최솟값을 출력한다. 단, M이상 N이하의 자연수 중 소수가 없을 경우는 첫째 줄에 -1을 출력한다. 예제 입력 1 60 100 예제 출력 1 6..

문제동호는 내년에 초등학교를 입학한다. 그래서 동호 어머니는 수학 선행 학습을 위해 쉽게 푸는 문제를 동호에게 주었다.이 문제는 다음과 같다. 1을 한 번, 2를 두 번, 3을 세 번, 이런 식으로 1 2 2 3 3 3 4 4 4 4 5 .. 이러한 수열을 만들고 어느 일정한 구간을 주면 그 구간의 합을 구하는 것이다.하지만 동호는 현재 더 어려운 문제를 푸느라 바쁘기에 우리가 동호를 도와주자.입력첫째 줄에 구간의 시작과 끝을 나타내는 정수 A, B(1 ≤ A ≤ B ≤ 1,000)가 주어진다. 즉, 수열에서 A번째 숫자부터 B번째 숫자까지 합을 구하면 된다.출력첫 줄에 구간에 속하는 숫자의 합을 출력한다. 예제 입력 13 7예제 출력 115 풀이a, b = map(int, input().split())..

문제 주어진 수 N개 중에서 소수가 몇 개인지 찾아서 출력하는 프로그램을 작성하시오. 입력 첫 줄에 수의 개수 N이 주어진다. N은 100이하이다. 다음으로 N개의 수가 주어지는데 수는 1,000 이하의 자연수이다. 출력 주어진 수들 중 소수의 개수를 출력한다. 예제 입력 1 4 1 3 5 7 예제 출력 1 3 풀이 N = int(input()) num = list(map(int, input().split())) ans = [] for i in num: cnt = 0# 나누었을 때 0이 되는 숫자의 개수 for j in range(1, i + 1): if i % j == 0: # 입력 받은 숫자를 1부터 자기자신의 수까지 나누어, 나머지가 0인 횟수를 구함 cnt += 1 ans.append(cnt)# ..

위장해시를 사용하는 문제 풀이def solution(clothes): hash = {} # hash를 초기화 => {"옷 종류" : 0} for n, t in clothes: hash[t] = 0 # 옷 종류별로 가진 옷의 수를 해시에 넣음 for key in hash.keys(): cnt = 0 for n, t in clothes: if key == t: cnt += 1 hash[key] = cnt value = list(hash.values()) # [2, 1] ans = 1 # 경우의 수를 계산 for i in value: ..