본문 바로가기
반응형

분류 전체보기1310

[BOJ] 백준 5052 전화번호 목록 출처: https://www.acmicpc.net/problem/5052 Input 2 3 911 97625999 91125426 5 113 12340 123440 12345 98346 Output NO YES 접두사를 이용해서 전화번호를 누르기 전에 다른 전화로 걸리는지 확인. (일상에서의 [통화 연결] 버튼이 따로 존재하지 않는다고 보면 됩니다.) ▶ Trie 이용 : Trie 자료구조에 번호들을 추가하면서 현재 주어진 번호가 다른 번호의 접두어가 되는지 바로 판단 ※ 숫자로 된 문자열이므로 10진 트리로 이해할 수도 있습니다. #include #include using namespace std; int charToIndex(char c){ return c - '0'; } struct Trie { b.. 2021. 2. 25.
[BOJ] 백준 1753 최단거리 출처: https://www.acmicpc.net/problem/1753 Input 5 6 1 5 1 1 1 2 2 1 3 3 2 3 4 2 4 5 3 4 6 Output 0 2 3 7 INF 음의 가중치가 없기 때문에 다익스트라(Dijkstra) 이용. 다익스트라 (Dijkstra) 개념 다익스트라 알고리즘은 Single Source shortest path problem으로 하나의 정점에서 다른 모든 정점까지 최단 경로를 구할 때 주로 사용됩니다. 이때, 간선의 가중치는 only 양수가 전제조건입니다. ( zoosso.tistory.com ▶ 그래프 구현 (인접 리스트 / 인접 행렬) 그래프 표현 (인접 리스트 / 인접 행렬) 정점 u - v 간 간선 여부 확인 - 인접 리스트는 adList[u]의 .. 2021. 2. 25.
[BOJ] 백준 1719 택배 출처: https://www.acmicpc.net/problem/1719 Input 6 10 1 2 2 1 3 1 2 4 5 2 5 3 2 6 7 3 4 4 3 5 6 3 6 7 4 6 4 5 6 2 Output - 2 3 3 2 2 1 - 1 4 5 5 1 1 - 4 5 6 3 2 3 - 6 6 2 2 3 6 - 6 5 5 3 4 5 - 다익스트라(Dijkstra)을 이용해 최단 경로를 구한 후, 다익스트라 (Dijkstra) 개념 다익스트라 알고리즘은 Single Source shortest path problem으로 하나의 정점에서 다른 모든 정점까지 최단 경로를 구할 때 주로 사용됩니다. 이때, 간선의 가중치는 only 양수가 전제조건입니다. ( zoosso.tistory.com 경로 추적으로 통.. 2021. 2. 25.
[BOJ] 백준 1079 마피아 출처: https://www.acmicpc.net/problem/1079 Input 4 500 500 500 500 1 4 3 -2 -2 1 4 3 3 -2 1 4 4 3 -2 1 1 Output 2 마피아는 1명만 있다고 보면 됩니다. 왜냐하면 "은진이는 마지막 남은 마피아"이기 때문입니다. 그리고 그 마피아가 오래 살아남을 수 있는 경우를 구하는 문제입니다. (정답은 마피아 밤을 가진 횟수) [낮] - 살아남은 player 수 = 홀수 - 유죄지수가 가장 높은 사람을 죽인다, 유지지수가 같으면 플레이어 번호가 낮은 사람을 죽인다. [밤] - 살아남은 player 수 = 짝수 - 마피아가 죽일 사람을 한 명 고른다. 마피아 자기자신과 죽은사람을 제외한 모든 Case를 DFS 탐색 - 죽이고나서는 유죄지.. 2021. 2. 25.
[BOJ] 백준 2160 그림 비교 출처: https://www.acmicpc.net/problem/2160 Input 3 ..X.... .XXX... .XX.... .....X. .X...X. ...X... ..XX... .XX.... .XX..X. .X...X. XX..... X...... XX...XX XXXX.XX XXX..XX Output 1 2 ex) n = 5 일 때, 아래와 같이 비교대상을 두어 완전탐색 ▷ 1 = { 2, 3, 4, 5 } ▷ 2 = { 3, 4, 5 } ▷ 3 = { 4, 5 } ▷ 4 = { 5 } #include #include using namespace std; #define MAX 987654321 char map[5][7][50]; string str; int firstPicture, secon.. 2021. 2. 25.
[BOJ] 백준 3090 차이를 최소로 출처: https://www.acmicpc.net/problem/3090 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. 2. 25.
[BOJ] 백준 2613 숫자 구슬 출처: https://www.acmicpc.net/problem/2613 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. 2. 25.
[BOJ] 백준 6987 월드컵 출처: https://www.acmicpc.net/problem/6987 Input 5 0 0 3 0 2 2 0 3 0 0 5 4 0 1 1 0 4 4 1 0 3 0 2 4 1 0 1 1 3 0 0 5 1 1 3 5 0 0 4 0 1 2 2 1 2 0 3 1 0 4 0 0 5 5 0 0 3 1 1 2 1 2 2 0 3 0 0 5 1 0 4 Output 1 1 0 0 단순히 이긴 횟수, 비긴 횟수, 패배한 횟수만을 비교해서 답을 구할 수 없습니다. C 팀이 다른 누군가와 비겼다는 것은 상대방 전적에도 비긴 횟수가 있어야 하기 때문입니다. 승/패 역시 마찬가지로 누군가가 이겼다면 다른 상대방은 졌다는 것을 의미합니다. ① 6개팀이 승부하는 경우의 수는 15가지입니다. A: {B, C, D, E, F} B: .. 2021. 2. 25.
[BOJ] 백준 2935 소음 출처: https://www.acmicpc.net/problem/2935 Input 1000 * 100 Output 100000 A와 B는 10의 제곱 형태로 길이가 최대 100자리이므로 int와 long 보다는 문자열(string) 활용 10의 제곱 형태이므로 0의 개수에 관해 생각합니다. ▶ A * B의 경우 0의 개수 = {A 문자열 길이 - 1} + {B 문자열 길이 -1} ex) 100 * 10,000 = 1000,000 ← 0의 개수 = (3 - 1) + (5 - 1) = 6 ▶ A + B의 경우 - 문자열의 길이가 같은 경우는 결과가 A 혹은 B의 2배가 됩니다. ex) 1000 + 1000 = 2000 - 문자열의 길이가 다른 경우 먼저, A와 B 중 문자열의 길이가 더 큰 숫자를 A로 둡.. 2021. 2. 25.
[BOJ] 백준 2822 점수 계산 출처: https://www.acmicpc.net/problem/2822 Input 20 30 50 48 33 66 0 64 Output 261 3 4 5 6 8 ▶ vector와 sort() 이용 ① 점수를 기준으로 내림차순 정렬하여 고득점 5개를 구합니다. ② 고득점 5문제를 문제번호 기준으로 내림차순 정렬. ※ vector 원소를 pair로 구현하거나 구조체로 구현 가능. #include #include #include using namespace std; // {점수, 문제 번호} vector problemList(8); int main() { for (int i = 0; i > problemList[i].first; problemList[i].second = i + .. 2021. 2. 25.
반응형

티스토리툴바