본문 바로가기
반응형

PS 문제 풀이/Baekjoon446

[BOJ] 백준 13015 별 찍기 - 23 출처: https://www.acmicpc.net/problem/13015 Input 2 Output ** ** *** ** ** 별도 메모리를 잡지 않고 2n - 1 줄에 거쳐 출력. 3가지 영역으로 구분합니다. 첫번째 / 중간 / 마지막 (첫번째와 마지막은 동일한 출력) ① 초기 a, b, c, d의 값은 아래와 같습니다. ▶ a = 0 , b = n - 1 ▶ c = 3n - 3, d = 4n - 4 n번째 줄까지는 a와 b는 증가 / c와 d는 감소 n번째 줄 이후로는 a와 b는 감소 / c와 d는 증가 ② 별을 찍는 형태는 아래와 같습니다. [첫번째와 마지막 줄] ▶ a 별 b 공백 c 별 d [중간] ▶ 공백 a 공백 b 공백 c 공백 d * n번째 줄에 해당하는 정가운데에서는 b와 c가 같은.. 2021. 2. 26.
[BOJ] 백준 1916 최소비용 구하기 출처: https://www.acmicpc.net/problem/1916 Input 5 8 1 2 2 1 3 3 1 4 1 1 5 10 2 4 2 3 4 1 3 5 1 4 5 3 1 5 Output 4 출발점 X부터 다른 정점 Y까지의 최소거리 비용을 구하기 위해 다익스트라(Dijkstra)을 이용 다익스트라 (Dijkstra) 개념 다익스트라 알고리즘은 Single Source shortest path problem으로 하나의 정점에서 다른 모든 정점까지 최단 경로를 구할 때 주로 사용됩니다. 이때, 간선의 가중치는 only 양수가 전제조건입니다. ( zoosso.tistory.com 정점과 간선의 개수가 비교적 크지 않으므로 선형적으로 구현 * 문제에서 Input Data 중 아래와 같이 서로 다른 .. 2021. 2. 25.
[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.
반응형

티스토리툴바