고오급 개발자가 되는길

이분 탐색 응용편 매개 변수 탐색 (Parametric Search) 1. 정답을 매개변수(Parameter) 로 만들고 Yes/No 문제(결정문제) 로 바꾸기 2. 모든 값에 대해서 Yes/No 를 채웠다고 생각했을 떄, 정렬된 상태인지 확인 3. Yes/No 결정하는 문제를 풀기 => 문제를 거꾸로 푸는것이기 때문에 통찰력을 요구, 많은 훈련이 필요함 자주하는 실수 1. 매개 변수에 대한 결정이 No/Yes 꼴이 아닌데 이분 탐색 하는 경우 2. L, R, M Result 변수의 정의를 헷갈려 부등호 등을 잘못 쓰는 경우 3. L,R 범위를 잘못 설정하거나 Result의 초기값을 잘못 설정하는 경우! 어떠한 경우에 매개변수 탐색을 쓰는것이 좋은가 - ~의 최대값을 구하시오 - ~의 최솟값을 구하시오 ..

이분 탐색(Binary Search) - 정렬이 보장되는 배열에서 기준 x를 가지고 범위를 이분하면서 탐색하는 방법 오름차순이 정렬이된 배열의 특성 - 임의의 M번 인덱스에 있는 배열 A의 A[M]이 기준 X 보다 크다면 A[M...N]은 전부 x 보다 크다. - 임의의 M번 인덱스에 있는 배열 A의 A[M]이 기준 X 보다 작다면 A[1...M]은 전부 x 보다 작다. L : 탐색할 가치가 있는 범위의 왼쪽 끝 인덱스 R : 탐색할 가치가 있는 범위의 오른쪽 끝 인덱스 Result : 탐색한 X의 위치 탐색 목표 : X이하의 원소 중에 가장 오른쪽에 있는 원소 자주하는 실수 1. 입력된 배열에 바로 이분탐색을 하는데, 정렬을 하지 않는 경우 2. L, R, M, Result 변수의 정의를 헷갈려서 부등..

다양한 정렬 응용편(Sort Application) 수열정렬 - N개의원소가P배열에 써있는 값으로 이동하여 B라는 배열을 만듬 static class Elem implements Comparable { public int num, idx; @Override public int compareTo(Elem other) { return num - other.num; } } } static int N; static int[] P; static Elem[] B; static void pro() { Arrays.sort(B); for (int i = 0; i < N; i++) { P[B[i].idx] = i; } for (int i = 0; i < N; i++) { sb.append(P[i]).append(' ')..

다양한 정렬 응용법 정렬이란? - 오름차순이면 크기가 작은것부터 점점 큰 순으로 정렬 - 내림차순이면 크기가 큰것부터 점점 작은 순으로 정렬 1. 정렬 조건이 필요 - 오름차순 이라면 크기가 제일 작은것을 앞으로 이동 시켜야 한다 2. N개의 원소를 정렬하는 것은 O(N logN) 만큼의 시간 복잡도를 가짐 • JAVA의 Arrays.sort(arr) Privitive 원소 정렬 EX) int,double... Object 원소 정렬 Dual-Pivot Quick Sort Tim Sort 최선 시간 복잡도 : O(N) 최선 시간 복잡도 : O(N) 최악 시간 복잡도 : O(N^2) 최악 시간 복잡도 : O(NlogN) 평균 시간 복잡도 : O(N logN) 평균 시간 복잡도 : O(N logN) 3. I..

완전탐색 - 총정리 - 문제를 풀 떄 항상 정답의 최대치를 파악하라! 연산자 끼워넣기 풀이 import java.io.*; import java.util.*; public class Main { static FastReader scan = new FastReader(); static StringBuilder sb = new StringBuilder(); static void input() { N = scan.nextInt(); nums = new int[N + 1]; operators = new int[5]; for (int i = 1; i

어떻게든 푼다! 완전 탐색 - 가장 기본적으로 접근하는 방식이므로 많은 연습이 필요하다 완전탐색이란? - 문제를 해결하기 위해 확인해야 하는 모든 경우를 전부 탐색하는 방법 - 그 중에서도 백트래킹을 통해야 하는 상황 해결 • 모든 코테 문제에서 기본적으로 접근해봐야하므로 많은 연습이 필요하다 장점 : 부분 점수를 얻기 좋다 단점 : 전부 탐색하기에 시간 복잡도가 일반적으로 높다. 1. N개중 중복을 허용하고 순서대로 나열하는 알고리즘 구현 (재귀함수) // 만약 M 개를 전부 고름 => 조건에 맞는 탐색을 한 가지 성공한 것! // 아직 M 개를 고르지 않음 => k 번째부터 M번째 원소를 조건에 맞게 고르는 모든 방법을 시도한다. static void rec_func(int k) { if (k == ..

알고리즘 유형별 문제풀이 실제로 현업에서는 알고리즘 및 자료구조를 사용하지는 않지만 알고리즘으로 코딩 테스트를 보는 이유는? -> 개발이란 무엇인지를 이해하고 있는가에 대해서 알아보는 시간 왜 알고리즘으로 코딩테스트를 하는가?! => 실제 개발자가 하는일과 공통점이 있기 때문 개발자가 하는 일 알고리즘 문제를 푸는 과정 1. 무엇을 만들어야하는지 파악 문제이해 2. 기능성, 효율성을 따져서 만들 방법 찾기 기능성,효율성을 따져 문제가 원하는 정답 구현 3. 프로그래밍을 통해서 직접 구현하기 프로그래밍을 통해서 직접 구현 • 필수 테크닉 - 정렬 - 문자열 처리 - DP(Dynamic Programming) - Dijkstra (다익스트라) - BFS & DFS - 완전 탐색 - 이분 탐색 • 높은 난이도..

자료구조와 알고리즘 정리 자료구조 • 배열 (Array) - 같은 유형의 데이터를 여러개 넣어 관리하는 데이터구조 • 큐 (Queue) - 가장 먼저 넣은 데이터를 가장 먼저 꺼내는 구조 (FIFO) • 스택 (Stack) - 가장 나중에 쌓은 데이터를 가장 먼저 빼낼 수 있는 데이터구조 (LIFO) • 링크드 리스트 (Linked List) - 데이터와 다음 데이터의 주소를 저장하는 공간을 같이 저장하여 중간 데이터 삽입,삭제 시 데이터를 찾아갈 수 있다. - 데이터 저장 단위인 Node와 이전노드와 연결 정보를 가진 포인터로 구성 º 더블 링크드 리스트 (Double Linked List, 이중 연결 리스트) - 양방향으로 연결되어 있어서 노드 탐색이 양쪽으로 모두 가능 • 해쉬 테이블 (Hash T..

백트래킹 (Backtracking, 퇴각 검색) - 제약 조건 만족 문제에서 해를 찾기 위한 전략 - 해를 찾기 위해, 후보군에 제약 조건을 점진적으로 체크 하다가, 해당 후보군이 제약 조건을 만족할 수 없다고 판단 되는 즉시 이 후보군은 체크를 하지 않는다는 표기를 하고, 다른 후보군으로 넘어가 최적의 해를 찾는 방법 - 실제 구현시, 고려할 수 있는 모든 경우의 수(후보군)을 상태 공간트리를 통해 표현 - 상태 공간 트리를 탐색하면서, 제약이 맞지 않으면 해의 후보가 될만한 곳으로 넘어가 탐색 • Promising : 해당 루트가 조건에 맞는지를 검사하는 기법 • Pruning(가지치기) : 조건에 맞지 않으면 포기하고 다른 루트로 바로 돌아서서, 탐색의 시간을 절약하는 기법 대표 문제 • N Que..

프림 알고리즘 (Prim's Algorithm) - 시작 정점을 선택한 후 , 정점에 인접한 간선중 최소 간선으로 연결된 정점을 선택하고, 해당 정점에서 다시 최소 간선으로 연결된 정점을 선택하는방식, - 최소 신장 트리를 확장해가는 방식 구현 1. 임의의 정점을 선택, '연결된 노드 집합'에 삽입 2. 선택된 정점에 연결된 간선들을 간선 리스트에 삽입 3. 간선 리스트에서 최소 가중치를 가지는 간선부터 추출해서, => 최소 Heap , PriorityQueue 사용 - 해당 간선에 연결된 인접 정점이 '연결된 노드 집합'에 이미 들어 있다면, 넘어간다 (사이클 방지) - 해당 간선에 연결된 인접 정점이 '연결된 노드 집합'에 들어 있지 않으면, 해당 간선을 선택하고, 해당 간선 정보를 최소 신장 트리에..