OILAT

수강한 강의 Part 3. 알고리즘 유형별 풀이 Chapter 02 알고리즘 - 그래프 탐색 (Graph Search, DFS & BFS) 학습 후기 알고리즘에서 그래프 = 정점(Vertex) + 간선(Edge) 간선: 무방향 / 방향 + 가중치 가 있을 수 있음 정점의 차수(degree): 정점 x의 차수는 정점 x에 연결된 간선의 수 모든 정점의 차수의 합 = 간선의 개수의 2배, 이유는 모든 정점의 차수를 더하면 한 간선이 두 번씩 중복해서 더해지므로 2배가 된다. 그래프를 저장하는 방법 1. 인접 행렬: 2차원 행렬로 이어지는 간선이 있는 곳에 1을 표시한다. 0으로 표시되어있다면 연결되어 있지 않다. 가중치 그래프일 경우 0, 1 대신 가중치로 표시하기도 함. O(V^2) 만큼의 공간이 필요하다..

수강한 강의 Part 3. 알고리즘 유형별 풀이 Chapter 02 알고리즘 - 두 포인터 (Two Pointers) - 응용 편 학습 후기 어느덧 챌린지 30일 차가 되었다. 매일 강의를 듣고 블로그에 글을 쓰며 며칠이 지났는지 확인하지 않았지만 오늘 문뜩 글 첫 제목을 쓰는데 30일 차여서 좀 놀랍다. 앞으로 남은 20일 더 힘내서 공부하자 백준 13144번 문제 수열에서 연속한 1개 이상의 수를 뽑았을 때 같은 수가 여러 번 등장하지 않는 경우의 수 정답이 최대치일 때를 생각해본다. 1~10만까지 차례로 늘어나는 배열이라면 모든 구간이 카운트되기에 그때 계수는 50억이므로 Long을 자료형으로 선택한다. 접근법 1. 가장 쉬운 방법 O(N^3) 1) 왼쪽 시작을 L로 결정: 총 O(N) 2) 오른쪽..

수강한 강의 Part 3. 알고리즘 유형별 풀이 Chapter 02 알고리즘 - 두 포인터 (Two Pointers) 학습 후기 두 포인터 - 화살표 두 개에 의미를 부여해서 탐색 범위를 압축하는 방법 1. 1차원 배열 위에 2개의 포인터를 만드는 경우 1) 2개의 포인터가 모두 왼쪽에서 시작하여 같은 방향으로 이동 2) 2개의 포인터가 양 끝에서 시작하여 서로를 향해 이동 2. 문제에 등장하는 변수 2개의 값을 두 포인터로 표현하는 경우 문제에서의 키워드 1차원 배열에서의 연속 부분 수열 or 순서를 지키며 차례대로 곱의 최소 A * B, A가 커지면 B는 작아짐 이런 키워드가 나오면 두 포인터로 접근해볼 만하다. 이번 강의에서 풀어본 문제 https://www.acmicpc.net/problem/18..

수강한 강의 Part 3. 알고리즘 유형별 풀이 - 이분 탐색 (Binary Search) - 응용 편 학습 후기 이분 탐색(Binary Search) 정렬이 보장되는 배열에서 기준 X를 가지고 범위를 이분하면서 탐색하는 방법으로 시간 복잡도는 O(log N)이라고 저번 시간에 배웠다. 이번 시간에는 이분 탐색 응용편인 매개 변수 탐색(Parametric Search)에 대해서 알아본다. 매개 변수 탐색(Parametric Search) 이분 탐색의 아이디어에서 왔으며 배열이 0과 1만 존재하며 오름차순 인건 보장되지만, 전체 배열은 모른다. 특정 인덱스와 값을 O(T)에 계산 가능할 때, 여기서 0과 1의 경계를 찾아야 한다면? 예시 Up-Down 게임 1. A가 1~1000 사이의 어떤 자연수를 선택..

수강한 강의 Part 3. 알고리즘 유형별 풀이 Chapter 02 알고리즘 - 이분 탐색 (Binary Search) 학습 후기 이분 탐색 Left 탐색할 가치가 있는 범위의 왼쪽 끝 인덱스 Right 탐색할 가치가 있는 범위의 오른쪽 끝 인덱스 Reuslt 탐색한 x의 위치 탐색 목표 X이하의 원소 중에 가장 오른쪽에 있는 원소 이분 탐색 자주 하는 실수 1. 입력된 배열에 바로 이분 탐색을 하는데 정렬을 하지 않는 경우 2. L, R, M, Result 변수의 정의를 헷갈려서 부등호 등을 잘못 쓰는 경우 3. L, R 범위를 잘못 설정하거나 Result의 초기값을 잘못 설정하는 경우 이번 강의에서 푼 문제 https://www.acmicpc.net/problem/7795 7795번: 먹을 것인가 먹..

수강한 강의 Part 3. 알고리즘 유형별 풀이 Chapter 02 알고리즘 - 다양한 정렬 응용법 (Sort Application) - 다양한 정렬 응용법 (Sort Application) - 응용법 학습 후기 정렬 오름차순: 1, 2, 3, 4... 뒤로 갈수록 숫자가 커지는 경우 내림차순: 9, 8, 7, 6... 뒤로 갈수록 숫자가 작아지는 경우 알고리즘에서 정렬을 사용하는 포인트 1. 정렬 조건이 필요하다 class Item implements Comparable { public int num; public int idx; @Override public int compareTo(Item o) { return num - o.num; } } compareTo 함수에서 return 값이 음수이면 nu..

수강한 강의 Part 3. 알고리즘 유형별 풀이 Chapter 02 알고리즘 - 어떻게든 푼다. 완전 탐색 (Brute Force) - 응용 편 학습 후기 이전 강의가 완전 탐색 기본이었다면 이번 강의는 조금 더 난이도 있는 문제들이 주어졌다. 문제를 풀 때 다음과 같은 순서로 문제를 푼다. 1. 문제 파악 주어진 문제를 파악하고 어떤 자료형을 쓸지 확인한다. 백준 알고리즘 사이트의 경우 문제 윗부분에 시간제한, 메모리 제한이 나와있고 입력, 출력에 어떤 자료형을 쓸지에 대한 힌트가 있다. 풀기 전에 확인하고 풀자. 2. 문제 스케치하기 문제를 보고 변수를 알맞은 자료형으로 선언해 놓는다. 코드를 작성하기 전에 한 줄 한 줄 주석으로 어떤 기능을 구현할 건지 적어본다. 3. 코드 작성 코드를 작성하면서 ..

수강한 강의 Part 3. 알고리즘 유형별 풀이 Chapter 01 코딩 테스트를 위한 준비 - 강의 소개 및 최종 목표 - 최신 입사 코딩 테스트 분석 - 꿀팁, 좋은 습관 Chapter 02 알고리즘 - 어떻게든 푼다. 완전 탐색 (Brute Force) 학습 후기 이번 강의부터 본격적인 알고리즘 문제를 풀기 시작한다. 코딩 테스트를 위한 준비 강의에서 알고리즘 문제 연습 시 좋은 습관을 알려주었는데 코딩 테스트를 위한 좋은 습관 1. 문제를 올바른 순서로 이해한다. - 문제를 풀기 위해 키보드에 손 올리는 시점은 늦게 - 문제를 제대로 이해하고 - 예제 데이터, 변수 정리 - 키워드가 되는 단어들 체크 2. 시간과 공간 복잡도를 계산한다. - 코드를 직접 짜지 않고도 시간과 공간 복잡도를 계산 - ..

수강한 강의 Chapter 22 자료구조와 알고리즘 정리 - 필수 자료구조와 알고리즘 정리 학습 후기 오늘 강의는 알고리즘 문제를 풀기 전 알아야 하는 기본 지식인 자료구조와 필수 알고리즘 강의를 다 듣고 정리하는 시간을 가졌다. 여태 들었던 강의를 정리해보려고 한다. 자료구조 배열, 큐, 스택, 링크드 리스트, 해쉬 테이블, 트리, 이진 탐색 트리, 힙 알고리즘 정렬: 버블 정렬, 선택 정렬, 삽입 정렬, 병합 정렬, 퀵 정렬 재귀 호출 동적 계획법 분할 정복 탐욕 알고리즘 백트래킹 탐색: 순차 탐색, 이진 탐색 그래프: 너비 우선 탐색(BFS), 깊이 우선 탐색(DFS), 최단 경로 알고리즘(다익스트라 알고리즘), 최소 신장 트리 알고리즘(크루스칼 알고리즘, 프림 알고리즘) 20여 일 동안 알고리즘의..

수강한 강의 Chapter 21 백 트래킹 - 백 트래킹 알고리즘 이해 학습 후기 백트래킹(Backtracking) 백트래킹 또는 퇴각 검색으로 불리며 제약 조건 만족 문제에서 해를 찾기 위한 전략이다. 모든 조합을 시도해서 문제의 해를 찾으며 퇴각 검색을 통해 많은 부분의 조합들을 배제하기에 풀이 시간이 단축된다. 모든 조합을 DFS방식으로 확인하며 조건이 맞지 않으면 포기하고 바로 해가 될만한 곳으로 넘어가서 탐색 용어 Promising: 조건에 맞는지 검사하는 것 Pruning: 가지치기로 조건에 맞지 않으면 포기하고 바로 다음 탐색할 곳으로 옮겨 시간을 절약하는 기법 대표적인 문제: N Queen 대표적인 백트래킹 문제로 NxN 크기의 체스판에 N개의 퀸을 서로 공격할 수 없도록 배치하는 문제로 ..