알고리즘 및 코테 복습 - DP 동적 계획법

⬛ 11. DP 동적 계획법 ⬛ DP 접근 방식 점화식의 규칙성이 존재해야 한다. 점화식 세우기 : D[i] 배열의 제대로 된 정의 점화식을 이용하여 D[i] 배열 채우기 D[N] 을 출력하면 == 정답이어야 한다. ⬛ 메모이제이션의 이해 앞선 부분 문제 푼 결과를 DP 테이블에 저장해둔 뒤, 재사용 할 것 톱 다운 방식 : 주로 재귀함수 : 큰 문제부터 점차 작은 문제로 바텀-업 방식 : 주로 반복문 : 작은 문제부터 큰 문제로 확장 ⬛ 0-1 배낭 문제 0-1 배낭 문제 : 물건을 통째로 배낭에 넣는데, 담을 수 있는 한 ‘최대 가치 낳도록 담는 문제 풀어볼 문제 : 동전 1, 동전 2, 평범한 배낭문제 등. 🟦 백준 4781번. 사탕 가게 | DP- 배당문제 (냅색) 문제 상근이는 선영이와 걸어가다..

• format_list_bulleted 알고리즘 이론 [개념]/[복습] 코테_알고리즘 복습
• · 2023. 7. 25.
• textsms

알고리즘 및 코테 복습 - 그래프(Graph)

⬛ 08. 그래프 ⬛ 08-1. 그래프의 표현 에지 리스트 : 엣지 중심으로 그래프를 표현 인접 행렬 : 노드 중심으로 그래프를 표현 인접 리스트 : 노드 중심으로 그래프를 표현 **** ⬛ 08-2. 유니온 파인드 특정 2개의 노드 연결 union 하고, 집합 여부 판별 find 하기 특정 2개의 노드를 연결하여 1개의 집합으로 묶은 Unioin연산, 두 노드가 같은 집합 소속인지 확인하는 Find 연산 ⚫ 백준 1717번. 집합의 표현 https://www.acmicpc.net/problem/1717 1717번: 집합의 표현 초기에 $n+1$개의 집합 $\{0\}, \{1\}, \{2\}, \dots , \{n\}$이 있다. 여기에 합집합 연산과, 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연..

• format_list_bulleted 알고리즘 이론 [개념]/[복습] 코테_알고리즘 복습
• · 2023. 7. 24.
• textsms

알고리즘 및 코테 복습 - 그리디 (Greedy)

⬛ 06. 그리디 ⬛ 06-1. 그리디 알고리즘 현재 상태에서 보는 선택지 중 최선의 선택지를 전체 선택지의 최선이라고 가정하는 알고리즘 그리디 알고리즘 적용 직전에 대상 데이터들을 (오름차순/내림차순) 정렬해두는 경우 多 현재 기준값을 기준으로 비교하고, 비교 한 뒤 현재의 기준값이 계속 갱신되는 행위 반복하는 것 ! ⬛ 그리디 접근 방식 1) 객체화 시켜서 각 필드의 값들에 대하여 객체의 compareTo 사용하여 정렬시키고, 최초 0번 값을 기준값으로 하여 비교한 뒤, 기준값 갱신시키는 방식 ex) 신입사원 class Sawon implements Comparable{ //필드 ... //생성자 ... @Override public int compareTo(Sawon o) { return 조건 };..

• format_list_bulleted 알고리즘 이론 [개념]/[복습] 코테_알고리즘 복습
• · 2023. 7. 18.
• textsms

알고리즘 및 코테 복습 - DFS, BFS, 이진 탐색

⬛ 05. 탐색 그래프의 순회 (=탐색) 현재 정점 처리 후 다음 처리할 정점에 대한 순서가 필요 한 정점에서 시작하여 그래프의 모든 정점을 한 번씩만 방문할 것. ⬛ 05-1. 깊이 우선 탐색 | DFS DFS는 한 번씩만 방문해야 하므로 visited[] 방문 체크 배열 필요하며 인접 리스트로 표현 🟦 백준 11724번. 연결 요소의 개수 구하기 DFS로 깊이 방문 하다가 복귀하는 게 한 덩어리 단위임 import java.util.ArrayList; import java.util.Scanner; /*11724번. 연결 요소의 개수 */ public class Main { static int N, M; static boolean[] visited; static ArrayList graph; //dfs..

• format_list_bulleted 알고리즘 이론 [개념]/[복습] 코테_알고리즘 복습
• · 2023. 7. 17.
• textsms

알고리즘 및 코테 복습 - 구간합, 투포인터, 스택과 큐

⬛ 03. 자료 구조 ⬛ 03-2. 구간 합 S[i] = S[i-1] + A[i] i ~ j까지의 구간 합 구하기 : S[j] - S[i-1] 🟦 백준 11659번. 구간 합 구하기 S[i] 는 1~i까지의 합 : 먼저 구해놓고, M개의 입력받은 구간 a,b 사잇 구간합을 구해서 출력 import java.util.ArrayList; import java.util.Scanner; //11659번. 구간 합 구하기 4 public class Main { //실행 메인 public static void main(String[] args) { // TODO Auto-generated method stub Scanner kb= new Scanner(System.in); int N = kb.nextInt(); i..

• format_list_bulleted 알고리즘 이론 [개념]/[복습] 코테_알고리즘 복습
• · 2023. 7. 17.
• textsms