1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가 www.acmicpc.net 풀이 그래프 최단 경로를 구하는 다익스트라 알고리즘을 사용하여 푸는 문제다. 인접리스트, PriorityQueue, 각 정점까지의 최단 경로를 저장하는 dis 배열을 사용하여 풀었으며 자세한 풀이는 이전에 풀었던 문제와 같기 때문에 설명은 생략하겠다. [프로그래머스] Lv.2 : 배달 (그래프 최단 경로 알고리즘) - 자바[Java] [프로그래머스] Lv.2 : 배달 (그래프 최단 경로 알고리즘) - 자바[Java] http..

10816번: 숫자 카드 2첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10,www.acmicpc.net 풀이Map을 사용하면 간단하게 풀 수 있지만, 이분 탐색으로도 풀 수 있다.다만 이 문제는 배열에 들어가있는 숫자의 개수를 구해야 하는데, 기본적인 이분 탐색 코드는 숫자의 위치(인덱스)만을 구할 뿐, 배열에 중복된 숫자가 있을 경우 숫자의 개수를 구하지는 못한다.그렇기 때문에 기본적인 이분 탐색 코드를 변형해서 중복된 숫자의 왼쪽 끝 위치(lower bound)와 오른쪽 끝 위치(upper bound)를 구해 중복된 숫자의 개수를 ..

10830번: 행렬 제곱크기가 N*N인 행렬 A가 주어진다. 이때, A의 B제곱을 구하는 프로그램을 작성하시오. 수가 매우 커질 수 있으니, A^B의 각 원소를 1,000으로 나눈 나머지를 출력한다.www.acmicpc.net풀이재귀함수를 이용한 분할정복으로 문제를 풀 수 있다.n, b, arr 배열 값을 입력받은 다음 divideAndConquer() 재귀함수를 호출하여 arr의 b제곱(result 배열)을 구한다. 주의할 점B의 범위는 1 ≤ B ≤ 100,000,000,000 이기 때문에 int로 값을 받으면 NumberFormatException이 발생한다. 그래서 Long.parseLong을 사용하여 long으로 값을 받아야 한다.A^B의 각 원소를 1,000으로 나눈 나머지를 출력해야 하므로,..

2630번: 색종이 만들기 첫째 줄에는 전체 종이의 한 변의 길이 N이 주어져 있다. N은 2, 4, 8, 16, 32, 64, 128 중 하나이다. 색종이의 각 가로줄의 정사각형칸들의 색이 윗줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진다. www.acmicpc.net 풀이 재귀함수를 이용한 분할정복을 사용하여 문제를 풀 수 있다. main 함수에서 전체 종이의 한 변의 길이 N과 색종이의 위치 정보를 입력받고 divideAndConquer() 재귀 함수를 호출하여 (0, 0)부터 색종이 배열 탐색을 시작한다. divideAndConquer() 함수 내에서 인자로 받은 시작위치부터 색종이 배열을 탐색하다가, 시작 위치의 색과 다른 색을 발견하면 위 그림과 같이 색종이를 4등분하여 새로운 탐색을 시작해..

https://www.acmicpc.net/problem/9184 9184번: 신나는 함수 실행입력은 세 정수 a, b, c로 이루어져 있으며, 한 줄에 하나씩 주어진다. 입력의 마지막은 -1 -1 -1로 나타내며, 세 정수가 모두 -1인 경우는 입력의 마지막을 제외하면 없다.www.acmicpc.net풀이반복적인 재귀 호출을 방지하기 위해, w(a, b, c)의 반환값을 저장하는 3차원 dp 배열을 사용한다.이 때 -50 ≤ a, b, c ≤ 50 이므로, 인덱스를 0부터 100까지 사용하기 위해 배열의 크기를 101x101x101만큼 할당하여 w(a, b, c)의 반환값을 dp[a+50][b+50][c+50]에 저장한다.  로직1. int형 3차원 배열 dp를 선언하고, 크기를 101x101x101만..

https://www.acmicpc.net/problem/1932 1932번: 정수 삼각형 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. www.acmicpc.net 풀이 맨 위층부터 시작해서 아래에 있는 수 중 하나를 선택하여 아래층으로 내려올 때, 이제까지 선택된 수의 합이 최대가 되는 경로에 있는 수의 합을 구해야 한다. 아래층으로 내려올 때, 아래층에 있는 수에서 위층의 대각선 왼쪽 또는 대각선 오른쪽에 있는 것 중에서만 선택할 수 있다. 즉, 현재 위치를 기준으로 위층의 대각선 왼쪽 또는 대각선 오른쪽에 있는 것 중 최댓값을 선택하여 그 수와 현재 위치의 수를 더한 값을 현재 위치의 배열에 저장하면 된다. 예시) 7 3 8..

https://www.acmicpc.net/problem/14503 14503번: 로봇 청소기 로봇 청소기가 주어졌을 때, 청소하는 영역의 개수를 구하는 프로그램을 작성하시오. 로봇 청소기가 있는 장소는 N×M 크기의 직사각형으로 나타낼 수 있으며, 1×1크기의 정사각형 칸으로 나누어 www.acmicpc.net 풀이 문제에서 주어진 대로 로봇 청소기의 동작을 구현하면 된다. 로직 1. static 변수로 n, m, cnt, room, dr, dc를 선언한다. cnt는 로봇 청소기가 청소하는 칸의 개수로 정답을 의미한다. room은 청소하는 영역의 상태 정보를 저장하는 2차원 배열로, 아직 청소하지 않은 경우에는 0, 벽인 경우에는 1, 청소한 경우에는 2를 저장한다. 1차원 배열 dr과 dc는 방향 배..

https://www.acmicpc.net/problem/14501 14501번: 퇴사첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다.www.acmicpc.net풀이상담을 할 수 있는 가능한 모든 경우를 구한 다음 그 중에서 최대 수익을 구해야 한다. 예시를 들어 설명하겠다. 먼저 1일에 상담을 한다고 가정했을 경우(현재 수익 10), 2, 3일은 할 수 없으므로 4일로 넘어간다. 4일에 상담을 한다고 가정하면(현재 수익 30), 5일로 넘어가고 또 이때 5일에 상담을 한다고 가정하면(현재 수익 45), 7일로 넘어간다. 7일에는 상담을 할 수 없으므로 총 수익은 45가 된다.총 수익을 구한 다음 가장 최근 분기였던 5일째로 돌아간다. 5일에 상담을 하지 않는다고 가정하면(현재 수익 30), 6일..

https://www.acmicpc.net/problem/1969 1969번: DNA DNA란 어떤 유전물질을 구성하는 분자이다. 이 DNA는 서로 다른 4가지의 뉴클레오티드로 이루어져 있다(Adenine, Thymine, Guanine, Cytosine). 우리는 어떤 DNA의 물질을 표현할 때, 이 DNA를 이루는 뉴클레오 www.acmicpc.net 풀이 입력으로 들어온 모든 DNA와 Hamming Distance의 합이 가장 작은 DNA 를 출력해야 한다. 뉴클레오티드는 총 4가지이므로, 입력으로 들어온 n개의 DNA의 각 자리에 있는 글자들을 비교하여, Hamming Distance의 합이 가장 작은 뉴클레오티드를 찾으면 된다. 로직 1. n과 m을 입력받는다. 2. 입력으로 들어오는 DNA 문..

https://www.acmicpc.net/problem/9205 9205번: 맥주 마시면서 걸어가기 송도에 사는 상근이와 친구들은 송도에서 열리는 펜타포트 락 페스티벌에 가려고 한다. 올해는 맥주를 마시면서 걸어가기로 했다. 출발은 상근이네 집에서 하고, 맥주 한 박스를 들고 출발한다. www.acmicpc.net 풀이 맥주 한 박스에는 맥주가 20개 들어있으며 50미터에 한 병씩 마시기 때문에 최대 1000m를 갈 수 있다. 즉, 처음 출발할 때와 편의점에 들렀을 때 최대 1000m를 갈 수 있다. 처음 출발할 때 1000m 이내로 아직 가지 않은 편의점이 있다면 그 편의점으로 가고, 이 과정을 반복해서 페스티벌 장소에 도착할 수 있다면 happy를 출력하고, 갈 수 없다면 sad를 출력하면 된다. ..

https://www.acmicpc.net/problem/15787 15787번: 기차가 어둠을 헤치고 은하수를 입력의 첫째 줄에 기차의 수 N(1 ≤ N ≤ 100000)과 명령의 수 M(1 ≤ M ≤ 100000)가 주어진다. 이후 두 번째 줄부터 M+1번째 줄까지 각 줄에 명령이 주어진다. www.acmicpc.net 풀이 기차의 상태를 저장하는 2차원 배열을 선언한 후, 입력하는 명령에 따라 기차의 상태를 변경하면 된다. 그 후 모든 기차를 탐색하여 기차의 상태가 중복되는게 있는지 검사한다. 로직 1. n과 m을 입력받는다. 2. 기차의 상태를 저장하는 boolean형 2차원 배열 train을 선언하고, n X 20 크기로 할당한다. 승객이 앉아있으면 해당 위치에 true, 승객이 없으면 fals..

https://www.acmicpc.net/problem/2615 2615번: 오목오목은 바둑판에 검은 바둑알과 흰 바둑알을 교대로 놓아서 겨루는 게임이다. 바둑판에는 19개의 가로줄과 19개의 세로줄이 그려져 있는데 가로줄은 위에서부터 아래로 1번, 2번, ... ,19번의 번호www.acmicpc.net풀이바둑판의 상태를 입력받은 후, 검은색 또는 흰색이 이기는지 출력하고 가장 왼쪽에 있는 바둑알의 위치를 출력한다. 로직1. 바둑판의 상태를 입력받는다.2. 이중 for문을 사용하여 바둑판을 왼쪽 위부터 탐색하고, 바둑알이 놓인 위치인 경우 check 함수를 호출하여 오목이 된 경우 검은색이 이겼을 경우에는 1을, 흰색이 이겼을 경우에는 2를 출력한다. 그리고 현재 위치를 출력하고 프로그램을 종료한다...