본문 바로가기

알고리즘/백준

(40)
[백준 1009 : JAVA] 분산처리 개요 a^b 의 경우 a가 어떤 숫자여도 1의 자릿수만 신경 쓰면 된다!! a의 1의 자릿수는 0, 1, 2 .... 8, 9 까지만 존재한다!! 문제 재용이는 최신 컴퓨터 10대를 가지고 있다. 어느 날 재용이는 많은 데이터를 처리해야 될 일이 생겨서 각 컴퓨터에 1번부터 10번까지의 번호를 부여하고, 10대의 컴퓨터가 다음과 같은 방법으로 데이터들을 처리하기로 하였다. 1번 데이터는 1번 컴퓨터, 2번 데이터는 2번 컴퓨터, 3번 데이터는 3번 컴퓨터, ... , 10번 데이터는 10번 컴퓨터, 11번 데이터는 1번 컴퓨터, 12번 데이터는 2번 컴퓨터, ... 총 데이터의 개수는 항상 ab개의 형태로 주어진다. 재용이는 문득 마지막 데이터가 처리될 컴퓨터의 번호가 궁금해졌다. 이를 수행해주는 프로그..
[백준 1004 : JAVA] 어린왕자 개요 한 가지만 알면 풀 수 있다. 시작점, 도착점 둘 중 하나만 각 행성 안에 있다면 무조건 진입/이탈을 해야된다. 문제 어린 왕자는 소혹성 B-664에서 자신이 사랑하는 한 송이 장미를 위해 살아간다. 어느 날 장미가 위험에 빠지게 된 것을 알게 된 어린 왕자는, 장미를 구하기 위해 은하수를 따라 긴 여행을 하기 시작했다. 하지만 어린 왕자의 우주선은 그렇게 좋지 않아서 행성계 간의 이동을 최대한 피해서 여행해야 한다. 아래의 그림은 어린 왕자가 펼쳐본 은하수 지도의 일부이다. 빨간 실선은 어린 왕자가 출발점에서 도착점까지 도달하는데 있어서 필요한 행성계 진입/이탈 횟수를 최소화하는 경로이며, 원은 행성계의 경계를 의미한다. 이러한 경로는 여러 개 존재할 수 있지만 적어도 3번의 행성계 진입/이탈이 ..
[백준 1010 : JAVA] 다리 놓기/ DP, 조합 개요 문제를 어떤 관점에서 바라보냐는 알고리즘 문제를 푸는 중요한 키이다. 이 문제는 조합(combination)을 이용하여 문제를 풀이할 수 있다. mCn을 구하는 문제이다. 직역하자면 m개 중에서 n개를 선택하는 경우의 수를 구하는 문제이다. 따라서 조합을 이용해야 하는데 기존의 조합의 식인 n! / ((n - r)! * r!)을 이용하기보다는 점화식인 f(n, k) = f(n - 1, k) + f(n - 1, k - 1)을 이용하면 된다. 위의 점화식은 마지막을 선택하냐 + 선택하지 않냐 의 관점을 이용한 점화식이다. 문제 재원이는 한 도시의 시장이 되었다. 이 도시에는 도시를 동쪽과 서쪽으로 나누는 큰 강이 흐르고 있다. 하지만 재원이는 다리가 없어서 시민들이 강을 건너는데 큰 불편을 겪고 있음을..
[백준 11725: JAVA] 트리의 부모 찾기/ 트리, DFS 개요 이 문제는 처음에 입력받은 순서대로 부모 노드 값을 저장하여 풀이하였는데 이렇게 푼 경우 누가 부모노드이고 누가 자식 노드인지 판별을 할 수 없는 문제가 발생하였다. 결국에는 입력받은 노드와 간선에 대한 정보를 인접리스트로 초기화하고 DFS를 이용하여 모든 경로를 탐색하며 부모노드 정보를 저장하여 풀이하였다. 기본적으로 DFS에 대한 이해가 바탕이 되어야 한다. 따라서 DFS에 대한 이해도가 낮다면 아래의 문제와 풀이를 먼저 보는 것을 추천한다. https://www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집들의 모임인 단지를 정의하고, 단지..
[백준 11779: JAVA] 최소비용 구하기 2 / 다익스트라, 역추적 개요 기본적인 최단거리 문제에서 경로 추적이 포함되어 있는 문제이다. 경로의 가중치가 양수이기 때문에 다익스트라를 선택하였고 경로 추적을 위해 부모 노드를 저장하여 풀이하였다. 다익스트라를 잘 모른다면 아래의 문제를 먼저 심도 있게 풀어보는 것이 좋을 것 같다. https://www.acmicpc.net/problem/1753 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1≤V≤20,000, 1≤E≤300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1≤K≤V)가 주어진다. 셋째 줄부터 E개의 줄에 걸쳐 각 간선을 나타내는 세 개의 정수 (u, v, w)가 순서대로 주어진다. 이는 u에서 v로 가는 가중치 w인..
[백준 9019: JAVA] DSLR / BFS, 역추적 개요 1. BFS를 이용하여 최단거리를 탐색한다. 2. 부모 노드의 값을 저장한다. 3. 연산목록을 구하기 위해 연산배열 정보를 저장한다. 4. 2와 3을 이용하여 연산목록을 역순으로 구한다. 문제 네 개의 명령어 D, S, L, R 을 이용하는 간단한 계산기가 있다. 이 계산기에는 레지스터가 하나 있는데, 이 레지스터에는 0 이상 10,000 미만의 십진수를 저장할 수 있다. 각 명령어는 이 레지스터에 저장된 n을 다음과 같이 변환한다. n의 네 자릿수를 d1, d2, d3, d4라고 하자(즉 n = ((d1 × 10 + d2) × 10 + d3) × 10 + d4라고 하자) D: D 는 n을 두 배로 바꾼다. 결과 값이 9999 보다 큰 경우에는 10000 으로 나눈 나머지를 취한다. 그 결과 값(2..
[백준 13913: JAVA] 숨바꼭질 4 / DP, BFS, 역추적 개요 숨바꼭질 시리즈에서 경로 탐색이 추가된 문제이다. 경로 탐색을 하기 위해서 찾은 경로의 부모 노드를 저장하여 풀이하였다. 동생의 위치에 도달한 경우는 동생의 위치부터 수빈이의 위치가 나올 때까지 loop를 돌며 경로를 탐색한다. 또한, 이때 경로를 stack에 저장하였는데 그 이유는 문제에서 수빈 -> 동생의 경로 순서대로 출력해야 하기 때문에 LIFO 구조가 필요했기 때문이다. 또한, BFS를 이용해서 최단거리를 탐색하였다. 문제 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이..
[백준 12738: JAVA] 가장 긴 증가하는 부분 수열 3/ 이분 탐색 개요 이 문제는 2가지 정도의 풀이가 존재한다. 1. 동적 프로그래밍 2. 이분 탐색 하지만, 이 문제의 입력에서 n의 값이 1,000,000 이기 때문에 이분 탐색으로 풀이하여야 시간 초과를 피할 수 있다. 간단히 설명하자면 우리가 구하고자 하는 증가 수열을 List 자료구조에 저장하고 새로 들어온 값에 대해서 list 안에서의 위치를 찾아 list를 갱신해주는 것이다. 문제 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다. 입력 풀이 개요에서 말했듯이 이분탐색을 이용해서 수열의 적당..