본문 바로가기
반응형

PS 문제 풀이/Baekjoon446

[BOJ] 백준 14867 물통 출처: www.acmicpc.net/problem/14867 Approach BFS (Breadth-First Search, 너비 우선 탐색) 이용 BFS (Breadth-First Search, 너비 우선 탐색) BFS 그래프 전체를 탐색하되, 인접한 노드들을 차례대로 방문합니다. Queue 이용 * DFS로 풀리는 문제는 일반적으로 BFS로도 풀 수 있습니다. Process ※ 깊이 우선 탐색과는 달리 너비 우선 탐색에서 zoosso.tistory.com DFS와 BFS 비교 DFS와 BFS 비교 출처: 나무위키 경로 비교 BFS - Queue 이용 - 최소신장트리(Minimum Spanning Trees), 최단경로(Shortest Paths) 장점: 무한히 깊거나 무한에 가까운 트리인 경우에 효과.. 2021. 3. 30.
[BOJ] 백준 17616 등수 찾기 출처: www.acmicpc.net/problem/17616 Approach [Jungol] 2462 키 순서 문제와 유사하다. [Jungol] 정올 2462 키 순서 출처: jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=1723&sca=40 Approach 문제 접근법 및 인접행렬로 구현된 코드는 [BOJ] 2458 키 순서 참고 [BOJ] 백준 2458 키 순서 출처: https://www.acmicpc.net/prob.. zoosso.tistory.com 전체 학생 수 N ≤ 100,000이며, 질문 횟수 M ≤ 500,000이기 때문에 인접행렬로는 학생들의 등수 관계를 표현할 수 없다. → 인접리스트로 구현 X 번 학생의 등수 범위를 알기 위해서는 자기 위와.. 2021. 3. 13.
[BOJ] 백준 1654 랜선 자르기 출처: https://www.acmicpc.net/problem/1654 Approach Binary Search (이분 탐색) Binary Search (이분 탐색) Binary Search (이분 탐색) 정렬된 자료에서 목표값을 찾고자 할 때, 사용되는 탐색기법 O(logN) 리스트 중간의 값(mid)을 선택하여 찾고자 하는 값과 비교하는 방식 분할 정복 알고리즘(Divide and Conquer Al zoosso.tistory.com [탐색] Parametric Search [탐색] Parametric Search Parametric Search 최적화 문제를 결정 문제로 바꿔 푸는 것 O(logN) ex) Binary Search (이분 탐색)을 이용해서 Lower/Upper Bound를 구하는 .. 2021. 3. 6.
[BOJ] 백준 11727 2×n 타일링 2 출처: https://www.acmicpc.net/problem/11727 Input 12 Output 2731 2 * N 직사각형이 주어질 때, 2×1과 2×2 타일로 채우는 방법의 수 첫번째 줄에 N을 입력 받습니다. ▶ 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력 Dynamic Programming (DP) 이용. - 자세한 풀이는 [BOJ] 1793 타일링 참고 [BOJ] 백준 1793 타일링 출처: https://www.acmicpc.net/problem/1793 Input 2 8 12 100 200 Output 3 171 2731 845100400152152934331135470251 107129202950599351702797472822744173501480.. 2021. 3. 1.
[BOJ] 백준 11723 집합 출처: https://www.acmicpc.net/problem/11723 Approach ※ 비트마스크 (Bitmask) 비트마스크 (Bitmask) 비트마스크 정수의 이진수 표현(Bit)을 자료 구조로 쓰는 기법 현대의 모든 CPU는 이진수를 이용해도 모든 자fy 표현 내부적으로 이진수를 사용하는 컴퓨터들은 이진법 관련 연산들을 아주 빨리 zoosso.tistory.com 집합 S에서 사용되는 숫자가 1 ≤ X ≤ 20이므로, 비트를 이용해서 표현 ex) S = 일 때, state = 10101000000000000001 ex) S = 일 때, state = 11110000000000000000 명령어의 개수가 M (1 ≤ M ≤ 3,000,000)이므로 빠른 입출력 처리를 위해서 아래 구문들 이용... 2021. 2. 28.
[BOJ] 백준 11811 데스스타 출처: https://www.acmicpc.net/problem/11811 Approach ※ 비트마스크 (Bitmask) 비트마스크 (Bitmask) 비트마스크 정수의 이진수 표현(Bit)을 자료 구조로 쓰는 기법 현대의 모든 CPU는 이진수를 이용해도 모든 자fy 표현 내부적으로 이진수를 사용하는 컴퓨터들은 이진법 관련 연산들을 아주 빨리 zoosso.tistory.com Input Data에서 마지막 행은 다음과 같다. m4i = ▶ m40 = 1 = a4 & a0 11 & 1 → 1011 & 0001 = 0001 ▶ m41 = 2 = a4 & a1 11 & 2 → 1011 & 0010 = 0010 ▶ m42 = 3 = a4 & a2 11 & 3 → 1011 & 0011 = 0011 ▶ m43 = .. 2021. 2. 28.
[BOJ] 백준 1062 가르침 출처: https://www.acmicpc.net/problem/1062 Input 3 6 antarctica antahellotica antacartica Output 2 N개의 단어는 모두 아래의 구조를 가지고 있습니다. [anta]...[tica] 따라서 a, n, t, i, c 알파벳을 알지못하면 모든 단어를 알 수 없습니다. 그렇기에 K < 5이며 알 수 있는 단어의 개수는 0개 입니다. K ≥ 5일때는 a, n, t, i, c 알파벳은 알고있어야 됩니다. 따라서 나머지 알파벳 인지 여부를 통해 알 수 있는 단어의 개수를 파악해야 합니다. 따라서 알파벳을 선택하는 경우의 수는 26-5CK-5 #include #include #include #include using namespace std; i.. 2021. 2. 28.
[BOJ] 백준 12813 이진수 연산 출처: https://www.acmicpc.net/problem/12813 Input 0001011000 0000101111 Output 0000001000 0001111111 0001110111 1110100111 1111010000 ※ 비트마스크 (Bitmask) 비트마스크 (Bitmask) 비트마스크 정수의 이진수 표현(Bit)을 자료 구조로 쓰는 기법 현대의 모든 CPU는 이진수를 이용해도 모든 자fy 표현 내부적으로 이진수를 사용하는 컴퓨터들은 이진법 관련 연산들을 아주 빨리 zoosso.tistory.com #include #include #include using namespace std; int main() { int A[100001], B[100001]; string strA, strB;.. 2021. 2. 28.
[BOJ] 백준 1436 영화감독 숌 출처: https://www.acmicpc.net/problem/1436 Input 2 Output 1666 종말의 숫자는 다음과 같습니다. ▶ 666 → 1666 → 2666 → 3666 → 4666 → 5666 → 6660 → 6661 → ... N은 10,000보다 작거나 같은 자연수이므로 숫자를 증가시켜가며 "666"을 포함여부를 확인하여 N번째 종말의 숫자를 출력합니다. #include using namespace std; int N; void solve() { int result = 666; int i, cnt = 0; while(1){ for(i=result; i; i /= 10){ if(i % 1000 == 666){ cnt++; break; } } if(cnt == N){ cout N; .. 2021. 2. 28.
[BOJ] 백준 2798 블랙잭 출처: https://www.acmicpc.net/problem/2798 Input 5 21 5 6 7 8 9 Output 21 ▶ 6 + 7 + 8 = 21 N이 크지 않은 숫자이므로 NC3으로 모든 경우의 수에 대한 최적의 해를 구합니다. #include #include #include using namespace std; int N, M; int result; vector v; // 조합 void DFS(int idx, int cnt, int sum){ // 3장의 카드 선택되어, 합이 M이하인 경우 if (cnt == 3 && sum = N || cnt > 3 || sum > M) return; // 해당 카드 선택한 경우 DFS(idx + 1, cnt + 1, sum + v[idx]); // 해.. 2021. 2. 28.
반응형

티스토리툴바