Log

쉬워 보였지만 생각보다 까다로운 문제였다. 0부터 시작해서 N번째 감소하는 수를 찾는 문제. 우선 문제에도 나와있다시피 0은 0번째 감소하는 수, 1은 1번째 감소하는 수이므로 10미만의 입력은 자기 자신이 n번째 감소하는 수가 된다. // 10보다 작은 수는 무조건 감소하는 수 if(N < 10) { System.out.println(N); return; } 그러면 N이 10 이상인 수에 대해서만 몇번째 감소하는 수인지 아닌지 확인하면 된다. 우선 어떤 수가 감소하는 수인지 아닌지를 확인하는 코드가 필요하다. 나는 일의자리부터 마지막자리까지 숫자가 커지지 않으면 false값을, 전부 다 커지는 숫자였으면 true값을 반환하였다. // num값은 10이상이다. public static boolean is..

이 전 포스팅에도 올렸지만 그래프에서 최소비용문제는 두 가지 유형이 있다. 1. 모든 정점을 연결하는 간선들의 가중치의 합이 최소가 되는 트리 → 최소신장트리(MST) 2. 두 정점 사이의 최소 비용의 경로 찾기 → 최단경로 이번 포스팅에서는 최단경로 중에서 Dijkstra 알고리즘을 정리할 것이다. 최단 경로란? 간선의 가중치가 있는 그래프에서 두 정점 사이의 경로들 중 간선의 가중치의 합이 최소인 경로를 말한다.(모든 정점을 방문하지 않아도 된다.) 만약 가중치가 없는 그래프에서의 최단경로는 거쳐오는 간선 수의 최솟값을 구하면 된다. 참고 : 최단 경로 알고리즘은 아래와 같다. 하나의 시작 정점에서 끝 정점까지의 최단경로 Dijkstra 알고리즘(탐욕기법) : 음의 가중치를 허용하지 않음. Bellm..

그냥 크루스칼 알고리즘 문제이지만 같은 성별의 대학교는 연결되면 안된다. 따라서 대학교의 성별을 확인할 수 있는 배열을 만들고, unionSet을 할 때 먼저 대학교 성별이 같으면 false를 반환한다. public static boolean unionSet(int x, int y) { if(gender[x] == gender[y]) return false;// 같은 성별의 대학교인 경우는 union하지 않는다. int xRoot = findSet(x); int yRoot = findSet(y); if(xRoot == yRoot) return false; parents[yRoot] = xRoot; return true; } 간단한 문제였다...!! 코드는 아래와 같다. public class BJ_146..

문제를 읽고 어떤 알고리즘으로 접근해야 맞는 건지 많이 고민했다. 크루스칼 알고리즘 → 입력에 이미 연결된 간선 몇 개가 주어져 있기 때문에 서로소 집합을 이용해야 할 거 같음. 하지만 어떤 간선이 존재하는 지 정보가 없으므로 간선리스트를 정렬할 수 없다. 프림 알고리즘 → 이미 연결된 정점들은 거리를 0, 아닌 정점들은 2차원 좌표계상의 거리로 처리 / 이미 연결된 정점들이 존재하므로 서로소 집합을 이용해볼 생각이였다. 프림 알고리즘에서 minEdge 배열은 신장 트리에서 방문하지 않은 정점까지의 최소 거리를 저장한다. 하지만 신장 트리의 어떤 정점으로부터 최소인지는 알 수 없다. 입력으로 이미 연결된 정점들이 존재하는데 나머지 정점들이 저 연결된 정점들에 union 하려면 어떤 정점으로부터 최소인 ..

입력의 형태가 간선 정보를 주기때문에 크루스칼 알고리즘으로 생각했다. 문제를 보고 가장 처음 든 생각은 어떤 기준으로 두 개의 분리된 마을로 분할할까...? 였다. 그래서 집들의 부분집합을 구해야하나...? → 입력이 너무 커서 백퍼 시간초과이고 간선들을 정렬하고 가장 작은 두 개의 간선을 두 개의 마을로 잡을까? → 1. 두 개의 간선이 같은 집을 가리킬 수 도 있기 때문에 안될 듯... 문제를 다시 한 번 살펴보니 마을에는 집이 하나 이상 있어야 한다.가 눈에 들어왔다. 이 말은 마을에는 집 하나만 있으면 되겠구나... 크루스칼 알고리즘은 간선들을 오름차순으로 정렬하고 그 중에서 사이클이 안생기도록 (정점-1)개의 간선들을 선택하면 모든 정점들이 이어진다. 하지만 여기서 (정점-2)개의 간선들을 연결..

그래프에서의 최소비용문제는 2가지가 있다. 1. 모든 정점을 연결하는 간선들의 가중치의 합이 최소가 되는 트리 → 최소신장트리 2. 두 정점 사이의 최소 비용의 경로 찾기 → 최단경로(Dijkstra 알고리즘) 이번 포스팅에서는 최소신장트리를 정리해보겠다... 우선 신장트리란? N개의 정점으로 이루어진 무향 그래프에서 N개의 정점과 n-1개의 간선으로 이루어진 트리를 말한다. 그럼 최소신장트리는? 무향 가중치 그래프에서 신장 트리를 구성하는 간선들의 가중치들의 총합이 최소인 신장 트리 최소신장트리를 구하는 알고리즘이 2가지 존재한다. 1. KRUSKAL(크루스칼) 알고리즘 2. PRIM(프림) 알고리즘 간선을 하나씩 선택해서 MST를 찾는 알고리즘 (접근방법 : 간선중심 →..

서로소 집합이란? 서로소 또는 상호배타 집합들은 서로 중복된 원소가 없는 집합들을 말한다. → 교집합이 없다. 집합에 속한 임의의 멤버 하나를 특정해서 대표자(representative)를 만들고 이를 통해 각 집합들을 구분한다. 서로소 집합 연산 1. MakeSet(x) 2. FindSet(x) 3. Union(x, y) 위와 같이 서로소인 집합 5개가 있다고 하자. → {A} , {B}, {C}, {D}, {E} 1. MakeSet(x) 연산 : 모든 원소를 각각의 집합으로 만드는 함수 자식노드가 있으면 부모 노드를 가리키고, 부모 노드가 없는(원소가 1개일때) 경우에는 대표자인 자기 자신을 가리킨다. 2. UnionSet(x, y) 연산 : x와 y를 하나의 집합으로 합치는 함수 - unionSet..

멀티탭의 플러그 빼는 횟수를 최소화하는 문제!! 처음에 생각한 로직 멀티탭에 비어있는 자리가 있으면 : 멀티탭에 추가 멀티탭에 비어있는 자리가 없으면 이미 꽂혀있는 경우 : 무시 멀티탭에 꽂혀있는 기기들의 사용빈도가 제일 낮은 기기를 뺀다. 하지만 이 경우에는 입력이 아래와 같으면 2 5 3 3 1 4 5 두 번째로 들어온 기기3이 2-1로 빠지는 게 아닌 1번으로 빠지게 되므로 오류... 두 번째로 생각한 로직 멀티탭이 비어있지 않고 이미 꽂혀있는 경우 : 무시 멀티탭에 비어있는 자리가 있으면 : 멀티탭에 추가 멀티탭에 비어있는 자리가 없으면 멀티탭에 꽂혀있는 기기들의 사용빈도가 제일 낮은 기기를 뺀다. 하지만... 이 경우에도 입력이 아래와 같으면 2 7 2 3 1 2 1 2 3 3 3 처음 기기1이..

아주아주아주 짜증나게 했던 문제..^^.. --리뷰는 나중에 추가-- import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.LinkedList; import java.util.Queue; import java.util.StringTokenizer; public class BJ_11725 { static LinkedList[] node; // 인접리스트로 간선끼리 연결된 노드 정보 static int[] parentNode; // 2부터 N까지 부모노드 정보 static int N; // 입력받는 수 public static void main(String[] arg..