Algorithm9

[백준] 1347번 미로 만들기 (Java) 0. 출처 백준 1347번 문제입니다. 1. 문제 홍준이는 미로 안의 한 칸에 남쪽을 보며 서있다. 미로는 직사각형 격자모양이고, 각 칸은 이동할 수 있거나, 벽을 포함하고 있다. 모든 행과 열에는 적어도 하나의 이동할 수 있는 칸이 있다. 홍준이는 미로에서 모든 행과 열의 이동할 수 있는 칸을 걸어다녔다. 그러면서 자신의 움직임을 모두 노트에 쓰기로 했다. 홍준이는 미로의 지도를 자기 노트만을 이용해서 그리려고 한다. 입력으로 홍준이가 적은 내용을 나타내는 문자열이 주어진다. 각 문자 하나는 한 번의 움직임을 말한다. ‘F’는 앞으로 한 칸 움직인 것이고, ‘L'과 ’R'은 방향을 왼쪽 또는 오른쪽으로 전환한 것이다. 즉, 90도를 회전하면서, 위치는 그대로인 것이다. (1) 입력 첫째 줄에 홍준이가 .. Algorithm & Data Structure/코딩 테스트 문제풀이 2024. 4. 19.

[백준] 1916번 최소비용 구하기 (Java) 0. 출처 백준 1916번 문제입니다. 1. 문제 N개의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 M개의 버스가 있다. 우리는 A번째 도시에서 B번째 도시까지 가는데 드는 버스 비용을 최소화 시키려고 한다. A번째 도시에서 B번째 도시까지 가는데 드는 최소비용을 출력하여라. 도시의 번호는 1부터 N까지이다. (1) 입력 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 주어진다. 그리고 그 다음에는 도착지의 도시 번호가 주어지고 또 그 버스 비용이 주어진다. 버스 비용은 0보다 크거나.. Algorithm & Data Structure/코딩 테스트 문제풀이 2024. 4. 18.

다익스트라(dijkstra) 알고리즘 (+Java 코드) 1. 다익스트라란? 다익스트라 알고리즘은 최단 거리를 구하는 알고리즘입니다. (1) 조건 다익스트라 알고리즘을 사용하여 문제를 풀기 위해서는 조건이 있습니다. 음수 가중치가 없어야 한다. 음수 가중치가 있는 그래프에서 최단 거리를 구하기 위해서는 벨만-포드 알고리즘을 사용하면 됩니다! 2. 다익스트라 알고리즘 방식 그렇다면 어떻게 그래프의 최단 거리를 구하는걸까요? 아직 방문하지 않은 정점 중 출발지로부터 가장 가까운 정점을 방문합니다. -> 우선순위 큐 해당 정점을 거쳐 갈 수 있는 정점의 거리가 이전 기록한 값보다 작으면 갱신합니다. (1)번 과정에서 출발지로부터 가장 가까운 정점을 방문해야 하기 때문에 구현할 때에는 우선순위 큐를 사용합니다. 예시를 통해 알아봅시다. (0) 예시 그래프 (1) 출발.. Algorithm & Data Structure/이론 2024. 4. 18.

[백준] 2157번 여행 (Java) 0. 출처 백준 2157번 문제입니다. 1. 문제 N개의 도시가 동쪽에서 서쪽으로 순서대로 위치해 있다. 제일 동쪽에 있는 도시는 1번 도시이며, 제일 서쪽에 있는 도시는 N번 도시이다. 당신은 이와 같은 도시 중에서 M개 이하의 도시를 지나는 여행을 계획하려 한다. 여행 경로는 반드시 1번 도시에서 시작해서 N번 도시에서 끝나야 한다. 물론 이 두 도시도 M개의 도시에 포함된다. 당신은 시차에 매우 민감하기 때문에, 한 번 서쪽으로 이동했다가 다시 동쪽으로 이동하면 몸이 대단히 아프다. 그래서 당신은 계속 서쪽으로만, 즉 도시 번호가 증가하는 순서대로만 이동하기로 하였다. 한편, 모든 도시에서 다른 모든 도시로 이동할 수 있는 건 아니다. 각각의 도시에서 다른 도시로 이동할 때에는 비행기를 타고 이동해.. Algorithm & Data Structure/코딩 테스트 문제풀이 2024. 4. 17.

[백준] 2302번 극장 좌석 (Java) 0. 출처 백준 2302번 문제입니다. 1. 문제 어떤 극장의 좌석은 한 줄로 되어 있으며 왼쪽부터 차례대로 1번부터 N번까지 번호가 매겨져 있다. 공연을 보러 온 사람들은 자기의 입장권에 표시되어 있는 좌석에 앉아야 한다. 예를 들어서, 입장권에 5번이 쓰여 있으면 5번 좌석에 앉아야 한다. 단, 자기의 바로 왼쪽 좌석 또는 바로 오른쪽 좌석으로는 자리를 옮길 수 있다. 예를 들어서, 7번 입장권을 가진 사람은 7번 좌석은 물론이고, 6번 좌석이나 8번 좌석에도 앉을 수 있다. 그러나 5번 좌석이나 9번 좌석에는 앉을 수 없다. 그런데 이 극장에는 “VIP 회원”들이 있다. 이 사람들은 반드시 자기 좌석에만 앉아야 하며 옆 좌석으로 자리를 옮길 수 없다. 오늘 공연은 입장권이 매진되어 1번 좌석부터 N.. Algorithm & Data Structure/코딩 테스트 문제풀이 2024. 4. 16.

이분 탐색 (+Java) 1. 이분 탐색이란 이분 탐색아란 오름차순으로 정렬된 수열에서 원하는 값을 찾는 탐색 알고리즘입니다. 여기서 포인트는 정렬된 수열에서 가능하다는 것입니다! 2. 이분 탐색 방법 정렬된 배열에서 값을 찾는다는 가정 하에 아래의 과정을 반복하면 됩니다! 배열의 가운데 요소의 인덱스를 pivot으로 정합니다. arr[pivot]의 값이 찾고자 하는 값과 같다면 탐색을 종료합니다. arr[pivot]의 값이 찾고자 하는 값보다 작다면 pivot ~ right 사이를 탐색합니다. arr[pivot]의 값이 찾고자 하는 값보다 크다면 left ~ pivot 사이를 탐색합니다. 3. 시간 복잡도 이분 탐색의 시간 복잡도는 O(logN)으로 기본적인 선형 탐색보다 훨씬 빠르게 탐색을 할 수 있습니다. 4. 이분 탐색 .. Algorithm & Data Structure/이론 2021. 12. 16.

BFS와 DFS (+Java 코드) 1. 그래프란? 그래프란 다대다 연결관계를 표현할 수 있는, 여러 노드와 간선으로 연결된 자료구조를 의미합니다. 그래프는 여러 개의 정점(Vertex) 와 간선(Edge)로 이루어져 있습니다. G=(V, E)로 표기합니다. 정점(Vertex): 그래프의 구성요소 간선(Edge): 두 정점을 연결하는 선 차수(Degree): 정점 하나에 연결된 간선의 수 2. 그래프 탐색 그래프 탐색은 하나의 정점으로부터 시작하여 차례대로 모든 정점들을 방문하는 것을 의미합니다. 그래프 탐색에는 크게 두 가지 방법이 있습니다. (1) BFS_너비우선탐색 BFS는 Breadth-First-Search의 약자로 너비 우선 탐색을 의미합니다. 너비 우선 탐색은 기준 노드에서 인접한 노드를 먼저 탐색하는 방법인데요. 시작 정점으.. Algorithm & Data Structure/이론 2021. 12. 16.

계수 정렬 (+Java 코드) 1. 카운팅 정렬이란 카운팅 정렬이란 단어 그대로 정렬 알고리즘 중 하나입니다. 그렇다면 앞에 붙은 카운팅은 무엇일까요? 무엇을 카운팅한다는 것일까요? 정답은 데이터의 값이 몇 번 등장했는지를 카운팅하는 것입니다. 대부분의 정렬은 데이터의 값을 직접 비교하여 정렬하는 경우가 많지만 데이터 값의 직접 비교는 시간 복잡도가 O(NlogN)보다 작아질 수 없다는 한계가 존재합니다. 그에 비해 카운팅 정렬은 O(N) 의 시간 복잡도를 자랑하는데요! 어떻게 가능한 것일까요? 2. 동작 방식 아래 그림과 같은 배열을 정렬하고 싶다고 가정하고 동작 방식을 설명하겠습니다. (1) 카운팅 배열 만들기 카운팅 정렬에는 기존 배열 외에도 카운팅 배열이 따로 필요합니다. 즉, 데이터가 얼마나 등장하는지를 배열 인덱스를 통해 .. Algorithm & Data Structure/이론 2021. 8. 9.

에라토스테네스의 체 (+Java 코드) 1. 에라토스테네스의 체란? 에라토스테네스의 체란 소수를 찾는 방법입니다. 해당 방법은 마치 체로 치듯이 수를 걸러낸다고 해서 에라토스테네스의 체 라고 부른다고 합니다. 2. 동작 방식 우리는 체에 집중해서 하나씩 소수가 아닌 수를 걸러낼 것 입니다. 즉, "소수를 찾고 해당 소수의 배수를 모두 지우면 소수만 남는다!" 입니다. 예를 들어, 100 이하의 자연수 중 소수를 모두 찾아보도록 하겠습니다. (1) 1 제거 우선 소수도, 합성수도 아닌 유일한 자연수인 1을 제거합니다. (2) 2를 제외한 2의 배수 제거 다음으로는 2를 제외한 2의 배수를 제거합니다. 무언가의 배수라는 것은 소수가 아니라는 것을 뜻하니까요! (3) 3을 제외한 3의 배수 제거 다음은 3을 제외한 3의 배수를 제거합니다. (4) .. Algorithm & Data Structure/이론 2021. 7. 27.

이전 1 다음

티스토리툴바