분류 전체보기

문제 바로가기 > 1629번: 곱셈 모듈러 성질과 분할 정복을 이용해 풀 수 있다. 분할 정복아래와 같이 계속해서 지수를 2로 나누어서 분할정복을 계속해서 해나간다.   이때, 지수가 홀수일 때는 마지막에 밑을 곱해주면 된다.    그럼 예제의 A = 10, B = 11 을 위 처럼 적용해보면 이렇다. 위 과정에서 지수는 절반으로 나누기 때문에 각 레벨에서 나뉜 두 지수를 모두 탐색할 필요없이 한 번만 구하면 된다.이를 코드로 옮겨보면 이렇게 짤 수 있다. 아래의 모듈러 공식을 이용해서 long이 오버플로우가 되지 않도록 계속해서 C의 나머지를 구해야 한다.   전체 코드import java.util.Scanner;public class _1629 { public static void main(St..

문제 바로가기 > 1202번: 보석도둑 얼핏보면 냅색 알고리즘이여서 DP를 이용해야 할것 같지만 가방에는 최대 한 개의 보석만 넣을 수 있다는 조건이 있다.그리디 알고리즘과 우선순위 큐를 사용하여 풀 수 있는 문제이다. 모든 가방에 대해 모든 보석을 검사하면 위 문제를 해결할 수 있으나, N과 K는 최대 30만이기때문에 O(9 x 10^10)으로 시간 초과가 난다. 따라서 O(N^2)보다 줄이기 위해서 우선순위 큐 자료구조를 이용해야 한다.보석은 무게에 대해 오름차순 정렬하되, 무게가 같을 경우 가격에 대해 내림차순 정렬한다.가방은 오름차순 정렬한다.모든 가방에 대해서 반복문을 수행한다.특정 가방의 무게보다 작은 보석의 가격을 모두 우선순위 큐에 집어넣는다. (이때, 우선순위 큐는 가격에 대해 내림차순 ..

문제 바로가기 > 12865번: 평범한 배낭 전형적인 0/1 냅색 알고리즘으로, DP로 풀 수 있다. 1. 초기화최대 무게 K를 수용할 수 있는 dp 배열을 선언하고, 크기를 K + 1로 설정하여 모든 인덱스를 0으로 초기화dp[j]는 무게 j일 때의 최대 가치를 저장2. 동적 프로그래밍을 통한 최대 가치 계산각 물건에 대해 반복을 수행, 물건의 무게를 weight, 가치를 valuedp 배열을 역순으로 갱신: 이는 각 물건을 한 번만 고려하도록 하여 중복을 방지dp[j] (무게 j에서의 최대 가치)는 dp[j] (현재 가치)와 dp[j - weight] + value (현재 물건을 추가했을 때의 가치) 중 더 큰 값으로 갱신j는 K부터 weight까지 감소하면서 계산3. 결과 출력dp[K]에 저장된 값..

https://www.codetree.ai/training-field/search/problems/series-of-bombs-detonating/description?utm_source=clipboard&utm_medium=text&page=9&pageSize=5 코드트리 | 코딩테스트 준비를 위한 알고리즘 정석국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요.www.codetree.ai  완전탐색, 시뮬레이션 문제이다. 1. 입력 받기: 폭탄의 개수와 각 폭탄의 위치를 입력 받는다.이때, 폭탄의 위치 인덱스를 배열에 저장하는데 이유는 폭탄의 위치 N이 최대 1,000,000,000까지이므로 예를 들어 boolean[] isBom..

분리 집합분리집합이란 서로 공통된 원소를 가지고 있지 않은 두 개 이상의 집합, 즉 서로소 집합이다. 따라서 A ∩ B = Ø가 성립된다. 유니온 파인드이러한 분리집합은 유니언 파인드 자료구조를 사용한다.  Find 연산각 트리셋의 자식 노드가 루트(최상위 노드)를 찾는 과정find(x)찾는 노드에 들어있는 대표 노드로 감x와 x의 부모가 같다면 x를 리턴그렇지 않다면 재귀적으로 find를 수행x의 x의 부모가 같다면 그 노드는 루트 노드이다.public int find(int x) { if (x == parent[x]) return x; return parent[x] = find(parent[x]);} Union연산한 트리셋의 루트가 다른 트리셋의 루트를 가르키게 하여 트리를 병합하는 과정Union(x..

문제 바로 가기 > 백준 20366번: 같이 눈사람 만들래? 정렬을 이용해 푸는 문제이다. 처음에는 아래와 같이 4중 for문을 이용해 풀려고 했으나 이렇게 풀면 N(4 ≤N≤ 600) 이여서 시간 초과가 난다.엘사가 만든 눈사람의 몸통 선택 → O(N)엘사가 만든 눈사람의 머리 선택 → O(N)안나가 만든 눈사람의 몸통 선택 → O(N)안나가 만든 눈사람의 머리 선택 → O(N)엘사가 만든 눈사람과 안나가 만든 눈사람의 키차이를 구하고 최소 비교➡️ 해당 풀이법의 시간 복잡도 : O(N4) → 시간 초과 그래서 몸통+머리를 합쳐서 눈사람을 우선 만들어서 정렬한 후에 이 눈사람의 뒷값과 비교를 한다.핵심은 정렬을 했기 때문에 현재 눈사람과의 차이가 가장 작은 눈사람은 내 바로 뒤의 인덱스에 있는 눈사람이..

플로이드 워셜 알고리즘이란?플로이드-워셜 알고리즘은 모든 정점에서 다른 모든 정점까지의 최단 경로를 모두 구하는 알고리즘이다. 따라서 2차원 테이블에 최단 거리 정보를 저장한다.  다익스트라벨만-포드플로이드-워셜경로계산방식One-To-AllOne-to-OneAll-to-All음의 가중치XOO음수 사이클XXX최단거리테이블1차원테이블1차원테이블2차원테이블다른 알고리즘 포함그리디-DP 경로 계산 방식에는 아래와 같은 종류가 있다. 1. (One-To-One) 한 지점에서 다른 특정 지점까지의 최단경로 구하기 ->벨만-포드 알고리즘  2. (One-To-All) 한 지점에서 다른 모든 지점까지의 최단경로 구하기 ->다익스트라 알고리즘3. (All-To-All) 모든 지점에서 모든 지점까지의 최단경로 구하기 ->..

벨만-포드 알고리즘이란? 벨만-포드 알고리즘은 다익스트라 알고리즘과 마찬가지로 한 정점에서 다른 모든 정점까지의 최단 경로를 구하는 알고리즘이다. 이때, 다익스트라와 달리 간선의 가중치가 음수인 경우에도 최단 거리를 구할 수 있다. 음의 사이클이 없고 한 노드에서 다른 노드까지의 최단 경로를 많아봐야 V-1개의 간선을 지난다는 가정에서 시작된다. 다익스트라 알고리즘에 비해 효율이 떨어지지만 더 많은 그래프에 대해서 정확한 답을 구할 수 있다.  다익스트라벨만-포드음수 가중치XO음수 사이클XX시간복잡도O(mlog n)O(mn)❗️벨만-포드가 가중치가 음수인 경우에도 최단 거리를 구할 수 있는 이유다익스트라 알고리즘에서는 매번 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택해서 1단계씩 최단 ..

다익스트라 알고리즘이란?다익스트라 알고리즘은 기본적으로 greedy와 dp를 사용한 알고리즘으로 그래프의 최단 경로를 구하는 알고리즘이다. 하나의 정점에서 출발하는 최단 거리를 구하는 것이다.  이때 간선의 가중치는 양수여야 한다. 인접 행렬로 표현된 그래프의 경우 시간 복잡도 O(n^2)이지만 우선순위 큐를 사용하면 시간 복잡도 O(mlog n)까지 낮출 수 있다.  음의 가중치를 가지면 안되는 이유 다음과 같은 경우에 다익스트라 알고리즘은 A->B->D 총 비용 22가 가장 최소 경로라고 생각 할 것이다. (A-B-DB->C->D가 총-90 으로 값이 더 작다. 즉, 위와 같이 음의 가중치가 포함된 그래프의 최단 경로는 다익스트라 알고리즘으로 구할 수 없는 경우가 있다. 동작 과정출발지에서 인접한 노..

✔️ Comparable목적: 자기 자신과 매개변수 객체를 비교구현 방법: Comparable 인터페이스를 구현하는 클래스는 compareTo 메서드를 오버라이드import java.util.*;class Person implements Comparable { private String name; private int age; public Person(String name, int age) { this.name = name; this.age = age; } public String getName() { return name; } public int getAge() { return age; } @Overrid..