알고리즘/백준
-
[백준] 2056번 : 작업 - 자바(Java)알고리즘/백준 2022. 6. 17. 00:01
https://www.acmicpc.net/problem/2056 2056번: 작업 수행해야 할 작업 N개 (3 ≤ N ≤ 10000)가 있다. 각각의 작업마다 걸리는 시간(1 ≤ 시간 ≤ 100)이 정수로 주어진다. 몇몇 작업들 사이에는 선행 관계라는 게 있어서, 어떤 작업을 수행하기 위해 www.acmicpc.net 문제 해석 수행해야 할 작업이 10000개 주어집니다. 작업들 사이에서는 선행 관계가 존재합니다. K번 작업에 대해 선행 관계에 있는 작업들은 모두 1 이상 K-1 이하입니다. 선행 관계에 있는 작업이 하나도 없는 작업이 반드시 하나 이상 존재합니다. (1번 작업이 항상 그렇다) 작업들은 동시에도 수행이 가능합니다. 모든 작업을 완료하기 위한 필요한 최소 시간을 구하세요 문제 풀이 전 설..
-
[백준] 10815번 : 숫자 카드 - 자바(JAVA)알고리즘/백준 2022. 6. 15. 00:01
문제 해석 int형 범위내의 N개의 숫자가 주어집니다. 이때 M개의 숫자가 다시 주어지고 M개의 숫자가 N개의 숫자에 존재하는지 탐색하는 문제입니다. 문제 풀이 전 설계 N제한이 50만이기 때문에 O(N^2)은 불가능합니다. 또한 문제에서는 정렬/이분 탐색으로 문제를 해결하라고 제시했지만 더 효율적인 방법인 HashSet을 이용하면 O(1)의 시간복잡도로 해결이 가능할 것 같습니다. 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.*; public class Main_10815_숫자카드 { public static void main(String[] ar..
-
[백준] 1644번 : 소수의 연속합 - 자바(JAVA)알고리즘/백준 2022. 6. 14. 00:01
https://www.acmicpc.net/problem/1644 1644번: 소수의 연속합 첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 4,000,000) www.acmicpc.net 문제 해석 어떤 수 N을 소수의 합으로 나타낼 수 있다면 그 경우의 수를 구하는 문제입니다. 예를 들어보겠습니다. 3은 3 자기 자신으로 한 가지가 가능합니다. 41 = 2 + 3 + 5 + 7 + 11 + 13 , 11 + 13 + 17, 41으로 3가지가 가능합니다. 53 = 5+7+11+13+17 = 53으로 세 가지가 가능합니다. 소수를 모두 구한 다음에 해당 소수를 기반으로 투 포인터를 통해 경우의 수를 탐색하면 될 것 같습니다. 즉, 소수들의 연속된 부분합이 특정수를 만족하는 경우를 찾으면 됩니다. 문제 ..
-
[백준] 2957번 : 이진 탐색 트리 - 자바(JAVA)알고리즘/백준 2022. 6. 12. 00:01
https://www.acmicpc.net/problem/2957 2957번: 이진 탐색 트리 이진 탐색 트리는 모든 노드가 많아야 2개의 자식 노드를 가지고 있는 트리이고, 각 노드에는 수가 하나씩 쓰여있다. 만약 어떤 노드에 쓰여 있는 수가 X라면, 그 노드의 왼쪽 서브트리에는 X보다 www.acmicpc.net 문제 해석 1보다 크거나 같고, N보다 작거나 같은 수 N개가 한 번씩 등장하는 수열이 주어집니다. 이때 이진트리를 구성하면 왼쪽 서브트리에는서브 트리에는 X보다 작은 수, 오른쪽 서브 트리에는 X보다 큰 수만 저장되어 있어야 합니다. 첫 번째 수를 루트로 놓고 다 머지 수들을 순서대로 삽입하고자 합니다. 이때 함수안에 C라는 카운터를 1씩 증가시키는 구문이 존재하는데 트리에 삽입된 후에 카..
-
[백준] 23807번 : 두 단계 최단 경로3 - 자바(JAVA)알고리즘/백준 2022. 6. 11. 00:01
https://www.acmicpc.net/problem/23807 23807번: 두 단계 최단 경로 3 첫째 줄에 정점의 수 N(10 ≤ N ≤ 100,000), 간선의 수 M(10 ≤ M ≤ 300,000)이 주어진다. 다음 M개 줄에 간선 정보 u v w가 주어지며 도시 u와 도시 v 사이의 가중치가 정수 w인 양방향 도로를 나타낸 www.acmicpc.net 문제 해석 시작점과 목적지의 최단거리를 구하는 문제이기 때문에 다익스트라가 바로 떠올랐습니다. 하지만 중간에 꼭 거쳐가야 하는 노드들이 주어집니다. 임의의 P개의 정점중에 적어도 3개의 정점은 무조건 거쳐가야 함. 문제 풀이 전 설계 DP를 사용해야 하나..? 전혀 방법이 떠오르지 않았습니다. 따라서 완전 탐색으로 접근해 보려고 합니다. 1번..
-
[백준] 1941번 : 소문난 칠공주 - 자바(JAVA)알고리즘/백준 2022. 6. 6. 00:01
https://www.acmicpc.net/problem/1941 1941번: 소문난 칠공주 총 25명의 여학생들로 이루어진 여학생반은 5×5의 정사각형 격자 형태로 자리가 배치되었고, 얼마 지나지 않아 이다솜과 임도연이라는 두 학생이 두각을 나타내며 다른 학생들을 휘어잡기 시작 www.acmicpc.net 문제 해석 총 25명의 여학생들로 이루어진 여학생반은 5x5의 정사각형 격자 형태로 자리가 배치되었습니다. 이때 학생들이 S, Y 세력으로 갈라지게 되었습니다. 이때 세력 S파는 칠공주를 결성하고자 했습니다. 칠공주는 다음과 같은 규칙을 만족해야 합니다. 1. 7명으로 구성되어야 합니다. 2. 7명의 자리는 서로 가로나 세로로 반드시 인접해 있어야 합니다. 3. 반드시 S세력으로 구성될 필요는 없습니..
-
[백준] 5670번 : 휴대폰 자판 - 자바(Java)알고리즘/백준 2022. 6. 5. 00:01
https://www.acmicpc.net/problem/5670 5670번: 휴대폰 자판 휴대폰에서 길이가 P인 영단어를 입력하려면 버튼을 P번 눌러야 한다. 그러나 시스템프로그래밍 연구실에 근무하는 승혁연구원은 사전을 사용해 이 입력을 더 빨리 할 수 있는 자판 모듈을 개발 www.acmicpc.net 문제 해석 hello, hell, heaven, goodbye라는 단어가 있습니다. 이때 입력을 더 빨리 받기 위해 자동입력을 지원해줍니다. 만약 h를 누르게 된다면 h로 시작하는 모든 단어가 he를 가지기 때문에 자동으로 e를 입력해줍니다. 이후에 a를 누르게되면 hea -> 이후로 단어는 heaven이 유일하므로 heaven이 자동완성됩니다. (2번만에 완성) he 상태에서 l을 누르게 되면 hel..
-
[백준] 7432번 : 디스크 트리 - 자바(JAVA)알고리즘/백준 2022. 6. 4. 00:01
https://www.acmicpc.net/problem/7432 7432번: 디스크 트리 갑자기 맥북이 상근이의 손에서 떨어졌고, 화면이 켜지지 않았다. AS센터에 문의해보니 수리비가 97만원이 나왔고, 상근이는 큰 혼란에 빠졌다. 돈도 중요하지만, 상근이는 그 속에 들어있는 파 www.acmicpc.net 문제 해석 디렉토리의 경로가 주어졌을때, 디렉토리 구조를 보기 좋게 출력하는 프로그램을 작성하세요 공백은 디렉토리 구조상 깊이를 의미하며 서브 디렉토리는 사전순으로 출력해야 합니다. 입력의 값을 토대로 디렉토리 구조를 유추하는 문제입니다. 문제 풀이 전 설계 우선 \ 라는 역슬래시로 디렉토리가 구분됩니다. 계층구조를 가져야 하기 때문에 트리구조? (부모, 자식)을 활용하여 디렉토리 구조를 만들고 같..