고오급 개발자가 되는길

두 포인터(Two Pointer) - 화살표 두개의 의미를 부여해서 탐색 범위를 압축하는 방법 1. 1차원 배열 위에 2개의 포인터를 만드는 경우 -1) 2개의 포인터가 모두 왼쪽에서 시작해서 같은 방향으로 이동 - 오른쪽 포인터가 먼저 이동하고 왼쪽이 따라감 -2) 2개의 포인터가 양 끝에서 서로를 향해 이동 -1)↓↓ ↓ ↓ ↓ ↓ 0 1 2 3 4 5 67 7 8 9 10 11 18 19 38 58 72 87 92 66 -2) → ← → ← - 1차원 배열에서의 "연속 부분 수열" or "순서를 지키며 차례대로" - 곱의 최소 부분 합 (백준 1806) - 접근 • 가장 쉬운 방법 O(N^2) 1. 왼쪽 시작 L결정 => O(N) 2. 오른쪽 끝을 R을 L로부터 시작해서 이동 => O(N) 3. 총..

이분 탐색 응용편 매개 변수 탐색 (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 == ..

Homebrew 설치 후 계속 brew 를 찾을 수 없다는 에러가 계속 떳다 원인은 homebrew 가 opt/homebrew/ 로 기본 경로가 설정 되어있어서 이거를 터미널 기본 경로로 바꿔주었다 vi ~/ .zshrc 명령어를 통해 터미널 기본 경로를 설정하여 주었다 참조 : https://miracleground.tistory.com/entry/Mac%EC%97%90%EC%84%9C-Homebrew-%EC%84%A4%EC%B9%98-%ED%9B%84-zsh-command-not-found-brew-%EC%98%A4%EB%A5%98%ED%95%B4%EA%B2%B0

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

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