목록전체 글 (69)
야금야금 공부
다이나믹 프로그래밍(동적 계획법) 이미 계산된 결과(작은 문제)는 별도의 메모리 영역에 저장해 다시 계산하지 않도록 해 수행 시간 효율성을 비약적으로 향상시키는 방법 일반적으로 Top-Down(하향식)과 Bottom-Up(상향식)으로 구성 Top-Down : 재귀 함수 사용. 큰 문제를 해결하기 위해 작은 문제를 재귀적으로 호출해 해결한 후, 큰 문제의 답을 얻을 수 있도록ex) Memorization 방식 Bottom-Up : DP의 전형적인 형태로 리스트와 반복문 사용. 작은 문제를 하나씩 해결해가며 리스트에 저장해 다음 문제를 해결 다음 2가지 조건을 만족할 때 사용 가능 1. 최적 부분 구조(Optimal Substructure) 큰 문제를 작은 문제로 나눌 수 있으며, 작은 문제의 답을 모아 큰..
6장 정렬 연속된 데이터를 기준에 따라 정렬하기 위한 알고리즘 - 선택 정렬 : 처리되지 않은 데이터 중 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸는 것 - 삽입 정렬 : 처리 되지 않은 데이터를 하나씩 골라 적절한 위치에 삽입 - 퀵 정렬 : 기준 데이터를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾸는 방법 - 계수 정렬 : 특정한 조건이 부합할 때만 사용할 수 있지만, 매우 빠르게 동작하는정렬 알고리즘 1. 선택 정렬 처리되지 않은 데이터 중 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸는 것 - 시간 복잡도 : N번 만큼 가장 작은 수를 찾아서 맨 앞으로 보내야 하므로, N + (N - 1) + (N - 2) + ... + 2 이므로 (N^2 + N - 2) /..
DFS/BFS 그래프를 탐색하기 위한 대표적인 두 가지 알고리즘 탐색(Search) : 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정 코딩 테스트에서 매우 자주 등장하는 유형 필요 자료구조 : 스택, 큐, 재귀함수 DFS (깊이 우선 탐색) 깊은 부분을 우선적으로 탐색하는 알고리즘 - 스택 혹은 재귀 함수를 이용 [동작 과정] 1. 탐색 시작 노드를 스택에 넣고 방문 처리를 한다. 2. 스택의 최상단 노드에 방문하지 않은 인접 노드가 1개라도 있으면, 그 노드를 스택에 넣고 방문 처리한다. 3. 방문하지 않은 인접 노드가 없으면, 스택에서 최상단 노드를 꺼낸다. 4. 더 이상 2번 과정을 수행할 수 없을 때까지 반복 (방문 기준 : 번호가 낮은 순서) 시작 노드 : 1 # DFS 메서드 정의 def..
onCreate() : 앱의 진입점. 다른 함수를 호출하여 사용자 인터페이스를 빌드함. ex) Kotlin의 main() 함수 setContent() : 레이아웃을 정의하는데 사용 @Composable : 이 주석으로 표시된 모든 함수는 setContent() 함수 또는 다른 구성 가능한 함수에서 호출할 수 있다. 아무것도 반환하지 않는다. 주석은 Jetpack Compose에서 이 함수가 UI를 생성하는 데 사용된다고 Kotlin 컴파일러에게 알리는 역할을 한다. 1. 구성 가능한 함수 몇 가지 입력을 받아 화면에 표시되는 내용을 생성하는 함수 구성 요소 ex) Greeting() 함수 : 위에 @Composable 주석이 있으므로 구성 가능한 함수이다. @Composable fun Greeting(n..
문제 준규가 가지고 있는 동전은 총 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의 배수이다. 아이디어 : 가장 큰 화폐 단위부터 돈을 거슬러 준다. ..