나다김강니

2차원 배열 정렬하는 방법백준 10814번을 풀면서 2차원 배열을 정렬하는 문제가 나왔다.💡 Arrays.sort와 Comparator를 활용한 배열 정렬배열에는 아래와 같이 데이터가 들어있다.arr[i][0]를 기준으로 정렬해야한다.String[][] arr = { {"21", "Junkyu"}, {"21", "Dohyun"}, {"20", "Sunyoung"}};  2차원 배열의 경우, 특정 열(column)을 기준을 정렬하려면 Comparator을 사용해야한다.compare메소드는 두 개의 매개변수를 비교한다. o1과 o2는 비교 대상 배열의 두 행을 나타낸다.여기서는 두 행의 0번째 요소를 비교한다.Arrays.sort(arr, new Comparator() { @Over..

11689 : GCD(n, k)문제자연수 n이 주어졌을 때, GCD(n, k) = 1을 만족하는 자연수 1 ≤ k ≤ n 의 개수를 구하는 프로그램을 작성하시오. 입력첫째 줄에 자연수 n (1 ≤ n ≤ 1012)이 주어진다. 출력GCD(n, k) = 1을 만족하는 자연수 1 ≤ k ≤ n 의 개수를 출력한다.입력출력11544524 문제 풀이오일러피로 푸는 문젠데 강의에 나온 이론으로 풀면 자꾸 런타임에러나는거;; 💡 오일러 피 구하는 다른 방법 - 소인수분해 사용 N 에서 소인수를 찾아내고 𝝓(n) 값을 갱신한다.소인수의 배수를 제거하여 N을 점점 작게 만든다.N이 소수로 남아잇다면, 𝝓(n) 값을 최종적으로 갱신한다.(예시)N = 36, res = 36소인수 확인 및 처리(N%i==0 확인, N..

DP(Dynamic Programming)복잡한 문제를 간단한 여러 개의 문제로 분리하여 부분의 문제들을 해결해 최종적으로 복잡한 문제의 답을 구한다. 💡 동적 계획법(DP)의 핵심 이론1️⃣  동적 계획법의 원리와 구현 방식 큰 문제를 작은 문제로 나눌 수 있어야 한다.작은 문제들이 반복돼 나타나고 사용되며 이 작은 문제들의 결과값은 항상 같아야 한다.모든 작은 문제들은 한 번만 계산해 DP테이블에 저장하며 추후 재사용할 때는 이 DP 테이블을 이용한다.-> 메모이제이션 기법동적 계획법은 톱-다운 방식(top-down)과 바텀-업(bottom-up) 방식으로 구현할 수 있다. 2️⃣  피보나치 수열(동적 계획법의 가장 대표적인 문제)피보나치 수열 공식D[N] = D[N-1] + D[N-2] 동적 계..

조합조합은 nCr로 표현되고, n개의 숫자 중 r개를 뽑는 경우의 수를 뜻한다.순열은 nPr로 표현되고, n개의 숫자 중 r개를 뽑아 순서를 고려해 나열할 경우의 수를 말한다. 💡 순열과 조합의 핵심 이론🔍  순열예를 들어, 5개중 순열을 이용해 3개를 뽑으면 (5*4*3*2*1)/(2*1)의 결과값이 나온다.  🔍  조합예를 들어, 5개중 조합을 이용해 3개를 뽑으면 (5*4*3*2*1)/(2*1)/(3*2*1)의 결과값이 나온다.(2*1) -> 순서가 다른 경우의 수를 제거하는 역할  ☝🏻  조합 점화식 세우기1️⃣ 특정 문제를 가정하기5개의 데이터에서 3개를 선택하는 조합의 경우의 수 구하기 2️⃣ 모든 부분 문제가 해결된 상황이라고 가정하고 지금 문제 생각하기먼저 5개의 데이터 중 4개는 ..

LCA(최소 공통 조상)트리 그래프에서 임의의 두 노드를 선택했을 때 각각 자신을 포함해 거슬러 올라가다 처음 공통으로 만나게 되는 부모 노드 💡 최소 공통 조상의 핵심 이론ⓐ 일반적인 최소 공통 조상 구하기트리의 높이가 크지 않을 때는 일반적인 방법으로 구한다. 1️⃣ 루트 노드에서 탐색을 시작해 각 노드의 부모 노드와 깊이를 저장한다. 2️⃣ 만약, 선택된 두 노드의 깊이가 다른 경우 더 깊은 노드의 노드를 부모 노드로 1개씩 올려주면서 depth를 맞춰준다. 3️⃣ 깊이가 같은 상태에서는 동시에 부모 노드로 올라가면서 두 노드가 같은 노드가 될 때까지 반복한다.     이때 처음 만나는 노드가 최소 공통 조상이 된다.  ⓑ 최소 공통 조상 빠르게 구하기트리의 높이가 매우 커질 경우, 시간 제약 문..

세그먼트 트리주어진 데이터의 구간 합과 데이터 업데이트를 빠르게 수행하기 위해 고안해낸 자료구조이다.더 큰 범위로 '인덱스 트리'라고 불린다. 💡 세그먼트 트리의 핵심 이론세그먼트 트리의 종류는 구간 합, 최대 · 최소 구하기로 나눌 수 있다. 1. 트리 초기화하기리프 노드의 개수가 데이터의 개수(N)이상이 되도록 트리 배열을 만든다.트리 배열 크기 구하기 : 2k ≥ N을 만족하는 k의 최솟값을 구하고 2k x 2를 트리 배열의 크기로 정의한다.그리고 주어진 데이터들을 2k에 해당하는 인덱스부터 채운다. 만약, 8개의 데이터가 주어졌을 때는 {5, 8, 4, 3, 7, 2, 1, 6}2의 제곱수 중 처음으로 8보다 크거나 같아지는 제곱수를 구한다 -> k=3배열의 크기는 23 x 2 = 16배열을 채..

이진 트리이진 트리는 각 노드의 자식 노드(차수)의 개수가 2 이하로 구성된 트리를 말한다. 💡 트리의 핵심 이론이진 트리의 종류데이터를 트리 자료구조에 저장할 때 편향 이진 트리의 형태로 저장하면 탐색 속도가 저하되고 공간이 많이 낭비 된다.일반적으로 코테에서 데이터를 트리에 담는다고 하면 완전 이진 트리 형태를 떠올린다.  이진 트리의 순차 표현이진 트리는 아래와 같이 1차원 배열의 형태로 표현할 수 있다.자식 노드 인덱스 = 부모 노드 인덱스 x 2, 부모 노드 인덱스 x 2 + 1 구성 요소인덱스 연산제약 조건(N = 노드 개수)루트 노드index = 1 부모 노드index = 자식 노드 인덱스 / 2현재 노드가 루트 노드가 아님왼쪽 자식 노드index = 부모 노드 인덱스 x 2index * ..

트리트리는 노드와 에지로 연결된 그래프의 특수한 형태이다.순환 구조(사이클)를 지니고 있지 않고, 1개의 루트 노드가 존재한다.루트 노드를 제외한 노드는 단 1개의 부모 노드를 가진다.트리의 부분 트리 역시 트리의 모든 특징을 따른다. 💡 트리의 핵심 이론구성 요소설명노드데이터의 index와 value를 표현하는 요소에지노드와 노드의 연결 관계를 나타내는 선루트 노드트리에서 가장 상위에 존재하는 노드부모 노드두 노드 사이의 관계에서 상위 노드에 해당하는 노드자식 노드두 노드 사이의 관계에서 하위 노드에 해당하는 노드리프 노드트리에서 가장 하위에 존재하는 노드(자식 노드가 없는 노드)서브 트리전체 트리에 속한 작은 트리  💡 코딩테스트에서 트리가 나오는 유형① 그래프로 푸는 트리(DFS, BFS)② 트..

최소 신장 트리(MST)최소 신장 트리란 그래프에서 모든 노드를 연결할 때 사용된 에지들의 가중치의 합을 최소로 하는 트리사이클이 포함되면 가중치의 합이 최소가 될 수 없다. -> 사이클을 포함하지 않는다.N개의 노드가 있으면 최소 신장 트리를 구성하는 에지의 개수는 항상 N-1개이다.최소 신장 트리 대표 알고리즘 : 크루스칼, 프림 💡 최소 신장 트리의 핵심 이론1. 에지 리스트로 그래프를 구현하고 유니온 파인드 리스트 초기화하기데이터를 노드가 아닌 에지 중심으로 저장한다. 그래서 인접 리스트가 아닌 에지 리스트의 형태로 저장한다.유니온 파인드 리스트도 함께 초기화한다. 자신의 인덱스 값으로 초기화한다.  2. 그래프 데이터를 가중치 기준으로 정렬한다.에지 리스트에 담긴 그래프 데이터를 가중치 기준으..

플로이드-워셜그래프에서 최단 거리를 구하는 알고리즘(다익스트라, 벨만-포드, 플로이드-워셜)모든 노드 간에 최단 경로 탐색 -> 시작 노드가 따로 정해져있지 않다.음수 가중치 에지가 있어도 수행 가능하다. 다만, 사이클이 있으면 안된다.동적 계획법의 원리를 이용해 알고리즘에 접근한다.시간 복잡도는 O(V3)   노드가 1000개이면 시간초과가 일어날 확률이 높다.💡  플로이드-워셜 핵심 이론A노드에서 B노드까지 최단 경로를 구했다고 가졍했을 때 최단 경로 위에 K노드가 존재한다면 그것을 이루는 부분 경로 역시 최단 경로 🔍 도출한 플로이드-워셜 점화식     D[S][E] = Math.min(D[S][E], D[S][K] + D[K][E]) 1. 리스트를 선언하고 초기화하기D[S][E]는 노드 S에서..