알고리즘 - Baekjoon
[백준] 14940번 : 쉬운 최단거리 Silver1(실버1) - JAVA[자바]
[Silver I] 쉬운 최단거리 - 14940 문제 링크 성능 요약 메모리: 81452 KB, 시간: 664 ms 분류 너비 우선 탐색, 그래프 이론, 그래프 탐색 제출 일자 2023년 12월 12일 10:15:01 문제 설명 지도가 주어지면 모든 지점에 대해서 목표지점까지의 거리를 구하여라. 문제를 쉽게 만들기 위해 오직 가로와 세로로만 움직일 수 있다고 하자. 입력 지도의 크기 n과 m이 주어진다. n은 세로의 크기, m은 가로의 크기다.(2 ≤ n ≤ 1000, 2 ≤ m ≤ 1000) 다음 n개의 줄에 m개의 숫자가 주어진다. 0은 갈 수 없는 땅이고 1은 갈 수 있는 땅, 2는 목표지점이다. 입력에서 2는 단 한개이다. 출력 각 지점에서 목표지점까지의 거리를 출력한다. 원래 갈 수 없는 땅인 ..
[백준] 2668번 : 숫자고르기 Gold5(골드5) - JAVA[자바]
[Gold V] 숫자고르기 - 2668 문제 링크 성능 요약 메모리: 11584 KB, 시간: 80 ms 분류 깊이 우선 탐색, 그래프 이론, 그래프 탐색 제출 일자 2023년 12월 12일 09:34:56 문제 설명 세로 두 줄, 가로로 N개의 칸으로 이루어진 표가 있다. 첫째 줄의 각 칸에는 정수 1, 2, …, N이 차례대로 들어 있고 둘째 줄의 각 칸에는 1이상 N이하인 정수가 들어 있다. 첫째 줄에서 숫자를 적절히 뽑으면, 그 뽑힌 정수들이 이루는 집합과, 뽑힌 정수들의 바로 밑의 둘째 줄에 들어있는 정수들이 이루는 집합이 일치한다. 이러한 조건을 만족시키도록 정수들을 뽑되, 최대로 많이 뽑는 방법을 찾는 프로그램을 작성하시오. 예를 들어, N=7인 경우 아래와 같이 표가 주어졌다고 하자. 이 ..
[백준] 10431번 : 줄세우기 Silver5(실버5) - JAVA[자바]
[Silver V] 줄세우기 - 10431 문제 링크 성능 요약 메모리: 15768 KB, 시간: 148 ms 분류 구현, 시뮬레이션 제출 일자 2023년 12월 11일 10:43:22 문제 설명 초등학교 선생님 강산이는 아이들을 데리고 단체로 어떤 일을 할 때 불편함이 없도록 새로 반에 배정받은 아이들에게 키 순서대로 번호를 부여한다. 번호를 부여할 땐 키가 가장 작은 아이가 1번, 그 다음이 2번, ... , 가장 큰 아이가 20번이 된다. 강산이네 반 아이들은 항상 20명이며, 다행히도 같은 키를 가진 학생은 한 명도 없어서 시간이 조금 지나면 아이들은 자기들의 번호를 인지하고 한 줄로 세우면 제대로 된 위치에 잘 서게 된다. 하지만 매년 첫 며칠간 강산이와 강산이네 반 아이들은 자기가 키 순으로 ..
[백준] 2331번 : 반복수열 Silver4(실버 4) - JAVA[자바]
[Silver IV] 반복수열 - 2331 문제 링크 성능 요약 메모리: 12884 KB, 시간: 112 ms 분류 구현, 수학 제출 일자 2023년 12월 10일 16:35:44 문제 설명 다음과 같이 정의된 수열이 있다. D[1] = A D[n] = D[n-1]의 각 자리의 숫자를 P번 곱한 수들의 합 예를 들어 A=57, P=2일 때, 수열 D는 [57, 74(=52+72=25+49), 65, 61, 37, 58, 89, 145, 42, 20, 4, 16, 37, …]이 된다. 그 뒤에는 앞서 나온 수들(57부터가 아니라 58부터)이 반복된다. 이와 같은 수열을 계속 구하다 보면 언젠가 이와 같은 반복수열이 된다. 이때, 반복되는 부분을 제외했을 때, 수열에 남게 되는 수들의 개수를 구하는 프로그램..
[백준] 4963번 : 섬의 개수 Silver2(실버 2) - JAVA[자바]
[Silver II] 섬의 개수 - 4963 문제 링크 성능 요약 메모리: 31412 KB, 시간: 316 ms 분류 그래프 이론, 그래프 탐색, 너비 우선 탐색, 깊이 우선 탐색 제출 일자 2023년 12월 10일 16:09:48 문제 설명 정사각형으로 이루어져 있는 섬과 바다 지도가 주어진다. 섬의 개수를 세는 프로그램을 작성하시오. 한 정사각형과 가로, 세로 또는 대각선으로 연결되어 있는 사각형은 걸어갈 수 있는 사각형이다. 두 정사각형이 같은 섬에 있으려면, 한 정사각형에서 다른 정사각형으로 걸어서 갈 수 있는 경로가 있어야 한다. 지도는 바다로 둘러싸여 있으며, 지도 밖으로 나갈 수 없다. 입력 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 ..
[백준] 10451번 : 순열 사이클 Silver 3(실버 3) - JAVA[자바]
[Silver III] 순열 사이클 - 10451 문제 링크 성능 요약 메모리: 310056 KB, 시간: 1696 ms 분류 그래프 이론, 순열 사이클 분할 제출 일자 2023년 12월 10일 15:30:38 문제 설명 1부터 N까지 정수 N개로 이루어진 순열을 나타내는 방법은 여러 가지가 있다. 예를 들어, 8개의 수로 이루어진 순열 (3, 2, 7, 8, 1, 4, 5, 6)을 배열을 이용해 표현하면 (1234567832781456)\(\begin{pmatrix} 1 & 2 &3&4&5&6&7&8 \\ 3& 2&7&8&1&4&5&6 \end{pmatrix}\) 와 같다. 또는, Figure 1과 같이 방향 그래프로 나타낼 수도 있다. 순열을 배열을 이용해 (1…i…nπ1…πi…πn)\(\begin{..
[백준] 10819번 : 차이를 최대로 Silver2(실버2) - JAVA[자바]
[Silver II] 차이를 최대로 - 10819 문제 링크 성능 요약 메모리: 12484 KB, 시간: 104 ms 분류 백트래킹, 브루트포스 알고리즘 제출 일자 2023년 12월 1일 09:40:35 문제 설명 N개의 정수로 이루어진 배열 A가 주어진다. 이때, 배열에 들어있는 정수의 순서를 적절히 바꿔서 다음 식의 최댓값을 구하는 프로그램을 작성하시오. |A[0] - A[1]| + |A[1] - A[2]| + ... + |A[N-2] - A[N-1]| 입력 첫째 줄에 N (3 ≤ N ≤ 8)이 주어진다. 둘째 줄에는 배열 A에 들어있는 정수가 주어진다. 배열에 들어있는 정수는 -100보다 크거나 같고, 100보다 작거나 같다. 출력 첫째 줄에 배열에 들어있는 수의 순서를 적절히 바꿔서 얻을 수 있는..
[백준] 11724번 : 연결 요소의 개수 Silver2(실버2) - JAVA[자바]
[Silver II] 연결 요소의 개수 - 11724 문제 링크 성능 요약 메모리: 118528 KB, 시간: 484 ms 분류 그래프 이론, 그래프 탐색, 너비 우선 탐색, 깊이 우선 탐색 제출 일자 2023년 11월 30일 10:00:16 문제 설명 방향 없는 그래프가 주어졌을 때, 연결 요소 (Connected Component)의 개수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주어진다. 출력 첫째 줄에 연결 요소의 개수를 출력한다. 풀이 과정 1. main 함수..