전체 글

주요 개념 ✨ 가중치 방향 그래프 방향을 지닌 그래프로, 각 edge에 가중치를 가진다. 다익스트라 알고리즘 특정한 하나의 정점에서 다른 모든 정점으로 가는 최단 경로를 알려주는 알고리즘이다. 가중치 방향 그래프에서 다익스트라 알고리즘을 이용할 때는 간선의 가중치가 음수이면 안되는 점을 유의해야 한다. (0은 될 수 있다.) 문제 ✨ 가중치 방향그래프에서 1번 정점에서 모든 정점으로의 최소비용을 출력하시오. (2번 정점부터 출력) 풀이 ✨ 메모이라이즈할 배열 변수를 두어 1부터 각 노드로의 거리비용을 저장한다. 해당 배열에 해당 노드의 거리비용 값이 있는 경우 새로운 값이 더 작을 때에만 그 값을 대체한다. 이 때 문제는 N개의 노드를 대상으로 각 노드로의 거리 비용을 구하기 위해서는 ${n}*{n}$만..

Priority Queue Java에서는 PriorityQueue라는 클래스를 그대로 사용하면 된다. 이진 트리로 구성되어 있어, $nlog(n)$의 시간만에 가장 우선순위가 높은 요소를 찾아준다. 이 때 우선순위는 그 값이 작을수록 높은 것이 기본이며, 반대로 큰 수가 곧 높은 우선순위로 여겨지려면 Collections.reverseOrder()을 인자로 전달한다. 예를 들어, 아래와 같이 일련의 수를 우선순위 큐에 넣는 경우를 보면 더욱 이해가 잘 될 것이다. PriorityQueue q = new PriorityQueue(); q.offer(7); q.offer(3); q.offer(1); q.offer(11); while (!q.isEmpty()) { System.out.print(q.poll()..

문제 ✨ 결혼식 피로연을 장소를 3일 동안 빌려 쉬지 않고 진행하려고 한다. 이에 참석하는 친구들 N명의 도착 시간과 떠날 시간을 전달받아 피로연 장소에 동시에 존재하는 최대 인원수를 구해 그 인원을 수용할 수 있는 장소를 빌리려 한다. 만약 도착 시간 13시이고 떠날 시간 15시라면, 이 친구는 13시에는 피로연 장소에 존재하나 15시에는 존재하지 않는다고 가정한다. 피로연장에 동시에 존재하는 최대 인원을 출력해야 한다. 피로연은 0시부터 72시까지 진행한다.) 풀이 ✨ 시간의 범위를 0부터 72까지 변화시키며(아래 코드에서는 정렬된 배열의 첫 번째 요소 - 친구 - 의 도착 시간을 출발값으로 정의) 당시의 시간과 출발 시간이 겹치는 친구가 있을 때에는 동시에 존재하는 인원(cnt)를 증가시키고, 당시..

문제 ✨ 한 개의 회의실과 이를 사용하고자 하는 n개의 회의들에 대해 회의실 사용표를 만들려고 한다. 각 회의는 시작시간과 끝나는 시간이 주어지고, 이를 통해 회의실을 사용할 수 있는 최대 수의 회의를 출력한다. (회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다른 회의가 시작될 수 있다. 또한, 회의시간은 0시부터 시작한다.) 풀이 ✨ 먼저 시작하는 것부터 선택하는 것이 아니라 빨리 끝나는 것 부터 선택해야 한다. 만약 끝나는 시간이 일치하는 경우에는 시작하는 시간으로 오름차열 정렬을 해야한다. 작성 코드 ✍️ import java.util.*; public class Main { static int cnt = 0; static int n; static Item[] lis..

그리디 알고리즘 순간 순간에 가장 최선이라고 여겨지는 선택을 하는 알고리즘을 뜻한다. 전반적인 결과도 최선이라는 보장을 할 수 없다. 문제 ✨ N명의 지원자의 키와 몸무게 정보를 입력받아 각 지원자가 다른 지원자와 일대일 비교해서 키와 몸무게 모두 높은 지원자가 존재할 경우에는 떨어트리고, 그렇지 않으면 선발한다고 했을 때 N명의 지원자가 주어지면 최대 몇 명의 선수를 선발할 수 있는지 출력한다. 풀이 ✨ 키와 몸무게 정보로 구성된 클래스를 생성한다. 두 가지 속성으로 비교하기 때문에 기본적으로 키를 기준으로 인스턴스들을 역순으로 정렬한 후 순서대로 해당 인스턴스의 몸무게가 여태까지 나온 최대 몸무게보다 클 때에만 탈락하지 않는다고 여긴다. 작성 코드 ✍️ import java.util.*; public..

문제 ✨ N x N 크기의 지도가 있고, 이는 1 x 1 크기의 격자칸으로 구성되어있다. 각 격자칸에 0은 빈칸, 1은 집, 2는 피자집으로 표현된다. 각 집의 피자배달거리는 해당 집과 도시에 존재하는 피자집들과의 거리 중 최소값을 해당 집의 피자배달거리라고 한다. M개의 피자집만 살리고 나머지는 폐업시킨다고 할 때, 도시의 피자배달거리 최소값을 구하라. (도시의 피자배달거리는 각 집의 피자배달거리를 합친 값이다.) 풀이 ✨ 인접 행렬을 구성하는 값들을 입력받을 때 피자 가게(2)들과 집(1)들을 리스트로 구성하고 피자 가게 리스트의 내부 요소들을 가지고 루프를 돌게 했다. 해당 순서의 피자 가게를 선택하는 경우(checked[idx] = true)와 그렇지 않은 경우(checked[idx] = fals..

문제 N*N의 섬나라 아일랜드의 지도가 격자판의 정보로 주어집니다. 각 섬은 1로 표시되어 상하좌우와 대각선으로 연결되어 있으며, 0은 바다입니다. 섬나라 아일랜드에 몇 개의 섬이 있는지 구하는 프로그램을 작성하세요. 만약 위와 같다면 섬의 개수는 5개입니다. 첫 번째 줄에 자연수 N(3

문제 ✨ 풀이 ✨ 이 문제를 트리라고 생각해보면 다음과 같이 접근할 수 있다. 시작 노드는 1(값과 달라야 함)이다. (이 때의 레벨을 1로 볼 수 있다.) 마지막 노드는 7이다. (이 때의 레벨을 7로 볼 수 있다.) 각 노드가 다음 노드로 이동할 수 있는 경우는 자기 자신 노드의 좌표 값(x, y)에서 x는 [0, 1, 0, -1]를 더하고, y는 [-1, 0, 1, 0]를 더한 좌표의 x좌표와 y좌표가 모두 1보다 크거나 같고, 7보다 작거나 같아야 하며, 이전에 왔던 길은 가지 않아야 한다. 또한 그 값이 1인 경우이다. 이 값을 인접 행렬로 정리할 수 있다. 레벨을 별도의 변수로 두지 않고, y값이 곧 레벨이라고 여긴다. 마지막에 좌표(7, 7)에 도달하는 경우 cnt를 증가시킨다. import..

문제 ✨ 가장 윗 줄에 1부터 N까지의 숫자가 한개씩 적혀 있다. 그리고 둘째 줄부터 파스칼의 삼각형처럼 위의 두개를 더한 값이 저장되게 한다. N과 가장 밑의 숫자가 주어져있을 때, 가장 윗줄에 있는 숫자를 구하는 프로그램을 작성하시오. 단, 답이 여러 개 나오는 경우에는 사전순으로 가장 앞에 오는 것을 출력해야 한다. 첫째 줄에 두개의 정수 N과 F가 주어진다. N은 가장 윗 줄에 있는 숫자의 개수를 의미하며, F는 가장 밑에 있는 수로 1,000,000 이하이다. 풀이 ✨ 규칙을 찾아야 한다. N이 4이고 F는 16인 경우에, 가장 윗 줄의 숫자들(답)이 3 1 2 4 순서로 있다고 생각해보자. 아래와 같은 역방향 삼각형을 이룰 것이다. 이 때 둘째 줄부터 해당 값들이 더해지는 과정을 모두 써보자...

블로그에 알고리즘 문제 해설을 올리면서, 수식입력이 불가피한 경우가 생겼다. 티스토리에서는 기본적으로 수식 입력이 지원되지 않으니 외부 라이브러리를 사용해야 한다. 내가 사용한 라이브러리는 MathJax로, 구분자를 두어 수식을 입력하면 수식이 정확하다는 전제 하에 원하던 수식 형태로 변환시켜 준다. 라이브러리 추가하기 글 작성 모드를 HTML모드로 변경 후 위에 작성해둔 코드를 글에 추가하자. 참고로 위 코드는 CDN을 통해 항상 최신 버전의 MathJax를 사용할 수 있게 해준다. 만약 Specific한 버전의 MathJax를 사용하고 싶다면, 아래 코드의 두 번째 줄에 mathjax@[버전] 부분을 수정하면 된다. 만약 블로그에 꾸준히 수식을 사용하게 될 것이라면 아예 블로그 어디서든 접근할 수 있..