개발자꿀꿀이

문제 3×3 표에 다음과 같이 수가 채워져 있다. 오른쪽 아래 가장 끝 칸은 비어 있는 칸이다. 1 2 3 4 5 6 7 8 어떤 수와 인접해 있는 네 개의 칸 중에 하나가 비어 있으면, 수를 그 칸으로 이동시킬 수가 있다. 물론 표 바깥으로 나가는 경우는 불가능하다. 우리의 목표는 초기 상태가 주어졌을 때, 최소의 이동으로 위와 같은 정리된 상태를 만드는 것이다. 다음의 예를 보자. 1 3 4 2 5 7 8 6 1 2 3 4 5 7 8 6 1 2 3 4 5 7 8 6 1 2 3 4 5 6 7 8 가장 윗 상태에서 세 번의 이동을 통해 정리된 상태를 만들 수 있다. 이와 같이 최소 이동 횟수를 구하는 프로그램을 작성하시오. 풀이 문제를 보면 BFS(너비 우선 탐색)로 풀어야 한다는 생각이 들지 않는다. ..

문제 N(2 ≤ N ≤ 40,000)개의 정점으로 이루어진 트리가 주어지고 M(1 ≤ M ≤ 10,000)개의 두 노드 쌍을 입력받을 때 두 노드 사이의 거리를 출력하라. 풀이 선형 시간의 LCA 알고리즘을 사용하였다. 해당 LCA까지의 간선 비용을 모두 합한 것이 두 정점 사이의 거리가 된다. 배열은 세개를 선언하였다 parents[] : 해당 정점의 바로 위 조상을 저장 하는 배열 parent_len[] : 해당 정점의 바로 위 조상과의 거리를 저장하는 배열 depth[] : 1번 정점을 제일 큰 조상을 두고 그로 부터의 깊이를 저장하는 배열 거리를 구하는 코드는 아래와 같다. public static int find_Dist(int a, int b) { if(depth[a] < depth[b]) {..

문제 N(2 ≤ N ≤ 100,000)개의 정점으로 이루어진 트리가 주어진다. 트리의 각 정점은 1번부터 N번까지 번호가 매겨져 있으며, 루트는 1번이다. 두 노드의 쌍 M(1 ≤ M ≤ 100,000)개가 주어졌을 때, 두 노드의 가장 가까운 공통 조상이 몇 번인지 출력한다. 풀이 conpulake.tistory.com/60 백준 11438 (LCA 2) - 최소공통조상(HLD 풀이) 문제 N(2 ≤ N ≤ 100,000)개의 정점으로 이루어진 트리가 주어진다. 트리의 각 정점은 1번부터 N번까지 번호가 매겨져 있으며, 루트는 1번이다. 두 노드의 쌍 M(1 ≤ M ≤ 100,000)개가 주어졌을 때, 두 conpulake.tistory.com 위의 링크에서 HLD 풀이를 했다. 좀 더 직관적이고 보편..

문제 N개의 숫자로 구분된 각각의 마을에 한 명의 학생이 살고 있다. 어느 날 이 N명의 학생이 X (1 ≤ X ≤ N)번 마을에 모여서 파티를 벌이기로 했다. 이 마을 사이에는 총 M개의 단방향 도로들이 있고 i번째 길을 지나는데 Ti(1 ≤ Ti ≤ 100)의 시간을 소비한다. 각각의 학생들은 파티에 참석하기 위해 걸어가서 다시 그들의 마을로 돌아와야 한다. 하지만 이 학생들은 워낙 게을러서 최단 시간에 오고 가기를 원한다. 이 도로들은 단방향이기 때문에 아마 그들이 오고 가는 길이 다를지도 모른다. N명의 학생들 중 오고 가는데 가장 많은 시간을 소비하는 학생은 누구일지 구하여라. 풀이 풀이 순서 1. 모든 학생에 대해서 다익스트라 알고리즘을 통해 최단거리를 구한다. for(int i = 1 ; i

문제 45656이란 수를 보자. 이 수는 인접한 모든 자리수의 차이가 1이 난다. 이런 수를 계단 수라고 한다. 세준이는 수의 길이가 N인 계단 수가 몇 개 있는지 궁금해졌다. N이 주어질 때, 길이가 N인 계단 수가 총 몇 개 있는지 구하는 프로그램을 작성하시오. (0으로 시작하는 수는 없다.) 풀이 N이 1과 2일 때, N = 1 -> 1, 2, 3, 4, 5, 6, 7, 8, 9 N = 2 -> 10, 12, 21, 23, 32, 34, 43, 45, 54, 56, 65, 67, 76, 78, 87, 89, 98 규칙을 찾아보면 N-1 의 수에서 -1, +1 해주는 것이다. 1차배열로는 이를 구현해내기 어렵기 때문에 2차배열로 뒷자리를 0~9 까지 저장을해서 갯수를 저장하는 방식으로 구한다. 예를들..

문제 알고스팟 운영진이 모두 미로에 갇혔다. 미로는 N*M 크기이며, 총 1*1크기의 방으로 이루어져 있다. 미로는 빈 방 또는 벽으로 이루어져 있고, 빈 방은 자유롭게 다닐 수 있지만, 벽은 부수지 않으면 이동할 수 없다. 알고스팟 운영진은 여러명이지만, 항상 모두 같은 방에 있어야 한다. 즉, 여러 명이 다른 방에 있을 수는 없다. 어떤 방에서 이동할 수 있는 방은 상하좌우로 인접한 빈 방이다. 즉, 현재 운영진이 (x, y)에 있을 때, 이동할 수 있는 방은 (x+1, y), (x, y+1), (x-1, y), (x, y-1) 이다. 단, 미로의 밖으로 이동 할 수는 없다. 벽은 평소에는 이동할 수 없지만, 알고스팟의 무기 AOJ를 이용해 벽을 부수어 버릴 수 있다. 벽을 부수면, 빈 방과 동일한 ..

문제 정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다. 1+1+1+1 1+1+2 1+2+1 2+1+1 2+2 1+3 3+1 정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오. 풀이 1 = 1 2 = 1+1, 2 3 = 1+1+1, 1+2, 2+1, 3 4 = 1의 경우에 3을 더함 2의 경우에 2를 더함 3의 경우에 1을 더함 5 = 2의 경우에 3을 더함 3의 경우에 2를 더함 4의 경우에 1을 더함 ... 이런식으로 진행되는 걸 점화식으로 나타내면 an = an-1 + an-2 + an-3 이 나온다. import java.io.BufferedReader; import java...

문제 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. 풀이 https://programmers.co.kr/learn/courses/30/lessons/12900?language=java 코딩테스트 연습 - 2 x n 타일링 가로 길이가 2이고 세로의 길이가 1인 직사각형모양의 타일이 있습니다. 이 직사각형 타일을 이용하여 세로의 길이가 2이고 가로의 길이가 n인 바닥을 가득 채우려고 합니다. 타일을 채울 때는 programmers.co.kr 해당 문제는 프로그래머스에도 존재한다. 풀이는 문제 개수를 세봤다. 1 -> 1 2 -> 2 3 -> 3 4 -> 5 5 -> 8 6 -> 13 7 ..

문제 정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다. X가 3으로 나누어 떨어지면, 3으로 나눈다. X가 2로 나누어 떨어지면, 2로 나눈다. 1을 뺀다. 정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오. 풀이 간단하게 3으로 나누고 2로 나누고 둘다 안되면 1을 빼면 된다는 문제로 생각하면 큰코 다친다. DP(Dynamic Programming) 문제의 예이다. 2가지 방식이 있다. Bottom-Up방식과, Top-Down 방식이 존재한다. Bottom-Up : 반복문을 통해 풀어내는 방식. Top-Down : 재귀를 통해 풀어내는 방식. 이 문제의 방식은 이렇다. 1부터 최솟값을 계속해서 저장을 한다. 6..

문제 요즘 많은 자동차에서는 GPS 네비게이션 장비가 설치되어 있다. 네비게이션은 사용자가 입력한 출발점과 도착점 사이의 최단 경로를 검색해 준다. 하지만, 교통 상황을 고려하지 않고 최단 경로를 검색하는 경우에는 극심한 교통 정체를 경험할 수 있다. 상근이는 오직 자기 자신만 사용 가능한 네비게이션을 만들고 있다. 이 네비게이션은 절대로 최단 경로를 찾아주지 않는다. 항상 거의 최단 경로를 찾아준다. 거의 최단 경로란 최단 경로에 포함되지 않는 도로로만 이루어진 경로 중 가장 짧은 것을 말한다. 예를 들어, 도로 지도가 아래와 같을 때를 생각해보자. 원은 장소를 의미하고, 선은 단방향 도로를 나타낸다. 시작점은 S, 도착점은 D로 표시되어 있다. 굵은 선은 최단 경로를 나타낸다. (아래 그림에 최단 경..