본문 바로가기

알고리즘/백준 문제풀이

 (38)
백준 9095번 - 1, 2, 3 더하기 https://www.acmicpc.net/problem/9095 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net 문제 접근 주어진 정수를 1,2,3의 합으로 나타내는 경우의 수를 구하는 문제 주어진 정수를 1,2,3으로 쪼개는 경우의 수 :: 재귀를 통해 구현 재귀함수의 구성요소는 다음과 같다. 1. 다음 경우를 호출 2. 정답을 찾은 경우 return 3. 불가능한 경우 return(문제의 조건을 위배한 경우, 절대로 답을 구할 수 없는 경우) 정답 코드 import java.util.Scanner fun main(args: Array): Unit = with(Scanner(System.`in`)) { ..
백준 2606-바이러스(Kotlin) https://www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어 www.acmicpc.net 문제 접근 딱 그래프 탐색을 할 수 있는지를 물어보는 문제 시간복잡도 인접 리스트를 활용한dfs로 계산시 O(V+E)인데, 간선이 얼마나 주어지는 지를 모르겠다.. 인접 행렬로 구현하면 O(V^2)인데, 이때 V(노드, 여기선 컴퓨터의 수)는 100이하니깐 100^2으로 여유롭다. 그보다도 O(V+E)가 더 작으니깐 어떤걸쓰든 그래프 탐색을 할 줄 아느냐를 물어보는 문제인듯 인접리스트 + DFS로 구현..
백준 1260-DFS와 BFS(Kotlin) https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 문제 접근 기본적으로 dfs와 bfs를 구현하는 문제입니다. 처음 dfs와 bfs를 연습할때 구현하는 방법을 연습하기 좋아보입니다. 정답코드 import java.util.* var node = 0 var g = Array(node+1){ArrayList()} val check = BooleanArray(1001) var que: Queue = LinkedLi..
백준 2576 색종이-2(Kotlin) https://www.acmicpc.net/problem/2567 2567번: 색종이 - 2 가로, 세로의 크기가 각각 100인 정사각형 모양의 흰색 도화지가 있다. 이 도화지 위에 가로, 세로의 크기가 각각 10인 정사각형 모양의 검은색 색종이를 색종이의 변과 도화지의 변이 평행하도록 www.acmicpc.net 문제 접근 검은색 영역의 둘레를 구하는 문제 하얀 영역은 0 검은 영역은 1로 처리 1에 인접한 0의 개수를 구하는 문제 정답 코드 import java.util.* fun main(args: Array): Unit = with(Scanner(System.`in`)) { //이차원 배열 위에 0과 1로 표시 val arr = Array(101){IntArray(101)} var n = next..
백준 2246 - 콘도 선정(Kotlin) https://www.acmicpc.net/problem/2246 2246번: 콘도 선정 첫째 줄에 콘도의 개수를 나타내는 자연수 N(1 ≤ N ≤ 10,000)이 주어진다. 다음 N개의 줄에는 각 콘도에 대한 정보를 나타내는 두 정수 D(1 ≤ D ≤ 10,000), C(1 ≤ C ≤ 10,000)가 주어진다. D는 그 콘도의 www.acmicpc.net 문제 접근 입력값을 모두 비교해야되기때문에 배열로 저장 후보군이 될 수 없는 경우는 건너뛰어가며 가능한 경우의 수를 셈 정답 코드 import java.util.* fun main(args: Array): Unit = with(Scanner(System.`in`)) { val n = nextInt() //1. 더 가까운데 숙박비가 더 싼 경우 //2...
백준 1051-숫자 정사각형(Kotlin) https://www.acmicpc.net/problem/1051 1051번: 숫자 정사각형 N×M크기의 직사각형이 있다. 각 칸에는 한 자리 숫자가 적혀 있다. 이 직사각형에서 꼭짓점에 쓰여 있는 수가 모두 같은 가장 큰 정사각형을 찾는 프로그램을 작성하시오. 이때, 정사각형은 행 www.acmicpc.net 문제 접근 문제 조건에 맞는 정사각형 중 크기가 최대인 정사각형의 크기를 구하는 문제 한 변의 최대길이에서 점점 내려가며 조건을 만족하면 최대값을 비교하는 식으로 구현 근데 풀기전에 다른사람 코드를 봐버림... 정답 코드 import java.util.* import kotlin.math.max import kotlin.math.min //꼭짓점의 값이 모두 같은 가장 큰 크기의 정사각형 찾기 f..
백준 2628 - 종이 자르기(Kotlin) https://www.acmicpc.net/problem/2628 2628번: 종이자르기 아래 과 같이 직사각형 모양의 종이가 있다. 이 종이는 가로방향과 세로 방향으로 1㎝마다 점선이 그어져 있다. 가로 점선은 위에서 아래로 1번부터 차례로 번호가 붙어 있고, 세로 점선 www.acmicpc.net 문제 접근 종이를 배열로 표현해서 자른 부분을 1로 처리한 다음 연속되는 0의 최대값을 곱해주면 됨 -> 어차피 한줄 끝까지 자르니깐 이차원 배열이 아닌 가로세로 각각 일차원 배열로 선언해서 연속되는 0의 개수의 최대값을 구하면 될듯? 정답 코드 import java.util.* fun main(args: Array): Unit = with(Scanner(System.`in`)) { val n = nextI..
백준 2563 - 색종이(Kotlin) https://www.acmicpc.net/problem/2563 2563번: 색종이 가로, 세로의 크기가 각각 100인 정사각형 모양의 흰색 도화지가 있다. 이 도화지 위에 가로, 세로의 크기가 각각 10인 정사각형 모양의 검은색 색종이를 색종이의 변과 도화지의 변이 평행하도록 www.acmicpc.net 문제 접근 좌표를 이차원 배열로 만들어 검은색 종이가 가리는 범위를 구하는 문제 검은색 범위가 가리는 부분을 1씩 증가시켜 전체 이차원배열중 0이 아닌부분의 개수를 구하는 식으로 해결함 정답 코드 import java.util.* fun main(args: Array): Unit = with(Scanner(System.`in`)) { var n = nextInt() val arr = Array(101..

티스토리툴바