분류 전체보기
-
[백준]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함수를..
-
[백준]5582: 공통 부분 문자열 - JAVA문제풀이/백준 2021. 6. 1. 10:53
[백준]5582: 공통 부분 문자열 https://www.acmicpc.net/problem/5582 5582번: 공통 부분 문자열 두 문자열이 주어졌을 때, 두 문자열에 모두 포함된 가장 긴 공통 부분 문자열을 찾는 프로그램을 작성하시오. 어떤 문자열 s의 부분 문자열 t란, s에 t가 연속으로 나타나는 것을 말한다. 예를 들 www.acmicpc.net 풀이 문제 이름에 맞게 "공통 부분 문자열"을 구하는 문제이다. LCS랑 비슷해 보이지만 약간 다르다. LCS는 부분 수열이 되는 수열 중 가장 긴 수열을 찾는 것이고, 이 문제는 공통 부분 문자열 중에 가장 긴 수열을 찾는 것이다. 두 이론의 차이는 예를 들어 다음과 같다. str1이 ABC이고 str2가 AC일때 LCS를 구하면 2가되며 LCS는 ..
-
[백준]6479: 전력난 - JAVA문제풀이/백준 2021. 5. 31. 11:36
[백준]6479: 전력난 https://www.acmicpc.net/problem/6497 6497번: 전력난 성진이는 한 도시의 시장인데 거지라서 전력난에 끙끙댄다. 그래서 모든 길마다 원래 켜져 있던 가로등 중 일부를 소등하기로 하였다. 길의 가로등을 켜 두면 하루에 길의 미터 수만큼 돈이 들 www.acmicpc.net 풀이 방향성이 없는 n개의 간선으로 연결된 m개의 노드 중에서 MST를 비용을 찾는 문제이다. MST를 찾아야 하는것은 맞지만 결과로 반환하는 값은 MST값이 아니다. 문제를 읽어보면 결국 최소 비용을 가질 수 있는 불이 켜진 길로만 이동할때 절약할 수 있는 최대 비용을 찾는것이다. 즉, 전체 비용에서 최소비용을 뺀 값이 우리가 구하려고 하는 값이 된다. 그러므로 prim이나 kru..
-
[백준]16234: 인구 이동 - JAVA문제풀이/백준 2021. 5. 30. 15:37
문제 https://www.acmicpc.net/problem/16234 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모 www.acmicpc.net 풀이 구현 능력에 더불어 탐색 알고리즘을 활용할 수 있는지 묻는 문제이다. 구현 문제들은 문제가 길고 복잡한 경우가 많아 세분화 하여 구현해 주기 위해 먼저 어떤 순서대로 구현할지 작업을 분류하고 시작하는 것이 좋다. 나는 아래와 같은 순서로 구현해 주었다. 1. 순회를 하며 방문하지 않은 노드를 방문한다. 이 과정은 모든 노드를 방문할 때까지 반복된다. 2. 노드를 방문할 때..