문제풀이
-
[백준]3980: 선발 명단 - JAVA문제풀이/백준 2021. 6. 18. 11:20
[백준]3980: 선발 명단 3980번: 선발 명단 각각의 테스트 케이스에 대해서, 모든 포지션의 선수를 채웠을 때, 능력치의 합의 최댓값을 출력한다. 항상 하나 이상의 올바른 라인업을 만들 수 있다. www.acmicpc.net 풀이 모든 포지션으로 선수를 채웠을때, 능력치의 최댓값을 출력하는 문제로 백트랙킹 유형을 활용하여 문제를 풀었다. 헤당 선수를 뽑았는지 아직 뽑지 않았는지 확인해기 위해 visited 배열을 구현해 주었고, 선수를 뽑을 때마다 능력치의 합을 누적시켜 주었다. 선수를 뽑을때 문제의 조건에 따라 능력치가 0인 선수는 뽑지 않도록 한다. 모든 선수에게 포지션을 지정하는데 성공했다면 pos값이 11이 되었을 것이고, 이때 max값을 현재 total값과 비교하여 지정한 다음 되돌아가 다..
-
[백준]17836: 공주님을 구해라! - JAVA문제풀이/백준 2021. 6. 15. 13:22
[백준]17836: 공주님을 구해라! 17836번: 공주님을 구해라! 용사는 마왕이 숨겨놓은 공주님을 구하기 위해 (N, M) 크기의 성 입구 (1,1)으로 들어왔다. 마왕은 용사가 공주를 찾지 못하도록 성의 여러 군데 마법 벽을 세워놓았다. 용사는 현재의 가지고 있는 www.acmicpc.net 풀이 탐색을 하면서 최단 경로를 찾되, 그람의 유무에 따라 경로가 달라질 수 있으므로 그람의 유무에 나눠 탐색을 진행하면 되는 문제이다. 최단 시간을 요구하므로 BFS탐색을 활용하였다. 이 문제에서 경로를 탐색할 때 필요한 값은 다음과 같다. X좌표, Y좌표, 현재 탐색 깊이, 그람의 유무 해당 정보들을 클래스로 만들어 주었다. 탐색을 하는 중에는, 그람의 유무에 따라 작업을 나눠주었다. 🔹 그람이 없을때 이동..
-
[백준]1477: 휴게소 세우기 - JAVA문제풀이/백준 2021. 6. 14. 17:29
[백준]1477: 휴게소 세우기 풀이 딱 보자마자 이분탐색을 통해 풀어야 겠다는 생각이 들지 않았어서 풀이하는데 시간이 좀 걸렸다. 이분탐색 유형에 아직 익숙하지 않아서 그런 것 같다. 이 문제는 휴게소의 간격을 기준으로 이분탐색을 진행한 다음 해당 간격이 형성되도록 M개의 휴게소를 생성할 수 있을 때의 최소값을 찾는 문제이다. 예제 입력1을 예시로 살펴보자. 휴게소가 설치될 수 있는구간은 다음과 같다. 1 ~ 81 83 ~ 200 202 ~ 410 412 ~ 554 556 ~ 621 623 ~ 754 756 ~ 799 휴게소의 위치와 0, L을 포함한 값을 배열에 담아 정렬시켜준다. (범위 값 계산을 하기 위해) 이때, 휴게소 간격의 최소값은 0, 최대값은 L이 된다. 이제 이분 탐색을 시작한다. 탐색..
-
[백준]2661: 좋은 수열 - JAVA문제풀이/백준 2021. 6. 14. 11:31
[백준]2661: 좋은 수열 2661번: 좋은수열 첫 번째 줄에 1, 2, 3으로만 이루어져 있는 길이가 N인 좋은 수열들 중에서 가장 작은 수를 나타내는 수열만 출력한다. 수열을 이루는 1, 2, 3들 사이에는 빈칸을 두지 않는다. www.acmicpc.net 풀이 문제의 조건에 제시된 좋은 수열의 조건을 만족하면서 가장 작은 N자릿수 를 반환하는 문제이다. 뽑을 수 있는 범위의 숫자는 1~3 밖에 없으므로 start 값을 1, end 값을 3으로 지정하였다. 숫자를 하나씩 뽑는 과정을 backtracking 함수라고 이름 붙였지만, 조건에 맞는 수를 확인하며 하나씩 뽑아주기 때문에 백트랙킹 보다는 순차적으로 순열 방법으로 수를 뽑아준 풀이라고 봐야 할 것 같다. (이럴거면 이름을 permutation..
-
[백준]14675: 단절점과 단절선 - JAVA문제풀이/백준 2021. 6. 11. 10:46
[백준]14675: 단절점과 단절선 14675번: 단절점과 단절선 프로그램의 입력은 표준 입력으로 받는다. 입력의 첫 줄에는 트리의 정점 개수 N이 주어진다. (2 ≤ N ≤ 100,000) 트리의 정점은 1번부터 n번까지 존재한다. 다음 줄부터 N-1개의 줄에 걸쳐 간선의 정 www.acmicpc.net 풀이 이 문제 트리의 성질을 잘 알고있다면 탐색 알고리즘을 사용하지 않고도 풀 수 있는 문제이다. 이 문제를 푸는데 필요한 트리의 성질은 다음과 같다. 트리는 사이클이 없고, 모든 정점이 연결되어 있다. (문제에 나와있다.) N개의 정점이 있을때 N-1개의 간선을 가진다. 입력 받은 정보는 현재 '트리'인 상태이며, 해당 트리가 두 부분으로 나눠지는지 확인하면 된다. 우선, t에 2가 입력되었을 때를 ..
-
[프로그래머스]모두 0으로 만들기 - JAVA문제풀이/프로그래머스 2021. 6. 8. 11:31
[프로그래머스]모두 0으로 만들기 - JAVA https://programmers.co.kr/learn/courses/30/lessons/76503 코딩테스트 연습 - 모두 0으로 만들기 각 점에 가중치가 부여된 트리가 주어집니다. 당신은 다음 연산을 통하여, 이 트리의 모든 점들의 가중치를 0으로 만들고자 합니다. 임의의 연결된 두 점을 골라서 한쪽은 1 증가시키고, 다른 한 programmers.co.kr 풀이 많이 해메였던 문제이다. 모든 정점의 가중치를 0으로 만들려면 필요한 아이디어를 먼저 살펴보자. 모든 가중치의 합이 0이된다. (0이 되지 않으면 애초에 모든 정점의 가중치를 0으로 만들 수 없다) 한 방향으로 탐색을 진행하면서 가중치 연산을 해야 한다. (목적 노드를 하나 정해두고 나머지 리..
-
[백준]20924: 트리의 기둥과 가지 - JAVA문제풀이/백준 2021. 6. 4. 13:06
[백준]20924: 트리의 기둥과 가지 https://www.acmicpc.net/problem/20924 20924번: 트리의 기둥과 가지 첫 번째 줄에는 노드의 개수 $N$($1 \le N \le 200\,000$)과 루트 노드의 번호 $R$($1 \le R \le N$)이 주어진다. 이후 $N-1$개의 줄에 세 개의 정수 $a$, $b$, $d$($1 \le a, b \le N$, $ a \ne b$)가 주어진다. 이는 $a$번 www.acmicpc.net 풀이 처음에는 나무 그림이 있길래 직접 트리를 구현하는 문제인가? 싶었는데 읽어보니 그냥 탐색 문제였다. 모든 노드를 탐색하며 조건에 맞는 노드를 찾아주어야 하므로 DFS탐색을 활용하여 문제를 풀었다. DFS알고리즘은 크게 두 함수를 사용하였다...
-
[백준]16197: 두 동전 - JAVA문제풀이/백준 2021. 6. 2. 11:27
[백준]16197: 두 동전 https://www.acmicpc.net/problem/16197 16197번: 두 동전 N×M 크기의 보드와 4개의 버튼으로 이루어진 게임이 있다. 보드는 1×1크기의 정사각형 칸으로 나누어져 있고, 각각의 칸은 비어있거나, 벽이다. 두 개의 빈 칸에는 동전이 하나씩 놓여져 있고, www.acmicpc.net 풀이 조건에 맞게 동전들을 이동하다가 하나의 동전만 떨어뜨릴 수 있는 최소값을 찾는 문제이므로 BFS탐색을 활용하였다. 보드를 입력 받을 때 동전의 위치는 Coin객체를 생성하여 따로 저장해 주었다. 방문체크는 boolean배열을 4차원으로 선언하였다. 두 개의 동전이 한번에 움직이므로 동시에 체크해줄 필요가 있어 4차원으로 선언하여 사용한다. 그럼 이제 BFS함수를..