섹션 3. 코딩테스트 [실전편] - 08. 그래프 - (4) 벨만-포드

🔎 벨만-포드 알고리즘이란? 그래프 최단 거리 구하는 알고리즘 1. 다익스트라(Dijkstra) : 특정 한 정점 -> 다른 모든 정점의 최단 거리 2. 벨만-포드(Bellman-Frod) : 특정 한 정점 -> 다른 모든 정점의 최단 거리 3. 플로이드-와셜(Floyd-Wrasahll) : 모든 정점들 간의 최단 거리 ⬛ 08-5. 벨만-포드 알고리즘 🟦 벨만- 포드 알고리즘 벨만-포드 : 특정 출발 노드에서 다른 모든 노드까지의 최단 경로 탐색 알고리즘 cf. 다익스트라와 다른 점 : 음수 가중치 엣지 있어도 수행 가능 ! 보통 음수 사이클 존재 여부 판별하는 문제가 多 출제 🟧 벨만-포드 핵심 이론 1) 에지 리스트로 그래프 구현 후, 최단 경로 배열 초기화 2) 모든 엣지 확인하며 정답 배열 업데..

• format_list_bulleted 알고리즘 이론 [개념]/[개념] 코테 알고리즘 공부 - 시즌 2
• · 2023. 7. 5.
• textsms

섹션 3. 코딩테스트 [실전편] - 08. 그래프 - (3) - 다익스트라

🔎다익스트라 알고리즘이란? 그래프 최단 거리 구하는 알고리즘 1. 다익스트라(Dijkstra) : 특정 한 정점 -> 다른 모든 정점의 최단 거리 2. 벨만-포드(Bellman-Frod) : 특정 한 정점 -> 다른 모든 정점의 최단 거리 3. 플로이드-와샬(Floyd-Wrasahll) : 모든 정점들 간의 최단 거리 ⬛ 08-4. 다익스트라 🟦 다익스트라 (one - to - All) 다익스트라 알고리즘 : 그래프에서 최단 거리 구하는 알고리즘 특정 노드에서 다른 노드들 간의 최단 거리를 구하는 탐색 알고리즘 엣지가 모두 양수 (cf. 벨만-포드의 경우 엣지 음수도 가능) 시간 복잡도 : O(ElogV) 🟧 다익스트라 알고리즘의 핵심 이론 1) 인접 리스트로 그래프 표현 2) 최단 거리 D[] 배열 초..

• format_list_bulleted 알고리즘 이론 [개념]/[개념] 코테 알고리즘 공부 - 시즌 2
• · 2023. 7. 3.
• textsms

섹션 3. 코딩테스트 [실전편] - 08. 그래프 - (2) -위상정렬

⬛ 08-3. 위상 정렬 🟦 위상 정렬 사이클이 없는 방향 그래프에서 노드 간의 순서 결정하는 알고리즘 사이클이 없어야 한다.(사이클 존재 시, 명확하게 순서 결정 불가능) 🟧 위상 정렬 수행 과정 1) 진입 차수가 0인 노드를 큐에 저장 2) 큐에서 데이터 poll() 후, 결과에 추가. 해당 노드가 가리키는 인접 정점의 진입차수 D[] 의 값 1씩 뺌 3) 감소한 상태의 진입 차수가 0인 경우 다시 Q에 add() 4) 큐가 빌때까지 1~3 반복 🟦 백준 2252번. 줄 세우기 문제 N명의 학생들을 키 순서대로 줄을 세우려고 한다. 각 학생의 키를 직접 재서 정렬하면 간단하겠지만, 마땅한 방법이 없어서 두 학생의 키를 비교하는 방법을 사용하기로 하였다. 그나마도 모든 학생들을 다 비교해 본 것이 아니..

• format_list_bulleted 알고리즘 이론 [개념]/[개념] 코테 알고리즘 공부 - 시즌 2
• · 2023. 6. 28.
• textsms

MySQL | SQL 기본적인 문법 정리

🟦 오름차순 정렬 | ASC select A, B from 테이블 ORDER BY 기준 (ASC); 🟦 내림차순 정렬 | DESC select A,B from 테이블 Order By 기준 (DESC); 🟦 데이터 최대값 가져오기 | MAX (칼럼) SELECT MAX(칼럼) FROM 테이블; 🟦 데이터 최솟값 가져오기 | MIN (칼럼) SELECT MIN(칼럼) FROM 테이블; 🟦 단순 집계 함수 | Count(), SUM(), AVG() select COUNT(*) FROM 테이블; select sum(칼럼) FROM 테이블; select avg(칼럼) FROM 테이블; 🟦 Group별 쿼리 (Group By, Having) Group By (ex. 도시별 인구 합계를 출력하라) select 도, ..

• format_list_bulleted 알고리즘 이론 [개념]/[개념] SQL 기본 문법 정리
• · 2023. 6. 28.
• textsms

섹션 3. 코딩테스트 [실전편] - 08. 그래프 - (1) 이분 그래프, 유니온 파인드

섹션 3. 코딩테스트 [실전편] - 08. 그래프 ⬛ 08. 그래프 그래프는 노드와 엣지로 구성된 집합. 노드는 데이터 표현 단위, 에지는 노드를 연결 ⬛ 08-1. 그래프의 표현 그래프 구현 방식은 크게 3가지가 있다. 🟦 1. 에지 리스트 에지 중심으로 그래프 표현하는 방식이다. 🟧 1) 가중치 X 그래프 표현 배열의 행 2개로 출발노드, 도착노드 표현한다. 🟧 2) 가중치 O 그래프 표현 배열 행 3개로 출발노드 도착노드, 가중치 표현한다. 🟦 2. 인접 행렬 2차원 배열 이용하여 노드 중심으로 표현하는 방식이다. 다만, 에지 탐색 시, N번 접근해야 하므로 노드 개수에 비해서 에지가 적을 때는 공간 효율성 떨어진다. 🟧 1) 가중치 X 그래프 표현 i행 j열에 i → j 표현 🟧 2) 가중치 O ..

• format_list_bulleted 알고리즘 이론 [개념]/[개념] 코테 알고리즘 공부 - 시즌 2
• · 2023. 6. 21.
• textsms

섹션 2. 코딩테스트 - 07. 정수론 -(1) 소수, 오일러 피, 유클리드 호제법

섹션 2. 코딩테스트 - 07. 정수론 ⬛ 07. 정수론 정수론 : 수의 성질 탐구하고 공부하는 이론 분야 실제 코테에서는 모든 정수론 분야가 나오는 것은 아니므로, 가장 많이 등장하는 ‘소수 부분’과 ‘호제법’ 부분을 집중적으로 다뤄보자. ⬛ 07-1. 소수 구하기 🟦 소수 1과 자기 자신 외에 약수가 존재하지 않는 수 소수 판별 방식을 묻는 ‘소수 구하기 문제’ 종종 출제 🟦 대표적인 소수 판별 방식 | ‘에라토스테네스의 체’ 시간 복잡도 : O(N2) 이중 for문 사용하므로.. 🟧 에라토스테네스의 체 방식 구하고자 하는 소수 범위만큼의 1차원 배열[] 생성 for(2~N) : 현재 i의 숫자 선택 → (첫 수 제외) 현재 선택된 i의 배수를 배열 끝까지 탐색하면서 모두 지움 그 다음 지워지지 않은..

• format_list_bulleted 알고리즘 이론 [개념]/[개념] 코테 알고리즘 공부 - 시즌 2
• · 2023. 6. 15.
• textsms

섹션 2. 코딩테스트 - 06. 그리디 알고리즘

섹션 2. 코딩테스트 - 06. 그리디 ⬛ 06. 그리디 알고리즘 ⬛ 06-1. 그리디 알고리즘 🟦 그리디(Greedy) 알고리즘 현재 상태에서 볼 수 있는 최적해가 전체의 최적해라고 가정하며 근시안적으로 보는 알고리즘 전체를 보지 않고, 근시안적 선택(현 상황에서의 부분적 최적해)가 최종 문제의 최적해를 얻는 일이라고 가정하며 답을 찾아가는 알고리즘 항상 최적해를 보장하지는 못한다. 🟧 그리디 알고리즘 수행 과정 1) 해 선택 : 현재 상태의 부분적 최적해 선택 2) 적절성 검사 : 그 최적해가 전체 문제 제약 조건 벗어나지 않는지 검사 3) 해 검사 : 현재까지 선택한 해 집합들이 전체 문제 해결 가능한지 검사. 만약 전체 문제 해결 못한다면 다시 1)로 돌아가 이 과정을 반복 🟦 백준 11047번...

• format_list_bulleted 알고리즘 이론 [개념]/[개념] 코테 알고리즘 공부 - 시즌 2
• · 2023. 6. 14.
• textsms

섹션 2. 코딩테스트 - 05. 탐색 - (2) 이분 탐색

섹션 2. 코딩테스트 - 05. 탐색 - (2) 이분 탐색 ⬛ 05-3. 이진 탐색 🟦 이진 탐색 (=이분 검색) 이진 탐색 : 이미 정렬된 데이터에서 원하는 값을 찾아내는 알고리즘 정렬된 대상 데이터 중앙값 vs 타겟값 비교하여 검색 범위를 절반씩 줄여나감 시간 복잡도 : O(logN) 🟧 이진 탐색 핵심 (1) 이미 정렬된 데이터에서 중앙값 선택 (2) 키값 < 중앙값 : 중앙값의 왼쪽 데이터셋 선택 (3) 중앙값 < 키값 : 중앙값의 오른쪽 데이터셋 선택 (4) 중앙값 == 키값 : break 탈출 🟦 백준 1920번. 원하는 정수 찾기 for문으로 각 타겟 데이터셋 찍으면서 while()문으로 탐색 대상 데이터의 st≤ed 동안 mid 값과 현재 타겟값 비교하며 if, if else 문 통과하면 ..

• format_list_bulleted 알고리즘 이론 [개념]/[개념] 코테 알고리즘 공부 - 시즌 2
• · 2023. 6. 13.
• textsms

섹션 2. 코딩테스트 - 05. 탐색 파트 - (1) DFS, BFS

섹션 2. 코딩테스트 - 05. 탐색 ⬛ 05. 탐색 (= 순회) 그래프의 순회 한 정점에서 시작하여 그래프의 모든 정점을 ‘한 번씩’ 중복 없이 방문하는 것 🏓그래프 순회의 종류 1) DFS (깊이 우선 탐색) 한 정점에서 시작하여 깊이 탐색하다가 다시 직전 정점으로 돌아와 깊이 탐색을 반복 (1) 정점 v 방문 (2) 정점 v에 대한 인접 정점들 中 (1개) 방문 방문 안한 w 존재 O : v 방문처리(push) 후, w 방문 (DFS(v) ) 방문 안한 w 존재 X : 더이상 방문할 w들이 존재하지 않으므로 복귀 pop (3) 스택(DFS) 공백되면 종료 2) BFS (너비 우선 탐색) 시작 정점에 대한 인접 정점들 모두를 차례로 방문하고, 다시 처음 방문했던 정점으로 되돌아와 너비 우선 탐색 반복..

• format_list_bulleted 알고리즘 이론 [개념]/[개념] 코테 알고리즘 공부 - 시즌 2
• · 2023. 6. 8.
• textsms

섹션 2. 코딩테스트 - 04. 정렬 파트

섹션 2. 코딩테스트 - 04. 정렬 ⬛ 04. 정렬 ⬛ 04-1. 버블 정렬 🟦 버블 정렬 두 인접한 요소끼리 비교한 뒤, swap 연산 수행하며 정렬 O(n2) 속도 느린 편 🟦 백준 2750번. 수 정렬하기 -1 문제 N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오. 입력 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 절댓값이 1,000보다 작거나 같은 정수이다. 수는 중복되지 않는다. 출력 첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다. package to_0605_6; import java.util.*; /* 2750번. 수 정렬 하기 1 - 버블 정렬 사용 * */ p..

• format_list_bulleted 알고리즘 이론 [개념]/[개념] 코테 알고리즘 공부 - 시즌 2
• · 2023. 6. 5.
• textsms

섹션 2. 코딩테스트 - 자료구조 (2) 파트

⬛ 03-4. ‘슬라이딩 윈도우’ 알고리즘 🟦 슬라이딩 윈도우 알고리즘 2개의 포인터로 고정 범위 지정한 뒤, 고정 범위를 옆으로 밀면서 이동함. O(n)으로 해결 원할 때 多 사용 크기를 유지한 상태로 이동하면서 조건에 맞는지 유효성 검사하며 탐색함 ⬛ 03-5. 스택과 큐 🟦 스택 (Stack) 삽입/삭제 연산이 후입선출 LIFO 로 이루어지는 자료구조 top 지칭하는 값(한쪽)에서만 삽입과 삭제가 일어남 🟧 스택 용어 1) 위치 top : 삽입과 삭제가 일어나는 위치 지칭 2) 연산 push : top 위치에 새 데이터 삽입 연산 pop : top 위치의 데이터 삭제 & 확인 연산 peek : top 위치의 데이터 단순 확인 연산 🟧 스택 활용 DFS(깊이 우선 탐색), 백트래킹 에서 多 활용 🟦 ..

• format_list_bulleted 알고리즘 이론 [개념]/[개념] 코테 알고리즘 공부 - 시즌 2
• · 2023. 6. 5.
• textsms

섹션 2. 코딩테스트 - 자료구조 (1) 파트

섹션 2. 코딩테스트 [기초] ⬛ 03. 자료구조 ⬛ 03-1. 배열과 리스트 🟦 배열과 리스트 🟧 배열 메모리의 연속 공간에 값이 채워져 있는 형태의 자료구조 각 값은 인덱스를 통해 참조 가능 배열 크기는 최초 선언 시 지정 가능하며, 한 번 선언한 뒤 크기 변경 불가능 🟧 리스트 값과 포인터를 묶은 노드를 다시 포인터로 연결한 자료구조 선언 시 크기 별도 지정 안하므로 크기 정해져 있지 않다. ⬛ 03-2. ‘구간 합’ 알고리즘 합 배열을 이용하여 시간 복잡도를 더 줄이기 위해 미리 구간합을 구해놓는 알고리즘 **** 🟦 구간 합 알고리즘 1차원 배열의 합 배열 S[i] 🟧 1) 합 배열 S의 정의 S[i] = A[0] + A[1] + ... + A[i]; //A[0] ~ A[i]까지의 합 저장 🟧 ..

• format_list_bulleted 알고리즘 이론 [개념]/[개념] 코테 알고리즘 공부 - 시즌 2
• · 2023. 5. 31.
• textsms

섹션 1. 코딩테스트 [준비] 하기 - 시간 복잡도, 디버깅

섹션 1. 코딩테스트 [준비] 하기 ⬛ 01. 시간 복잡도의 중요성 어떤 알고리즘으로 풀어야 하는가 ? 알고리즘 선택의 기준이 되는 ‘시간복잡도’ ⬛ 01-1. 시간 복잡도 표기법 🟦 시간 복잡도 시간복잡도 : 주어진 문제 해결을 위한 ‘연산 횟수’ 기본적으로 1억 번(10의 8승) 의 연산 = 1초의 시간으로 간주한다. 🟦 시간 복잡도의 유형 1) 빅-오메가 : ‘최선’일 때의 연산 횟수 표기법 2) 빅-세타 : ‘보통’일 때의 연산 횟수 표기법 3) 빅-오(O(n)) : ‘최악’일 떄의 연산 횟수 표기법 - 코테에서 사용 ⬛ 01-2. 시간 복잡도 활용하기 연산 횟수 = (알고리즘 시간복잡도) X (데이터 크기) 시간 제한을 확인하여 가능한 연산 횟수의 제한을 두고 생각할 것. 🟦 (1) 시간 제한 ..

• format_list_bulleted 알고리즘 이론 [개념]/[개념] 코테 알고리즘 공부 - 시즌 2
• · 2023. 5. 30.
• textsms

섹션4. Sorting & Thinking - (3)

🎈섹션4. Sorting & Thinking - (3) 🟦 4-5. 모임 장소 문제 풀이 완성 코드 최소거리가 될 중앙점 찾는 게 중요하다. row[] 에 각 학생 행 위치 좌표 담고 col[]에 각 학생 열 위치 좌표 담고 그 각각을 오름차순 정렬해준다. 오름차순 정렬된 인덱스가 갖는 좌표의 값(행, 열) 이 최소 이동 거리 좌표값이 된다. ⇒ 이유 : 모이는 지점이 모든 좌표(가장 밀접한 두 점) 의 중앙에만 위치한다면 (그 사이에만 존재한다면) 그 사이의 어디에서 모여도 최소 이동 거리가 동일하다는 사실을 이용한다. package to_0525_1; // 4-5. 모임 장소 import java.util.*; class Solution { //솔루션 함수 public int solution(int[..

• format_list_bulleted 알고리즘 이론 [개념]/[개념] 코테 알고리즘 공부 - 시즌 2
• · 2023. 5. 25.
• textsms

섹션4. Sorting & Thinking - (2)

🎈섹션4. Sorting & Thinking - (2) 🟦 4-3. 카드 가져가기 문제 풀이 첫 시도 코드 1) 먼저 내림차순 정렬 한 뒤에 2) 기본적으로 영희 우선권이므로 (짝수 번째), 철수는 홀수번째 일텐데 3) k번의 철수 우선권이 존재하므로 각 케이스별 차이를 담을 배열을 생성하고 4) 차이가 클 때 철수가 우선권을 사용할 index값을 따로 담고 그 인덱스값의 2배에서 철수가 (짝수 번째) 값을 누적하여 사용할 수 있게 문제 풀이를 시도했다. → 코드가 꼬여서 마무리를 못했다. import java.util.*; class Solution { public int solution(int[] nums, int k){ int answer = 0; //복붙 ArrayList numsA = new A..

• format_list_bulleted 알고리즘 이론 [개념]/[개념] 코테 알고리즘 공부 - 시즌 2
• · 2023. 5. 24.
• textsms

섹션4. Sorting & Thinking - (1)

🎈섹션4. Sorting & Thinking - (1) 🟦 4-1. 이진수 정렬 문제 풀이 첫 시도 코드 정답은 맞았는데 ,코드가 너무 길고 비효율적이다. 우선 객체를 NumCnt로 생성했다. 이 클래스의 경우 Comparable를 implements해서 내부적으로 compareTo메소드를 재정의할 수 있도록 했다. compareTo() 메소드는 기본적으로 cnt값 기준 오름차순 하되, 만약 두 객체간 cnt 값이 일치할 경우 num의 값 기준 오름차순 정렬이 되도록 재정의했다. 우선 [10진수 → 이진수(String) ] : Integer.toBinaryString() 사용하여 각 nums별로 이진수값을 tmp에 담은 뒤, tmp내부를 탐색하여 ‘1’을 가진 경우에 한해서 OneCnt[i]로 카운팅했다..

• format_list_bulleted 알고리즘 이론 [개념]/[개념] 코테 알고리즘 공부 - 시즌 2
• · 2023. 5. 22.
• textsms

섹션3. 자료구조 활용 섹션 -(4)

🎈섹션3. 자료구조 활용 섹션 -(4) ⬛ 우선순위 큐 | Priority Queue 큐(Queue)는 FIFO 의 형태로 데이터를 처리한다. Priority Queue 는 우선순위를 먼저 결정한 뒤, 그 우선순위가 높은 요소부터 먼저 나가는 자료구조이다. import java.util.PriorityQueue; //import //int형 priorityQueue 선언 (우선순위가 내부 값 오름차순) PriorityQueue priorityQueue = new PriorityQueue(); //int형 priorityQueue 선언 (우선순위가 내부 값 내림차순) PriorityQueue priorityQueue = new PriorityQueue(Collections.reverseOrder()); /..

• format_list_bulleted 알고리즘 이론 [개념]/[개념] 코테 알고리즘 공부 - 시즌 2
• · 2023. 5. 4.
• textsms

섹션3. 자료구조 활용 섹션 -(3)

🎈섹션3. 자료구조 활용 섹션 -(3) 🟦 3-3. 현관문 출입 순서 | 너무 어렵다. . . 이 문제는 큐를 2개 사용하여 대기열을 각각 만든다. prev 변수로 직전 현관문 사용 상태를 (0 or 1) 저장해두고 참고해야 한다. 시간 변수 t 가 하나씩 증가하면서 각 시간 별로 이용 사원을 세팅해야 한다. 완성 코드 package to_0502; /* 3-3. 현관문 출입 순서 | 진짜 개어렵다. .. */ import java.util.*; class Solution1 { //솔루션 함수 public int[] solution(int[] arrival, int[] state){ //들어오는 대기열 Queue enter = new LinkedList(); //나가는 대기열 Queue exit = ne..

• format_list_bulleted 알고리즘 이론 [개념]/[개념] 코테 알고리즘 공부 - 시즌 2
• · 2023. 5. 2.
• textsms

섹션3. 자료구조 활용 섹션 -(2)

🎈섹션3. 자료구조 활용 섹션 -(2) 🟦 3-4. 피부과 문제 풀이 첫 시도 코드 이 문제는 enter 가 최대 100,000 이므로 이중 for문을 돌면 안되는데 도저히 해결 방법이 떠오르지 않아서 이중 for 문 사용하고 답은 나왔다. . package to_0501; /* 3-4. 피부과 문제풀이 -> 이중 for 돌지 않아야 함 ㅠ * */ import java.util.ArrayList; class Person { int inTime; int outTime; Person(int inTime, int outTime){ this.inTime = inTime; this.outTime =outTime; } } class Solution1 { //시간 HH:MM -> M분으로 변경 public int ..

• format_list_bulleted 알고리즘 이론 [개념]/[개념] 코테 알고리즘 공부 - 시즌 2
• · 2023. 5. 1.
• textsms