ajeong

`이것이 코딩 테스트다 (나동빈)` 커리큘럼에 따라 진행합니다 ✨ 계수 정렬 정의 - 매우 빠르게 동작하지만 특정한 조건이 부합할 때만 사용이 가능하다. - 데이터의 크기 범위가 제한되어 정수 형태로 표현할 수 있을 때 사용 가능 - 데이터의 개수가 N, 데이터 (양수) 중 최댓값이 K일 때, 최악의 경우에도 수행 시간이 O(N+K)를 보장한다 동작 방식 1. 가장 작은 데이터부터 가장 큰 데이터까지의 범위가 모두 담길 수 있도록 리스트를 생성 -> 정렬할 데이터의 가장 작은 데이터가 0이고, 가장 큰 데이터가 9이면, 0부터 9까지의 리스트를 생성한다 2. 데이터를 하나씩 돌면서 데이터와 동일한 인덱스에 데이터가 몇 번 등장했는지 개수를 센다. 시간 복잡도 - O(N+K) - 때에 따라 심각한 비효율성..

`이것이 코딩 테스트다 (나동빈)` 커리큘럼에 따라 진행합니다 ✨ 퀵 정렬 정의 - 기준 데이터를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾸는 방법 - 일반적인 상황에서 가장 많이 사용되는 정렬 알고리즘 중 하나 - 가장 기본적인 퀵 정렬은 첫 번째 데이터를 기준 데이터 (Pivot)로 설정한다 방식 1. 피벗의 값을 설정한다 (대부분 첫 번째 데이터를 기준으로 함) 2. 왼쪽에서부터 피벗보다 큰 데이터를 고르고, 오른쪽에서부터는 피벗보다 작은 데이터를 고른다 3. 위치가 엇갈리는 경우 (왼쪽과 오른쪽으로 접근하다가 왼쪽에서 선택한 값이 오른쪽이 되고, 오른쪽에서 선택한 값이 왼쪽이 되는 경우) 피벗과 작은 데이터의 위치를 서로 변경한다 4. 분할 완료 후 다시 반으로 나눈 데이터들에 ..

`이것이 코딩 테스트다 (나동빈)` 커리큘럼에 따라 진행합니다 ✨ 삽입 정렬 정의 - 처리되지 않은 데이터를 하나씩 골라 적절한 위치에 삽입 - 선택 정렬에 비해 구현 난이도가 높은 편이지만, 일반적으로 더 효율적으로 동작한다. - 앞쪽의 원소들이 이미 정리되어 있다고 가정하고 뒤쪽에 있는 원소를 적절한 위치에 삽입한다. 예시 import java.util.*; public class Main { public static void main(String[] args) { int n=10; int[] arr = {7, 5, 9, 0, 3, 1, 6, 2, 4, 8}; for (int i=1; i0; j--) { if (arr[j] < arr[j-1]) { int temp = arr[j]; arr[j] = a..

`이것이 코딩 테스트다 (나동빈)` 커리큘럼에 따라 진행합니다 ✨ 정렬 정의 - 데이터를 특정한 기준에 따라 순서대로 나열하는 것 - 일반적으로 문제 상황에 따라 적절한 정렬 알고리즘이 공식처럼 사용된다 ✨ 선택 정렬 정의 - 처리되지 않은 데이터 중에서 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸는 것을 반복하는 정렬 - 이중 반복문을 사용해 가장 작은 원소 확인 -> 데이터 교환의 과정을 반복한다 시간 복잡도 - N번 만큼 가장 작은 수를 찾아 맨 앞으로 보내야 하므로 O(N^2) 만큼의 시간이 소요된다 - N + (N-1) + (N-2) + ... + 2 => (N^2 + N - 2) / 2 ✨ 문제 - 선택 정렬을 사용하지 않지만... 접근 - 좌표 Xi보다 작은 값이 몇 개 있는지 구..

`이것이 코딩 테스트다 (나동빈)` 커리큘럼에 따라 진행합니다 ✨ DFS 정의 - DFS (깊이 우선 탐색) : 깊은 부분을 우선적으로 탐색하는 알고리즘 - 스택 자료구조 또는 재귀 함수를 이용해 문제를 푼다 동작 과정 1. 탐색 시작 노드를 스택에 삽입하고 방문 처리 2. 스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문 처리 -> 방문하지 않은 인접 노드가 없을 경우 스택에서 최상단 노드를 꺼낸다 -> 최상단 노드를 기준으로 깊은 부분을 탐색 3. 더 이상 2번의 과정을 수행할 수 없을 때까지 반복 예시 def dfs(graph, v, visited): visited[v] = True print(v, end=' ') for i in graph[v]: if ..

`이것이 코딩 테스트다 (나동빈)` 커리큘럼에 따라 진행합니다 ✨ 개념 - 재귀 함수 : 자기 자신을 다시 호출하는 함수 - dfs를 실제로 구현할 때 자주 사용하므로 제대로 이해하고 넘어가는게 좋다 - 문제를 풀 때는 재귀 함수의 종료 조건을 반드시 명시해야 한다 ✨ 문제 24060번: 알고리즘 수업 - 병합 정렬 1 첫째 줄에 배열 A의 크기 N(5 ≤ N ≤ 500,000), 저장 횟수 K(1 ≤ K ≤ 108)가 주어진다. 다음 줄에 서로 다른 배열 A의 원소 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 109) www.acmicpc.net 조건 1. N개의 서로 다른 양의 정수가 저장된 배열 A 2. 병합 정렬로 배열 A를 오름차순 정렬 3. 배열 A에 저장되는 K번째 수 구하기 ..

`이것이 코딩 테스트다 (나동빈)` 커리큘럼에 따라 진행합니다 ✨ 개념 스택 - `선입후출` 또는 `LIFO` (Last In First Out) - 먼저 들어온 데이터가 나중에 나가는 형식의 자료구조 - 파이썬 : 별도의 자료구조 없이 리스트를 사용 -> 리스트를 거꾸로 뒤집어 출력 - 자바 : Stack 자료구조 사용 -> push, pop, peek(출력) 메소드 사용 예시 - 박스 쌓기 - 가장 나중에 쌓은 박스부터 들어올려야 한다 - 배열 뒤집기 문제를 풀었는데 새로운 메소드를 알게 되어 추가 for (char c : str.toCharArray()) { } - 문자열에서 하나씩 추출하며 반복(?) 할 때 이런 식으로 사용한다고 한다 Stack q = new Stack(); // 삽입 q.pus..

`이것이 코딩 테스트다 (나동빈)` 커리큘럼에 따라 진행합니다 ✨ 개념 - 구현 : 머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정 - 풀이를 떠올리는 것은 쉽지만 소스코드로 옮기기 어려운 문제 예시 - 알고리즘은 간단한데 코드가 지나칠 만큼 길어지는 문제 - 실수 연산을 다루고, 특정 소수점 자리까지 출력해야 하는 문제 - 문자열 처리 관련 문제 - 적절한 라이브러리를 사용해야 하는 문제 ✨ 문제 17276번: 배열 돌리기 각 테스트 케이스에 대해 회전 연산을 마친 후 배열의 상태를 출력한다. n줄에 걸쳐 각 줄에 n개의 정수를 공백으로 구분하여 출력한다. www.acmicpc.net - 왼쪽 입력, 오른쪽 출력 ✨ 접근 - 2차원 배열로 접근 (좌표) - 가장 가운데 고정 ex) 5 X 5인 경우 (..

`이것이 코딩 테스트다 (나동빈)` 커리큘럼에 따라 진행합니다 ✨ 그리디 알고리즘 (탐욕법) 개념 - 현재 상황에서 지금 당장 좋은 것만 고르는 방법 - 대표적인 알고리즘으로는 "거스름돈" 문제가 있다 - 항상 최적의 값을 보장하는 것은 아니지만 코딩테스트에서 출제하는 문제는 최적의 해를 보장하는 경우로 출제된다 문제 1543번: 문서 검색 세준이는 영어로만 이루어진 어떤 문서를 검색하는 함수를 만들려고 한다. 이 함수는 어떤 단어가 총 몇 번 등장하는지 세려고 한다. 그러나, 세준이의 함수는 중복되어 세는 것은 빼고 세야 한 www.acmicpc.net - 첫째 줄이 문서, 둘째 줄이 검색하고 싶은 단어이다. - 검색하고 싶은 단어가 문서에 몇 개나 있는지 세는 프로그램이다 - 그리디 알고리즘이 사용된..

`Do it! 알고리즘 코딩테스트 : 자바편` 커리큘럼에 따라 공부합니다 ✨ 문제 1546번: 평균 첫째 줄에 시험 본 과목의 개수 N이 주어진다. 이 값은 1000보다 작거나 같다. 둘째 줄에 세준이의 현재 성적이 주어진다. 이 값은 100보다 작거나 같은 음이 아닌 정수이고, 적어도 하나의 값은 0보 www.acmicpc.net 입출력 ✨ 접근 - 자신의 점수 중 최댓값을 골라 점수/최댓값*100으로 고쳐야 한다 1. 최댓값 찾기 2. 개인 점수 구하기 -> for문 돌리며 점수/최댓값*100 계산 3. 평균 구하기 ✨ 풀이 - Java package Week03_01_Array_List; import java.io.BufferedReader; import java.io.IOException; imp..