BOJ 백준 검색 결과

해당 글 54건

백준 02623 - 음악프로그램

출처 : https://www.acmicpc.net/problem/2623 2623번: 음악프로그램 첫째 줄에는 가수의 수 N과 보조 PD의 수 M이 주어진다. 가수는 번호 1, 2,…,N 으로 표시한다. 둘째 줄부터 각 보조 PD가 정한 순서들이 한 줄에 하나씩 나온다. 각 줄의 맨 앞에는 보조 PD가 담당한 www.acmicpc.net 고려 사항 위상 정렬 알고리즘! 주어진 정보를 활용하여, vector[가수 번호] = { 연결된 노드 리스트 ( 연결 당한 노드들 ) }, array[가수 번호] = 연결 당한 횟수. 연결 당한 횟수가 0 인 가수 번호를 큐에 삽입. 큐가 비지 않으면 반복해서, 1. 정답 벡터에 제일 먼저 들어온 가수를 담고 pop 한다. 2. 그 가수가 연결한 가수 번호들의 cnt ..
BOJ 백준/그래프, 경로 2021. 4. 6. 21:13

백준 01647 - 도시 분할 계획

출처 : https://www.acmicpc.net/problem/1647 1647번: 도시 분할 계획 첫째 줄에 집의 개수N, 길의 개수M이 주어진다. N은 2이상 100,000이하인 정수이고, M은 1이상 1,000,000이하인 정수이다. 그 다음 줄부터 M줄에 걸쳐 길의 정보가 A B C 세 개의 정수로 주어지는데 A번 집 www.acmicpc.net 고려사항 최소 신장 트리 문제! 도시를 두 개로 분할했을 때의 최소 도로 비용은 최소 신장 트리로 모든 도시를 연결했을 때, 가장 비싼 비용의 도로를 제거해주면 2개로 나뉜다! 프림 방식으로 풀었다. 프림 방식은 1. 노드(vertex)를 선택 하고, 그 노드에 연결된 edge들을 minHeap 에 담아준다. 2. 힙에서 e를 꺼내고, 해당 e를 통해..
BOJ 백준/그래프, 경로 2021. 4. 6. 20:11

백준 12852 - 1로 만들기 2

출처 : https://www.acmicpc.net/problem/12852 12852번: 1로 만들기 2 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 자연수 N이 주어진다. www.acmicpc.net 고려사항 동적 프로그래밍을 활용하면, 가작 작은 연산 수는 쉽게 구할 수 있다. 그 경로를 추적하는 것은 생각보다 어려웠다... 근데 그냥 똑같은 길이의 배열하나 더 만들어서 더 최소값이 나와서, v의 값이 갱신 될 때, 해당 값이 어떤 수에서 왔는지 path배열에 기록해주고 1을 만날 때 까지 쫙 뽑아주면 되는 것이 었다.. #include #include using namespace std; int memo[1000001]; int path[1000001]; int dp(int num){ ..
BOJ 백준/Dynamic Programming 2021. 1. 4. 22:56

백준 09252 - LCS 2

출처 : https://www.acmicpc.net/problem/9252 9252번: LCS 2 LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 고려사항 동적 프로그래밍 LCS 알고리즘을 응용하여 제일 긴 부분 문자열의 요소들을 뽑아내는 문제. lcs 를 재귀로 풀 수도 있고( 09251 - LCS ), 이 문제처럼 bottom -> top 으로 반복문으로도 풀 수 있다. 재귀는 top -> down 이다! 현재 조사중인 str1 의 인덱스 y 와 str2의 인덱스 x 들의 문자가 ..
BOJ 백준/Dynamic Programming 2020. 12. 30. 20:00

백준 02178 - 미로 탐색

출처 : https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 고려사항 BFS 를 활용 - BFS를 활용하면 레벨 (몇 번 움직였는지)가 작은 순서대로 탐색하기 때문에 먼저 (N, M) 에 도달하면 더이상 탐색 없이 return 해줄 수 있다. DFS를 사용하면 현재 움직인 cnt 값을 인자로 넘겨주며 값을 구할 수 있지만 N, M 에 도달해도 다른 가지까지 탐색을 진행해야 최소값인지를 알 수 있다. ( 가지치기를 이용하면, 연산을 줄일 수 있긴 하지만.. ) #include #i..
BOJ 백준/DFS + BFS 2020. 12. 20. 02:43

백준 11653 - 소인수분해

출처 : https://www.acmicpc.net/problem/11653 11653번: 소인수분해 첫째 줄에 정수 N (1 ≤ N ≤ 10,000,000)이 주어진다. www.acmicpc.net 고려사항 나누는 수를 2부터 시작해서 나눈 결과가 0이면 출력한다. 나머지가 0이 아니면 d를 1씩 증가하며 반복하고, num 이 1일 때 완료한다. 작은 소수부터 나눗셈을 하게 되는 방식이라, 증가된 d가 4와 같이 소수가 아닐 시에는 이미 4의 약수인 2로 나눗셈을 진행했었기 때문에 나눠지는 일이 없기 때문에 다시 d를 증가시키게 된다. #include using namespace std; int main() { int num, d = 2; cin>>num; while(num != 1){ if(num %..
BOJ 백준/기타 2020. 12. 19. 23:48

백준 02609 - 최대공약수와 최소공배수

출처 : https://www.acmicpc.net/problem/2609 2609번: 최대공약수와 최소공배수 첫째 줄에는 입력으로 주어진 두 수의 최대공약수를, 둘째 줄에는 입력으로 주어진 두 수의 최소 공배수를 출력한다. www.acmicpc.net 고려사항 유클리드호제법으로 최대공약수 구하기 최소공배수 = a * b / gcd(a, b) #include using namespace std; int main() { int a, b, tmp, gcd, lcm; cin>>a>>b; lcm = a * b; if(a 0){ tmp = b; b = a % b; a = tmp; } gcd = a; lcm /= gcd; cout
BOJ 백준/기타 2020. 12. 18. 23:57

백준 02252 - 줄 세우기

출처 : https://www.acmicpc.net/problem/2252 2252번: 줄 세우기 첫째 줄에 N(1≤N≤32,000), M(1≤M≤100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의미이 www.acmicpc.net 고려사항 위상정렬 알고리즘 사용. 위상정렬 설명이나 질문 페이지에 가면, 자신에게 들어오는 간선의 수가 0인 정점이 더이상 없지만, 아직 방문 안한 정덤들이 있어 더 이상 위상정렬을 진행할 수 없을 때, 이를 순환상태로 보고 이를 찾기 위해 그래프를 dfs로 탐색하는 방식이 있는데, 굳이 왜그래야 하나 싶어서 내 생각대로 풀어보았다. edgeIn 벡터에 자..
BOJ 백준/기타 2020. 11. 27. 03:19