고오급 개발자가 되는길

순서대로라면 모의고사를 먼저 진행하고 SQL을 진행해야하지만 실제로 문제를 풀어보고 강의를 듣기 위해 주말에 정확한 시간을 재며 모의고사 강의를 들어봐야겠다 ㅠ SQL 강의 SQL 문법 1. Select [컬럼명들] (","를 통해서 구분) 2. FROM [테이블명] 3. WHERE [조건들] (조건 검색, and, or 연산자들을 통해서 구분) 4. ORDER BY [컬렴명들] (정렬 기능 "," 를 통해서 구분) EX) SELECT CNAME, CADDR FROM tCustomer as tcu WHERE CADDR = "남구" ORDER BY CNAEM ASC -> tCsutomer테이블을 tcu라고 명칭하고 해당 테이블에서 CADDR이 남구인 검색조건에서 CNAME, CADDR 컬럼만 추출하여 오름..

모의 코딩 테스트 풀이 1 홀수 홀릭 호석 (BOJ 20164) - 완전 탐색 (재귀 함수가 제일 좋다) - 함수 디자인 1. 매 순간 들고 있는 수 : x 2. 시작부터 지금까지 얻은 점수, total_odd_cnt 재귀함수 조건 1. 종료 조건 -> x가 한자리 수인 경우 2. 아닌 경우 -> 가능한 경우로 모두 잘라서 다음 수에 대해 재귀 호출 별도 함수 - 수에 포함된 홀수의 개수를 계산해주는 함수 구현 static int N, ans_min, ans_max; static PrintWriter out = new PrintWriter(System.out); static void pro(){ ans_min = 0x7fffffff; ans_max = 0; // 시작하는 순간에는 N 이라는 숫자와, 여기..

동적 프로그래밍 3 😢 파일 합치기 (BOJ 11066) 1. 각자의 크기가 존재하는 파일들이 순서대로 존재한다. 2. 연속한 두 파일을 하나로 합치면, 합친 크기 만큼의 비용이 필요하다. 3. 전체 K개의 파일들을 하나로 합치는 방법들 중에서 총 비용의 최솟값을 계산하라. 점화식 구해내기 (i = 짜르기 시작한 부분, K는 i 이후 자른 시작 부분, j는 마지막 부분) - Dy[i][j] = min { Dy[i][k] + Dy[k+1][j] + (i~j 파일 총량) (i

동적 프로그래밍(Dynamic Programming) - 2 계단 오르기 (BOJ 2579) 1. 계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 즉, 한계단을 밟으면서 이어서 다음 계단이나 다다음 계단으로 오를 수 있다. 2. 연속된 세계의 계단을 모두 밟아서는 안된다. 단, 시작점은 계단에 포함되지 않는다. 3. 마지막 도착 계단은 반드시 밟아야 한다. 완전 탐색 접근을 통해서 모든 경우를 직접 하나하나 찾으면 경우의수가 너무 많기 때문에 동적 프로그래밍 으로 문제를 나누어서 탐색한다. 문제 파티셔닝 - 마지막에 1칸을 올랐을 경우 => (i-1) 번째 직전에 (i-2) 번째 계단도 밟았는가? (연속된 세번 계단을 오를수 없기 때문) - 마지막에 2칸을 올랐을 경우 가짜문제 정의 - 필요한..

동적 프로그래밍 (Dynamic Programming) 1 - 문제의 크기를 변화하면서 정답을 계산하는데, 작은 문제의 결과를 이용해서 큰 문제 해결 동적 프로그래밍 풀이 방식 1. 풀고 싶은 가짜 문제 정의 2. 가짜 문제를 풀면 진짜 문제를 풀 수 있는가? 3. 가장 작은 문제 해결하기 4. 3)에서 계산 한 것을 기반으로, 점점 더 큰 문제 해결하기 5. 1~4) 가 성공적으로 끝난다면 진짜 문제 해결하기 1,2,3 더하기 (BOJ 9095) - 정수 n이 주어졌을떄, n을 1,2,3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성 접근1 : 풀고싶은 가짜 문제 정의 - 진짜 문제를 써 본후 가짜 문제로 정의한다 - Dy[i] = i 를 1,2,3의 합으로 표현하는 경우의 수 접근2 : 가짜 ..

최단 경로 (Shortest Path) 최단 거리란? - 그래프의 시작점에서 다른 지점 까지의 최단 거리 EX) 네비게이션 1. BFS - 간선의 가중치 모두 1 - 시작점은 한 정점 - 도착점은 모든 정점 - 시간 복잡도 O(V+E) 2. Dijkstra - 간선의 가중치 모두 0 이상 - 시작점은 한 정점 - 도착점은 모든 정점 - 시간 복잡도 O(ElogV) 필요한 정보 - dist[i] : 시작점에서 i번 정점까지 가능한 최단 거리 => 다익스트라 알고리즘이 한번 돌떄마다 배열이 채워짐 - 자료구조 D : 시작점에서 v까지 d만에 갈 수 있음을 확인 구현 순서 1. dist 배열 초기화, dist[i] = o if i == S , else 2. D에 (S,0)을 추가한다 3. min(v,d), D..

위상 정렬 (Topological Sort) - 정점들을 위상에 맞춰 정렬 • DAG (Directed Acyclic Graph) Directed = 간선에 방향성이 있다 Acyclic : 싸이클이 없다 Graph = 정점 + 간선 Indegree : 자신(정점) 에 들어오는 개수 (차수) Outdegeree : 자신에서 나가는 간선의 개수(차수) 제일 먼저 올 수 있는 정점은? => 들어오는 간선이 없는 정점 정리 1. 정점들의 Indegree, Indeg[1...N] 계산하기 2. 들어오는 간선이 0개인 (indeg[i] ==0) 정점들을 찾아서 자료구조 D에 넣기 3. D가 빌 떄 까지 1. D에서 원소 X를 꺼내서 정렬 시키기 2. Graph 에서 정점 X 제거하기 3. 새롭게 정렬 가능한 점을 ..

트리 (Tree) - 그래프의 특수한 형태 - V + E + 특성 특성 1. - 모두가 연결되어 있는 그래프 - 어떤 두 점을 골라도 간선을 타고 사이를 이동 가능 특정 2. - 사이클이 존재하지 않음 특성 3. - 정점 개수 v = 간선 개수 e + 1 특성중 2가지를 만족하면 트리로 문제 풀이 Rooted Tree란? 1. Node 2. Root 3. Depth 4. Parent, Child, Ancestor(조상),Sibling(형제, 같은 부모를 갖는 관계) 5. Leaf Node (자식이 없는 노드) - 모든 두 정점 사이에 이들을 잇는 경로가 존재하면서 사이클이 존재하지 않는 경우 - 마을과 마을 사이를 직접 잇는 N-1 개의 길이 있으며, 모든 마을은 연결되어있다 (1,3 만족) 트리는 인접..

그래프와 탐색 그래프란? - 자료구조로써 그래프 = 정점 (Vertex) + 간선 (Edge) • 간선 (Edge) : 무방향 / 방향 을 나타내는 선, 가중치를 가질수도 있다 - degree = 정점 x의 차수, 정점 x에 연결된 간선의 수 모든 정점의 차수의 합 = 간선의 개수의 2배 그래프를 저장하는 대표적인 두 가지 방법 1. 인접 행렬 (Adjacency Matrix) - 그래프를 2차원 배열로 표현하는 방법 => 0이면 두 정점을 연결하지 않는다, 1이면 두 정점이 연결 되어있다 - int[][] adj = int new[V][V]; - O(V^2) 만큼의 공간 필요, 하지만 실제로 1인 대상은 얼마 없으므로 공간 낭비 - A와 B를 잇는 간선 존재 여부 확인 문제에서 사용 2. 인접 리스트 ..

투 포인터 응용 List of Unique Numbers (BOJ 13144) 난이도 4 - 수열에서 연속한 1개 이상의 수를 뽑았을 떄 같은 수가 여러번 등장하지 않는 경우의 수 정답의 최대치 구현 static int N; static int[] A, cnt; static void pro() { long ans = 0; for (int L=1, R=0; L