알고리즘 - Baekjoon/Silver

[백준] 2630번 : 색종이 만들기 Silver2(실버2) - JAVA[자바]

[Silver II] 색종이 만들기 - 2630 문제 링크 성능 요약 메모리: 13152 KB, 시간: 108 ms 분류 분할 정복, 재귀 제출 일자 2023년 12월 12일 10:44:08 문제 설명 아래 과 같이 여러개의 정사각형칸들로 이루어진 정사각형 모양의 종이가 주어져 있고, 각 정사각형들은 하얀색으로 칠해져 있거나 파란색으로 칠해져 있다. 주어진 종이를 일정한 규칙에 따라 잘라서 다양한 크기를 가진 정사각형 모양의 하얀색 또는 파란색 색종이를 만들려고 한다. 전체 종이의 크기가 N×N(N=2k, k는 1 이상 7 이하의 자연수) 이라면 종이를 자르는 규칙은 다음과 같다. 전체 종이가 모두 같은 색으로 칠해져 있지 않으면 가로와 세로로 중간 부분을 잘라서 의 I, II, III, IV와 같이 똑..

[백준] 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는 단 한개이다. 출력 각 지점에서 목표지점까지의 거리를 출력한다. 원래 갈 수 없는 땅인 ..

[백준] 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 함수..