프로그래밍/C++
-
코테 일기(12) : 백준 [11047번] 동전 0프로그래밍/C++ 2020. 4. 23. 17:57
전형적인 그리디 알고리즘이다. 그리디 알고리즘(Greedy Algorithm) 이란? 매 선택에서 지금 이 순간 당장 최적인 답을 선택하는 알고리즘이다.Dijkstra와 다르게 현재 노드에서 다음 노드까지만 생각하는 "오늘만 사는 알고리즘" 이라고 할 수 있다. 그래서 그리디 알고리즘 자체의 난이도가 낮을 수 밖에 없다. 무한한 while문 속에서 현재에 해당하면 continue, 해당하지 않으면 break와 같은 극과 극의 알고리즘이다. 코드 #define _CRT_SECURE_NO_WARNINGS #include #include #include using namespace std; int get_coin(vector coin, int value) { int count = 0; int i = coin...
-
코테 일기(11) : 백준 [1780번] 종이의 개수프로그래밍/C++ 2020. 4. 22. 20:28
전형적인 divide and conquer 문제이다. 코드를 짜는데 30분 밖에 걸리지 않았지만, 그 놈의 시간초과 때문에 한참을 애썼다. 코드 #define _CRT_SECURE_NO_WARNINGS #include #include #include using namespace std; int pr[3]; //pr[0] -> -1, pr[1] -> 0, pr[2] -> 1 vector input; //입력 받을 배열 typedef struct { int row; int col; } place; void div_paper(int param, place pl) {//배열과 배열 크기, 위치를 인자로 넣음 if (param == 1) { //크기가 1개면 바로 return 할 수 있게 함. if (input[..
-
코테 일기(10) : 백준 [1051번] 숫자 정사각형프로그래밍/C++ 2020. 4. 21. 23:11
DP(Dynamic Programming)를 풀다가 머리가 아파서 잠깐 brute force로 돌렸다... 역시 어려운 것을 하다가 쉬운 것을 풀면 너무 빨리 풀린다. 총 코딩 시간 10분, 삽질 20분... 정답률 37%는 아무래도 오답을 했던 기록까지 포함해서 인지 상당히 낮다. 하지만 난이도는 초보자도 풀 수 있을 정도라는 것. (전형적인 brute force 문제이다.) 코드 #include #include #include using namespace std; int find_square(vector arr) { int result = 1; for (int i = 0; i < arr.size(); i++) { // 행 위치 for (int j = 0; j < arr[0].size(); j++) {..
-
코테 일기(9) : 백준 [2178번] 미로찾기(BFS)프로그래밍/C++ 2020. 4. 21. 18:06
이번에 풀 문제는 백준 2178번 미로찾기이다. DFS, BFS는 꼭 알고 가야 하는 탐색기법이기에 풀어보기로 했다. 정답률은 35%로 충분히 풀만한 오기가 생겼다. 처음엔 실력도 모자란 내가 풀어도 될까? 라는 마음이 들었지만 언젠간 넘어가야 할 산이다. 처음 든 생각 DFS로 stack을 사용해서 푸는것이 더 편해 보였다. 하지만 문제에서는 BFS를 요구했으니 넓이 탐색으로 풀기로 했다. 연속된 1을 통해 array의 마지막에 도달하는 것이 우리 최종 목표이다. 먼저 queue의 size가 0 이 아닌 한 반복을 해야 할 것이고 while (queue.size() > 0) queue의 front를 받아와서 한 단계 씩 나아가야한다. (queue.front()) 이후 상하좌우를 모두 검색하여 1이 존재..
-
코테 일기(8) : 하노이탑(The tower of Hanoi)프로그래밍/C++ 2020. 4. 20. 14:02
하노이탑은 Divide and Conquer(정복 분할 기법)에서 가장 많이 다뤄지는 문제 중 하나다. A에서 B를 거쳐 C로 옮기기 위해 하노이 탑의 순서는 다음과 같다. 1. (1,2)를 B로 옮긴다. 2. (3)을 C로 옮긴다. 3. (1,2)를 C로 옮긴다. 이를 코드로 그대로 옮기면 다음과 같다. Code //하노이탑 만들기 #include using namespace std; int hanoi(int a, int b, int c, int d); int main() { int N; cout
-
코테 일기(7) : 백준 [1260번] DFS와 BFS(DFS & BFS 완성)프로그래밍/C++ 2020. 4. 20. 00:37
오랜만에 C++을 잡으려 하니 벌써부터 심장이 아프다.. 내가 짠 BFS 코드를 보면서 DFS를 짜기에는 코딩실력이 아닌 Copy and Paste의 느낌이 강할 것 같아 과감하게 BFS를 보지 않고 풀어보았다. 처음 든 생각 먼저 DFS는 stack 구조가 매우 편해보였다. Depth로 탐색을 하기에 Terminal Node(최하위노드)를 제거하는 것 이 아니고, 탐색을 할 노드가 없으면 Tree를 거슬러 올라가야 한다는 점에서 Stack을 사용했다. 또한 백준에서는 함수마다 입력을 받는 것이 아니라, 주어진 입력을 통해 두 개의 함수를 모두 사용하는 것이기에 처음 필요한 입출력을 main에 넣었다. 코드(DFS만) void dfs(int n, int m, int v, vector arr) { int*..
-
코테 일기(6) : 백준 [1260번] DFS와 BFS(BFS편)프로그래밍/C++ 2020. 4. 5. 16:29
CodeUp으로 몸? 뇌?를 풀어줬으니, 이제 알고리즘의 꽃인 백준 온라인 저지로 입성하자. 처음 접한 문제는 DFS, BFS를 다루는 문제였다. 그래프 탐색 알고리즘은 알고리즘 필수 요소 중 하나이기 때문에 절대적으로 짚고 넘어가야 한다. BFS는 Breath-First Search 이다. 즉 depth를 한 단계씩 내려가면서 너비를 위주로 탐색하는 너비우선탐색이다. 예제 입력 2번과 같은 경우 3번에서 1, 4번을 먼저 방문 한 후에1번에서 2번, 4번에서 5번을 방문하는 결과가 나온다.즉 3 (1 4) (2 5) 와 같은 결과가 나와야 한다. 처음 든 생각 정점(Node)의 개수가 N이고 간선의 개수가 M이면 탐색은 M번이 이루어 져야 한다. { for(int i = 0; i> srt >> dst;..