개발하고싶은 블로그

순환하지 않는 유향 그래프를 방향성에 거스르지 않도록 순서대로 배열하는 방법 말 그대로 순환하지 않는 유향 그래프에서 순서가 정해져 있을 때 그 순서대로 방문을 하고 싶을 때 사용할 수 있는 알고리즘이다. 그림을 통해서 예시를 하나 들어보겠다. 만약 아래와 같은 그래프가 있다고 가정해 보자 처음으로 진입점이 존재하지 않는 1부터 시작해 보자. (1을 큐에 넣는다) 현재 큐에는 1만 있으므로 큐에서 1을 꺼내면 1이 가리키고 있는 2, 3이 후보가 된다. 2, 3 모두 앞의 순서가 1밖에 없다. 그러므로 2, 3 모두 방문이 가능하므로 큐에 2, 3을 넣는다. 다시 큐에서 2를 꺼내 2가 가리키고 있는 4, 5에 대해서 확인해 보면 5는 2 이외에도 3이 앞 순서로 있기 때문에 현재 작업할 수 없는 상태이..

[문제] 이동 규칙 다음에 이동할 수 있는 거리(광년)는 현재 이동거리의 현재 이동거리, +1 또는 -1이다. 현재 3을 이동했다면 다음에 이동할 수 있는 거리는 2, 3, 4 중에 하나이다. 마지막 이동거리는 1이여야 한다. 위의 이동 규칙을 가지고 현재 x지점에서 y지점으로 가기 위해선 최소 몇 번 움직여야 할까? 처음에는 단순하게 brute-force, BFS를 사용하면 되지 않을까라고 생각했다. 처음에 1을 움직이고 그다음에는 1, 2를 큐에 넣고 그 다음에도 또 1,1,2,3을 큐에 넣고 이런 식으로 전체 탐색을 하다가 현재 지점이 y이면서 이동거리가 1였을 때를 찾으면 되지 않을까라고 생각했다. 하지만… 메모리 초과가 발생했다. 당연하게도 처음에 이동할 때를 제외하고는 3번씩 (-1, 현재, ..

먼저 공백을 print하고 *을 프린트 해주면 된다 import java.io.BufferedReader; import java.io.InputStreamReader; class Main { public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int n = Integer.parseInt(br.readLine()); for (int i = 1; i

입력값이 엄청 큰 숫자이다. 최대 10^1000까지 값이 들어올 수 있는데 이 값은 Long의 범위도 벗어난다. 자바에서는 이럴 때 정수형이므로 BigInteger를 사용하면 된다. import java.io.BufferedReader; import java.io.InputStreamReader; import java.math.BigInteger; import java.util.StringTokenizer; class Main { public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = ne..

앞으로 푸는 모든 문제에 대해 정리하려 한다. import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.StringTokenizer; class Main { public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine()); int a = Integer.parseInt(st.nextToken()); int b = Integer.parseInt(st.n..

플러드 필(flood fill) 혹은 시드 필(seed fill)은 다차원 배열의 어떤 칸과 연결된 영역을 찾는 알고리즘이다. - 위키백과 위와 같은 다차원 배열이 있다고 가정했을 때, 검은색으로 칠해진 부분은 연결되지 않은 영역이라고 하자. 그러면 위의 다차원 배열에 대해서 특정 칸과 연결된 영역을 찾고 싶을 때 플러드 필 알고리즘을 이용해서 찾을 수 있다. (연결된 영역은 상하좌우로 접근 가능한 경우이다) 만약 0.0과 연결된 영역을 찾는다면 아래와 같은 영역이 찾아진다. 또한 0.3과 연결된 영역을 찾으면 아래와 같은 영역이다.이렇게 연결된 영역을 찾고 싶을 때 사용할 수 있는 알고리즘이 플러드 필 알고리즘이다. 스택 기반이나 큐 기반으로 구현할 수 있다. 자세한 사항은 아래 위키백과를 참조하자. ..

idea-sketch.tistory.com/29 [알고리즘] 되추적(Backtracking)을 알아보자. 오늘의 주제는 되추적(Backtracking) 이다. 저번 포스팅인 깊이우선탐색(Depth-First Search)과 넓이우선탐색(Breath-First Search)의 몸풀기를 거치고 최단경로(Shortest Path) 알고리즘에 들어가는 첫 걸음이라.. idea-sketch.tistory.com 여기에 설명이 잘 되어 있다. 요지는 dfs를 스택을 이용하여 구현한다면 "스택을 사용하고 스택에 넣기 전에 유망성 검사를 한다. 유망성 검사 조건을 어떻게 할 것인가" 인 것 같다