OILAT

수강한 강의 Part 4. SQL Chapter 02. 문법 설명 - 순위 집계 (rank, dense-rank, row-number) - 조인 (inner, outer, full outer, self, cross) 학습 후기 순위 집계 1. RANK SELECT RANK() OVER(PARTITION BY [그룹할 컬럼들] ORDER BY [순위를 매길 때 사용할 컬럼들]) FROM TABLE 순위를 매길 때 같은 점수가 나오면 같은 등수를 주고 그다음 등수에 같은 등수 바로 다음 등수의 순위가 아닌 같은 등수의 합을 지난 등수를 준다. 예) 1등(100점), 2등(90점), 3등(85점), 3등(85점), 3등(85점), 6등(80점), 7등(79점)... 2. DENSE_RANK SELECT DEN..

수강한 강의 Part 4. SQL Chapter 01. 오리엔테이션 - 강의 목적 및 소개 Chapter 02. 문법 설명 - 기본 검색 및 정렬 (Select, Where, Order by 절) 학습 후기 알고리즘 강의 후 모의 테스트 강의가 있었는데 모의 테스트는 주말에 시간을 내서 한번 풀어보려고 SQL 강의로 넘어왔다. 간혹 코딩 테스트에서 SQL 문제를 내는 곳도 있는데 이번 강의를 통해서 기본적인 SQL 코딩 테스트 준비는 마칠 수 있어서 좋을 거 같다. 해당 강의는 샘플데이터가 주어지고 Postgresql 9.6, DBeaver Community를 사용하여 강의를 진행한다. 문법 설명 SQL 문제 풀이 실습을 위해서 기본적으로 알고 있어야 하는 문법을 설명해 준다. 1. 기본 검색 및 정렬 ..

수강한 강의 Part 3. 알고리즘 유형별 풀이 Chapter 02 알고리즘 - 동적 프로그래밍 (Dynamic Programming) - 3 학습 후기 동적 프로그래밍 그 3번째 시간이다. 여러 동적 프로그래밍 문제를 풀며 동적 프로그래밍의 대표적인 문제 유형을 강의에서 정리해주었다. 1. 문제 크기 N을 변수로 만들어서 표기하는 경우 ex) i를 1, 2, 3의 합으로 표현하는 경우의 수 2. 문제 크기 N과 마지막 상태를 함께 기록해줘야 하는 경우 ex) 계단 오르기 1) Dy[i][0]: i - 1번째 계단을 밟지 않고, i 번째 계단에 도착하며 얻는 최대 점수 2) Dy[i][1]: i - 1번째 계단을 밟고, i 번째 계단에 도착하며 얻는 최대 점수 3. 구간 L ~ R에 대한 문제를 해결할 ..

수강한 강의 Part 3. 알고리즘 유형별 풀이 Chapter 02 알고리즘 - 동적 프로그래밍 (Dynamic Programming) - 2 학습 후기 동적 프로그래밍: 작은 문제로 큰 문제의 해를 구하는 방법 이번 강의에서는 이전 강의에서 동적 프로그래밍 푸는 과정에서 잘못했을 때 어떻게 다시 식을 세워야 하는지 알려주는 강의였다. https://www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 문제 조건 계단의 수 1

수강한 강의 Part 3. 알고리즘 유형별 풀이 Chapter 02 알고리즘 - 동적 프로그래밍 (Dynamic Programming) - 1 학습 후기 동적 프로그래밍(Dynamic Programming)란 문제의 크기를 변화하면서 정답을 계산하는데, 작은 문제의 결과를 이용해서 큰 문제의 정답을 빠르게 계산하는 알고리즘이다. 동적 프로그래밍 시나리오 1. 문제가 원하는 정답을 찾기 위해 가장 먼저 완전 탐색 접근을 시도해 본다. 2. 근데, 완전 탐색 과정에서 탐색하게 되는 경우가 지나치게 많아서 도저히 안 될 경우 3. 모든 경우를 빠르게 탐색하는 방법으로 다이내믹 프로그래밍 접근을 시도해 볼 수 있다. 동적 프로그래밍을 푸는 규격화된 방법 1. 풀고 싶은 가짜 문제를 정의한다. 2. 가짜 문제를 ..

수강한 강의 Part 3. 알고리즘 유형별 풀이 Chapter 02 알고리즘 - 최단 경로 (Shortest Path) 학습 후기 최단거리란 그래프의 시작 지점에서 다른 지점까지의 최단거리 최단거리 알고리즘 이름 간선의 가중치 시작점 도착점 시간복잡도 BFS 모두 1 한 정점 모든 정점 O(V + E) Dijkstra >= 0 한 정점 모든 정점 O(E log V) Floyd-Warshall 제약없음 모든 정점 모든 정점 O(V ^ 3) Bellman-Ford 제약없음 한 정점 모든 정점 O(V * E) SPFA 제약없음 한 정점 모든 정점 O(V * E) A* >= 0 한 정점 한 정점 O(b ^ d) 탐색 = 시작점에서 간선을 0개 이상 사용해서 갈 수 있는 정점들은 무엇인가? DFS/BFS BFS ..

수강한 강의 Part 3. 알고리즘 유형별 풀이 Chapter 02 알고리즘 - 위상 정렬 학습 후기 위상 정렬: Directed Acyclic Graph(DAG) 1. 간선에 방향성이 있다. 2. 사이클이 없다. 3. 그래프로 정점과 간선을 가진다. 차수(degree)란 정점에 연결된 간선의 개수 방향성(Directed)은 Indegree / Outdegree로 구별 정점들을 위상에 맞게 정렬 위상 정렬 해당 문제 - 제일 먼저 올 수 있는 정점은? 들어오는 간선이 없는 정점이다. 정렬 방법 1. 정점들의 Indegree를 계산한다. 2. 들어오는 간선이 0개인 정점을 찾아서 자료구조에 넣는다. 3. 자료구조가 빌 때까지 1) 자료구조에서 원소 X를 꺼내서 정렬한다. 2) 그래프에서 정점 X를 제거한다..

수강한 강의 Part 3. 알고리즘 유형별 풀이 Chapter 02 알고리즘 - 트리 (Tree) 학습 후기 트리: 그래프의 특수한 형태로 그래프 중에서 어떤 특정한 조건을 만족해야 한다. 1. 모두가 연결되어 있는 그래프 - 어떤 두 점을 골라도 간선을 타고 이동 가능 2. 사이클이 존재하지 않음 3. 정점 개수는 간선 개수 + 1이다 이 중 2개 이상의 조건을 만족하는 그래프를 트리라고 한다. Rooted Tree 나무를 뒤집어 놓은 듯한 모양으로 다음과 같은 용어를 알아야 한다. 1. Node: 정점 2. Root: 최 상위 정점 3. Depth: Root를 0으로 자식으로 내려갈수록 +1, Root에서 얼마나 떨어져 있느냐로 볼 수 있다. 4. Parent: 부모 노드, Child: 자식 노드, ..

수강한 강의 Part 3. 알고리즘 유형별 풀이 Chapter 02 알고리즘 - 그래프 탐색 (Graph Search, DFS & BFS) - 응용 편 2 학습 후기 그래프 탐색할 때 BFS를 사용하여 A에서 B까지 갈 수 있는지와 A에서 다른 경로까지의 최소 이동 횟수도 계산 가능하다. 단, 최소 이동 횟수만 말하는 거지 간선에 가중치가 포함되어 있다면 안된다. 최소 이동 횟수, 최단 시간 키워드가 존재하면 사용해볼 만하다. 1. https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.n..

수강한 강의 Part 3. 알고리즘 유형별 풀이 Chapter 02 알고리즘 - 그래프 탐색 (Graph Search, DFS & BFS) - 응용 편 1 학습 후기 격자형 그래프 해당 좌표를 중심으로 상, 하, 좌, 우를 확인해가며 이동할 수 있는 격자인지 확인 이때 중심 좌표를 기준으로 상, 하, 좌, 우 좌표는 {{1, 0}, {0, 1}, {-1, 0}, {0, 1}}을 사용하여 확인한다. https://www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net ..