본문 바로가기
728x90

Algorithm68

백준 5250번 최단 경로들 문제 Nikola는 Bit 마을에 살고 있고 Hex 마을에 사는 Anita의 남자친구이다. Nikola는 주변 지도를 아주 잘 알고 있어서 두 마을 사이의 최단 경로를 찾았다. 그리고 이 경로를 운 좋은 경로라고 부르기로 했다. 주변 지도는 서로 다른 마을을 잇는 양방향 도로의 집합으로 표현된다. 어떤 날, 이 나라의 대통령이 도로에 공사를 하기로 했다. 나라의 교통을 유지하기 위하여, 오직 하루에 하나의 도로만 닫기로 했다. 운 좋은 경로에 있는 도로에 대해서, Nikola는 그 도로가 닫혔을 때 Anita와의 최단 경로의 길이를 알고 싶어 한다. 입력 입력의 첫째 줄은 4개의 정수로 이루어진다: n - 도시의 개수; m - 도로의 개수; a - Bit 마을(Nikola가 살고 있는 마을)의 번호; b.. 2023. 5. 30.
백준 1848번 동굴 탐험 문제설명 월드산의 하부에는 동굴로 들어가는 입구가 있는데, 동굴은 터널을 통해 서로 연결되어 있는 여러 개의 작은 방들로 구성되어 있다. 동굴 입구는 탐험의 시작점이 되는 방 (이하 시작방)으로 곧장 연결되어 있다. 각 방을 연결하는 터널은 서로 교차하지 않으며, 두 개의 방을 연결하는 터널은 많아 봐야 하나이다. "원쌤배 동굴 탐험 대회"가 개최될 예정이다. 대회의 목표는 시작방에서 출발하여 동굴 내부를 달려, 다시 시작방으로 되돌아 와 빠져 나오는 것인데, 그 경로는 참가자가 마음대로 정할 수 있지만 두 가지 조건을 지켜야 한다. 첫째 조건은, 시작방 이외의 방을 최소한 하나는 거쳐야 한다는 것이며, 둘째 조건은, 어떤 방과 터널도 최대 한 번밖에 방문할 수 없다는 것이다. (시작방은 물론 두 번 방.. 2023. 4. 15.
프로그래머스 달리기 경주 달리기 경주 1. 문제 설명 문제 설명 얀에서는 매년 달리기 경주가 열립니다. 해설진들은 선수들이 자기 바로 앞의 선수를 추월할 때 추월한 선수의 이름을 부릅니다. 예를 들어 1등부터 3등까지 "mumu", "soe", "poe" 선수들이 순서대로 달리고 있을 때, 해설진이 "soe"선수를 불렀다면 2등인 "soe" 선수가 1등인 "mumu" 선수를 추월했다는 것입니다. 즉 "soe" 선수가 1등, "mumu" 선수가 2등으로 바뀝니다. 선수들의 이름이 1등부터 현재 등수 순서대로 담긴 문자열 배열 players와 해설진이 부른 이름을 담은 문자열 배열 callings가 매개변수로 주어질 때, 경주가 끝났을 때 선수들의 이름을 1등부터 등수 순서대로 배열에 담아 return 하는 solution 함수를 .. 2023. 4. 15.
백준 9328번 열쇠 문제 상근이는 1층 빌딩에 침입해 매우 중요한 문서를 훔쳐오려고 한다. 상근이가 가지고 있는 평면도에는 문서의 위치가 모두 나타나 있다. 빌딩의 문은 모두 잠겨있기 때문에, 문을 열려면 열쇠가 필요하다. 상근이는 일부 열쇠를 이미 가지고 있고, 일부 열쇠는 빌딩의 바닥에 놓여져 있다. 상근이는 상하좌우로만 이동할 수 있다. 상근이가 훔칠 수 있는 문서의 최대 개수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 테스트 케이스의 개수가 주어진다. 테스트 케이스의 수는 100개를 넘지 않는다. 각 테스트 케이스의 첫째 줄에는 지도의 높이와 너비 h와 w (2 ≤ h, w ≤ 100)가 주어진다. 다음 h개 줄에는 빌딩을 나타내는 w개의 문자가 주어지며, 각 문자는 다음 중 하나이다. '.'는 빈 공간을 나타.. 2023. 4. 1.
백준 2042번 구간 합 구하기(BIT) 문제 어떤 N개의 수가 주어져 있다. 그런데 중간에 수의 변경이 빈번히 일어나고 그 중간에 어떤 부분의 합을 구하려 한다. 만약에 1,2,3,4,5 라는 수가 있고, 3번째 수를 6으로 바꾸고 2번째부터 5번째까지 합을 구하라고 한다면 17을 출력하면 되는 것이다. 그리고 그 상태에서 다섯 번째 수를 2로 바꾸고 3번째부터 5번째까지 합을 구하라고 한다면 12가 될 것이다. 입력 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 합을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄까지 N개의 수가 주어진다. 그리고 N+2번째 줄부터 N+M+K+1번째 줄까지 세 .. 2023. 3. 30.
세그먼트 트리란? 세그먼트 트리(Segment Tree)란? 여러 개의 데이터가 존재할 때 특정 구간의 합(최솟값, 최댓값, 곱 등)을 구하는 데 사용하는 자료구조이다. 트리 종류 중에 하나로 이진 트리의 형태이며, 특정 구간의 합을 가장 빠르게 구할 수 있다는 장점이 있다. (O(logN)) 아래 예제를 통해 세그먼트 트리(Segment Tree)를 왜 사용하는지 알아보자. (Ex) 위와 같은 배열이 있다고 하자. 이 때 데이터의 개수는 10개로 인덱스는 0부터 9까지 차례대로 1~10의 원소가 삽입되어 있다. 만약 인덱스 2부터 8까지 데이터를 더하려면 어떻게 할까? 위 그림처럼 2~8 범위의 원소를 하나씩 다 더하면 된다. 결과는 42이다. 이러한 방식으로 다른 특정 구간의 합을 구한다고 고려했을 때 앞에서 하나씩 .. 2023. 3. 29.
728x90

티스토리툴바