개발하고싶은 블로그

순환하지 않는 유향 그래프를 방향성에 거스르지 않도록 순서대로 배열하는 방법 말 그대로 순환하지 않는 유향 그래프에서 순서가 정해져 있을 때 그 순서대로 방문을 하고 싶을 때 사용할 수 있는 알고리즘이다. 그림을 통해서 예시를 하나 들어보겠다. 만약 아래와 같은 그래프가 있다고 가정해 보자 처음으로 진입점이 존재하지 않는 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

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

링크 : www.acmicpc.net/problem/1339 1339번: 단어 수학 첫째 줄에 단어의 개수 N(1 ≤ N ≤ 10)이 주어진다. 둘째 줄부터 N개의 줄에 단어가 한 줄에 하나씩 주어진다. 단어는 알파벳 대문자로만 이루어져있다. 모든 단어에 포함되어 있는 알파벳은 최대 www.acmicpc.net 문제는 알파벳이 들어왔을 때 각 알파벳마다 0부터 9까지 숫자 중 하나로 바꿨을 때의 합의 최댓값을 구하는 문제입니다. 일단 경우의 수는 10! 가지이기 때문에 시간 초과가 발생하지 않지만 각 경우마다 합을 구하는 로직이 들어가기 때문에 그렇게 하면 시간 초과가 발생하게 됩니다. 그래서 다른 방법을 생각해봤는데 문제를 잘 보시면 제일 앞 자릿수에 큰 수를 할당하면 문제를 풀 수 있습니다. 예를 들..

링크 : https://www.acmicpc.net/problem/1107 1107번: 리모컨 첫째 줄에 수빈이가 이동하려고 하는 채널 N (0 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 고장난 버튼의 개수 M (0 ≤ M ≤ 10)이 주어진다. 고장난 버튼이 있는 경우에는 셋째 줄에는 고장난 버튼�� www.acmicpc.net 문제는 현재 위치가 100일 때 주어진 위치로 가기 위해서 리모컨을 최소 몇 번을 클릭해야 하느냐는 문제입니다. 대신 리모컨의 숫자 버튼 일부가 고장 나 있는 상태일 수 있다는 것이죠 현재 위치에서 문제에서 주어지는 위치로 갈 수 있는 방법은 일반적으로 생각하면 2가지 경우입니다. 1. + 또는 - 버튼을 사용하여 해당 위치로 간다. 100보다 큰 위치이면 +, 100..