PS(Problem Solving)/BOJ244

• [백준/BOJ] 2437번: 저울 문제 https://www.acmicpc.net/problem/2437 2437번: 저울 하나의 양팔 저울을 이용하여 물건의 무게를 측정하려고 한다. 이 저울의 양 팔의 끝에는 물건이나 추를 올려놓는 접시가 달려 있고, 양팔의 길이는 같다. 또한, 저울의 한쪽에는 저울추들만 놓 www.acmicpc.net 해설 문제의 예시를 봐보자. 3, 1, 6, 2, 7, 30, 1이 있을 때 이를 오름차순으로 정렬해보면 1, 1, 2, 3, 6, 7, 30이 된다. 만약 가장 가벼운 추에 1이 없다면, 우리가 측정 못하는 가장 작은 무게는 1이 된다. 차례대로 봐보면, 첫번째 추로 1을 측정할 수 있다. 두번째 추를 이용해 2도 측정할 수 있다. 세번째 추를 이용하여 3, 4를 측정할 수 있다. 4번째 추를 사용하.. PS(Problem Solving)/BOJ 2022. 11. 1.

• 

  [백준/BOJ] 1926번: 그림 문제 https://www.acmicpc.net/problem/1926 1926번: 그림 어떤 큰 도화지에 그림이 그려져 있을 때, 그 그림의 개수와, 그 그림 중 넓이가 가장 넓은 것의 넓이를 출력하여라. 단, 그림이라는 것은 1로 연결된 것을 한 그림이라고 정의하자. 가로나 세로 www.acmicpc.net 해설 그림이 그려진 영역의 개수와 가장 큰 영역의 넓이를 출력하는 문제이다. bfs를 통해 문제를 풀 수 있다. 입력을 모두 받고, 2중 반복문을 수행하며 아직 방문하지 않은 1이 찾는다. 이러한 1을 찾았다면, bfs를 수행시켜 그림의 영역을 구한다. 그림의 영역을 구하면서 방문 여부 처리를 해주며 이 칸에 또 방문했을 때 bfs를 수행할 일이 없도록 해준다. 이처럼 아직 방문하지 않은 1을 찾.. PS(Problem Solving)/BOJ 2022. 10. 1.

• 

  [백준/BOJ] 1058번: 친구 문제 https://www.acmicpc.net/problem/1058 1058번: 친구 지민이는 세계에서 가장 유명한 사람이 누구인지 궁금해졌다. 가장 유명한 사람을 구하는 방법은 각 사람의 2-친구를 구하면 된다. 어떤 사람 A가 또다른 사람 B의 2-친구가 되기 위해선, 두 사람 www.acmicpc.net 해설 2-친구가 되기 위한 조건은 다음과 같다. 서로 친구이다. 한다리 건너 친구이다. 이 문제는 플로이드 와샬 알고리즘을 이용하여 해결하였다. 우선 자기 자신과는 친구를 맺을 수 없으므로 0으로, 나머지는 INF(987654321)로 초기화하였다. 후에 입력으로 Y값이 들어온다면 그 인덱스를 1로 선언하였다. 이제 플로이드 와샬 알고리즘을 수행시켜 몇다리를 건너 아는 사이인지를 모두 구한다. .. PS(Problem Solving)/BOJ 2022. 9. 25.

• 

  [백준/BOJ] 9205번: 맥주 마시면서 걸어가기 문제 https://www.acmicpc.net/problem/9205 해설 문제에서 상근이는 집에서 맥주 한 박스를 들고 출반한다. 이때 한 박스에는 20개의 맥주가 들어있다. 50미터 당 맥주 한 병을 마시므로 최대 1000미터까지 움직일 수 있고, 이후에는 맥주를 새로 사거나 이미 페스티벌에 도착했어야 한다. 이 문제를 해결하기 위해서는 매허튼 거리를 계속해서 계산해주어야 한다. 맨허튼 거리란 두 좌표 사이의 x 좌표의 차이 + y 좌표의 차이를 뜻한다. 만약 집 위치와 락 페스티벌의 멘허튼 거리가 1000이 안된다면, 맥주 한박스로 페스티벌에 도착할 수 있게 되는 것이다. 하지만 1000이 넘는다면, 중간에 편의점을 들려 맥주를 사야한다. 따라서 집과 편의점의 맨허튼 거리를 구하여 1000이 안된.. PS(Problem Solving)/BOJ 2022. 9. 24.

• 

  [백준/BOJ] 1325번: 효율적인 해킹 문제 https://www.acmicpc.net/problem/1325 graph[a].add(b) 이 과정이 끝났다면 각 컴퓨터마다 dfs 알고리즘을 수행시켜 해킹할 수 있는 컴퓨터의 수를 세면 된다. dfs의 동작 방식은 코드를 보자. 코드 private lateinit var graph: Array private lateinit var visited: BooleanArray private lateinit var hacking: IntArray private var max = 0 fun main() = with(System.`in`.bufferedReader()){ val (computerCnt, trustCnt) = readLine().split(" ").map { it.toInt() } graph.. PS(Problem Solving)/BOJ 2022. 9. 23.

• 

  [백준/BOJ] 9019번: DSLR 문제 https://www.acmicpc.net/problem/9019 9019번: DSLR 네 개의 명령어 D, S, L, R 을 이용하는 간단한 계산기가 있다. 이 계산기에는 레지스터가 하나 있는데, 이 레지스터에는 0 이상 10,000 미만의 십진수를 저장할 수 있다. 각 명령어는 이 레지스터에 www.acmicpc.net 해설 bfs를 이용하는 문제이다. 숫자를 관리하는데 있어, 문자열이 아닌 int형으로 계산하였다. bfs를 수행할 때 사요오디는 Queue에는 두가지 정보가 담기게 된다. 현재 숫자와 여태 진행된 명령어 두가지로 저장된다. 즉, Pair(num, command)가 담기게 된다. 초기값으로는 Pair(startNum, "")이 된다. 각 명령어마다 계산하는 방법을 보자. D -> .. PS(Problem Solving)/BOJ 2022. 9. 23.

• 

  [백준/BOJ] 5014번: 스타트링크 문제 https://www.acmicpc.net/problem/5014 5014번: 스타트링크 첫째 줄에 F, S, G, U, D가 주어진다. (1 ≤ S, G ≤ F ≤ 1000000, 0 ≤ U, D ≤ 1000000) 건물은 1층부터 시작하고, 가장 높은 층은 F층이다. www.acmicpc.net 해설 bfs를 연습하기에 좋은 문제라고 생각된다. 첨에 방문여부처리할 배열의 크기를 어떻게 정할까 고민을 했었는데, 엘레베이터는 건물의 최고층 이후로는 올라갈 수 없으므로 전체 층수 + 1만큼을 배열의 크기로 저장하면 되는 것이었다. bfs를 수행할 큐에는 현재 층수, 움직인 횟수 정보를 담는다. 현재 층수에서 움직일 수 있는 방법은 2가지가 있다. U버튼을 통해 올라가거나, D버튼을 통해 내려가는 것이.. PS(Problem Solving)/BOJ 2022. 9. 22.

• 

  [백준/BOJ] 1389번: 케빈 베이컨의 6단계 법칙 문제 https://www.acmicpc.net/problem/1389 1389번: 케빈 베이컨의 6단계 법칙 첫째 줄에 유저의 수 N (2 ≤ N ≤ 100)과 친구 관계의 수 M (1 ≤ M ≤ 5,000)이 주어진다. 둘째 줄부터 M개의 줄에는 친구 관계가 주어진다. 친구 관계는 A와 B로 이루어져 있으며, A와 B가 친구라는 뜻 www.acmicpc.net 해설 bfs로도 풀 수 있겠지만, 나는 이런 문제를 플로이드 와샬 알고리즘을 사용하여 모두 구해놓은 후 그 값들을 통해 해결하는 편을 좋아한다. 배열에서 자기 자신으로 가는 경우의 수는 0으로 초기화해주고, 나머지는 INF(987654321)의 값으로 초기화해주었다. 후에 입력받은 관계 (a, b라 하자)를 1로 저장한다. 즉, arr[a][b.. PS(Problem Solving)/BOJ 2022. 9. 21.

• 

  [백준/BOJ] 2644번: 촌수계산 문제 https://www.acmicpc.net/problem/2644 2644번: 촌수계산 사람들은 1, 2, 3, …, n (1 ≤ n ≤ 100)의 연속된 번호로 각각 표시된다. 입력 파일의 첫째 줄에는 전체 사람의 수 n이 주어지고, 둘째 줄에는 촌수를 계산해야 하는 서로 다른 두 사람의 번호가 주어 www.acmicpc.net 해설 부모자식 관계가 성립하는지를 저장하기 위해 ArrayList라는 자료형을 가진 graph를 선언하였다. 부모자식을 양방향으로 모두 저장하였다면 dfs를 통해 찾고자 하는 두 사람의 관계가 나올 때까지 dfs 알고리즘을 수행하면 된다. 코드 private lateinit var visited: BooleanArray private val graph = ArrayList.. PS(Problem Solving)/BOJ 2022. 9. 20.

• 

  [백준/BOJ] 2583번: 영역 구하기 문제 https://www.acmicpc.net/problem/2583 2583번: 영역 구하기 첫째 줄에 M과 N, 그리고 K가 빈칸을 사이에 두고 차례로 주어진다. M, N, K는 모두 100 이하의 자연수이다. 둘째 줄부터 K개의 줄에는 한 줄에 하나씩 직사각형의 왼쪽 아래 꼭짓점의 x, y좌표값과 오 www.acmicpc.net 해설 bfs를 이용하여 푸는 문제이다. 풀이 과정을 나눠보면 다음과 같다. 주어지는 좌표에 해당하는 영역을 미리 체크해놓는다. 모든 사각형의 체크가 끝났다면, 처음부터 반복문을 실행하며 아직 방문하지 않았으며, 사각형 영역에 해당하지 않는 곳을 찾는다. 아직 방문하지 않았으며, 사각형 영역에 해당하지 않는 곳에 도달했다면, bfs를 수행하여 영역의 총 크기가 얼마인지 구한.. PS(Problem Solving)/BOJ 2022. 9. 18.

• 

  [백준/BOJ] 1240번: 노드사이의 거리 문제 https://www.acmicpc.net/problem/1240 1240번: 노드사이의 거리 N(2≤N≤1,000)개의 노드로 이루어진 트리가 주어지고 M(M≤1,000)개의 두 노드 쌍을 입력받을 때 두 노드 사이의 거리를 출력하라. www.acmicpc.net 해설 n - 1개의 노드 사이의 거리가 주어지고, m개의 노드 사이의 거리를 구해야 한다. 크루스칼 알고리즘, dfs 등 여러 방법이 있을 수 있지만, 나는 문제를 보자마자 플로이드 와샬 알고리즘을 떠올렸다. n이 크지 않으므로 간단히 모든 노드 사이의 최소 거리를 구해놓고, 구하고자 하는 노드 사이의 거리를 출력하면 된다라고 생각했다. 또한 플로이드 와샬 알고리즘은 구현 방법도 쉽기 때문에 상당히 쉽게 풀은 문제였다. 코드 import.. PS(Problem Solving)/BOJ 2022. 9. 17.

• 

  [백준/BOJ] 1946번: 신입 사원 문제 https://www.acmicpc.net/problem/1946 1946번: 신입 사원 첫째 줄에는 테스트 케이스의 개수 T(1 ≤ T ≤ 20)가 주어진다. 각 테스트 케이스의 첫째 줄에 지원자의 숫자 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개 줄에는 각각의 지원자의 서류심사 성 www.acmicpc.net 해설 문제에서 핵심 문장은 "어떤 지원자 A의 성적이 다른 어떤 지원자 B의 성적에 비해 서류 심사 결과와 면접 성적이 모두 떨어진다면 A는 결코 선발되지 않는다."이다. 즉, 두 성적이 모두 다른 지원자보다 떨어진다면, 그 사람은 면접에서 떨어지게 된다. 문제의 예시 중 첫 번째 테스트케이스를 보자. (3, 2), (1, 4), (4, 1), (2, 3), (5, 5).. PS(Problem Solving)/BOJ 2022. 9. 16.