C++47

• 

  [c++] 백준 - 합이 0인 네 정수 ( 이분탐색) 1. 문제 2. 입출력 및 예제 3. 문제 해설 처음에 이 문제를 접했을 때 비슷한 문제가 생각났다. 백준-피자판매 문제와 백준-두배열의 합 문제였다. 따라서 처음엔 두 문제와 같이 map을 사용해서 풀면 쉽게 풀릴 줄 알았다. 위의 두 문제의 경우 가능한 모든 합의 경우의 수를 미리 구해두어 map에 그 합과 그 합이 나오는 경우의 수를 모두 저장해둔다. 그 후 다른 배열을 돌면서 합이 K가 되는 경우를 구해야한다면 cnt += map[K - 다른배열[i]]와 같은 로직으로 경우의 수를 모두 구해 더해주면 되었다. unordered_map의 경우 정렬을 하지 않는 map이고 hash table을 기반으로 하는 자료구조이기 때문에 O(1)의 시간복잡도로 원하는 자료에 접근이 가능했다. 하지만 위의 접근 .. c++/알고리즘 2023. 2. 6.

• 

  [c++] 백준- 보석도둑 (Greedy) 1. 문제 2. 입출력 및 예제 3. 문제 해설 이 문제를 처음 봤을 때 완전탐색으로는 아주 쉬운 알고리즘으로 풀 수 있겠다는 생각을 했다. 담을 수 있는 무게가 다른 가방이 여러개 있고 보석의 무게와 가치가 여러개 존재한다면 당연히 보석을 최대한의 가치로 가져가는 방법은 담을 수 있는 무게가 가장 작은 가방부터 최대로 채워가는 것이다. 다시 말하면 가장 담을 수 있는 무게가 작은 가방부터 담을 수 있는 보석 중 가장 높은 가치를 가지고 있는 보석을 차례대로 담아가면 되는 것이다. 이것을 완전탐색으로 풀면 for문을 두 번 돌면서 그냥 이 보석이 이 가방에 담을 수 있는 것인지 아닌지를 판별한다음 담을 수 있다면 담을 수 있는 것 중 가장 가치가 큰 것을 선택해 답에 포함시켜주고 선택된 것을 제외시켜주면.. c++/알고리즘 2023. 2. 5.

• 

  [c++] 백준 - lca (그래프 이론) 1. 문제 2. 입 출력 3. 예제 입출력 4. 문제 해설 처음 이 문제를 마주했을 때 나는 대강 풀이법을 들어서 알고 있었다. 따라서 조금 빨리 구현할 수 있었던 거 같다. 그런데 한 가지 고민했던 점은 부모노드와 자식노드를 어떻게 판별하는 것일까였다. 처음에는 입력의 순서가 부모-자식 순인가 했었지만 다시 생각해보니 부모-자식 순으로 입력이 들어오는 것은 아닌 거 같았다. 처음에 들어오는 입력이 더 클 수도 나중에 들어오는 입력이 더 큰 경우도 존재했기 때문이다. 그래서 그 다음 생각했던 것은 입력의 순서대로 트리가 구성되는 것인가?를 고민해보았다. 그러면 입력이 어떻게 들어오든 앞선 입력에 존재하는 노드가 부모가 되겠거니 했다. 그래서 양방향으로 벡터에 푸쉬해주었다. 1. 입력 (양방향으로 연결성을.. c++/알고리즘 2023. 2. 3.

• 

  [c++] 백준 - 달리기 (인덱스드 트리) 1. 문제 2. 입출력 3. 예제 입출력 4. 문제 해설 처음에 이 문제를 읽었을 때는 왜 플래티넘 4인가 했다. 단순히 자신보다 앞에 있는 수 중 자신보다 큰 수의 숫자를 구하면 되는 것이 아닌가?라는 생각이 들었다. 그런데 문제 조건을 확인하니 선수의 수 N은 최대가 500000이고 만약 위의 방법을 적용하면 대략 O(N^2)의 시간복잡도를 갖게 된다. 500000 * 5000000 = 25000000000000 = 20조의 연산 횟수가 늘어나고 만약 break문을 통해 중간중간 가지치기를 해준다해도 시간 제한이 1초라는 것은 대략 1억번의 연산안에 결과가 나와야하는 것인데 O(N^2)알고리즘으로는 불가능하다는 생각이 들었다. 가능한 시간 복잡도는 O(NlogN)정도였다. 결국 알고리즘 분류를 봐버렸.. c++/알고리즘 2023. 2. 3.

• 

  [c++] 백준 사탕상자 - 인덱스드 트리 1. 문제 2. 입 출력 예제 입 출력 4. 문제 해설 문제의 조건을 살펴보자 사탕 상자에 수정이가 손을 댄 횟수는 n(1 = OFFSET){ //offset은 원본 배열의 시작 점 update(i-OFFSET +1, -1); // 하나씩 빼준다. return i - OFFSET + 1; // 사탕의 맛은 1부터 시작이나 원본배열은 OFFSET(짝수)부터 시작하므로 } if(Tree[i * 2] >= rank) { return query(rank, i*2); // 만약 왼쪽 자식 노드의 값이 구하고자 하는 값보다 크거나 같다면 }else { return query(rank - Tree[i*2] , i*2+1); // 왼쪽 자식 노드의 값이 구하고자 하는 값보다 부족하다면 오른쪽 자식 노드로 이동 } } .. c++/알고리즘 2023. 2. 2.

• 

  [c++] 인덱스드 트리에 관하여 1. 인덱스드 트리란? 인덱스드 트리란 어떤 수열이 존재할 때 각 구간의 대표값들로 이루어진 트리를 의미한다. 주로 부분합, 부분 곱, 부분 차 등 구간 별 값을 구해야하는 상황에서 많이 사용된다. 또한 수열의 값이 자주 변경되는 상황에서도 많이 사용된다. 누적 합 배열과 같이 처음부터 순서대로 누적되는 합의 배열을 구하는 방식의 경우 중간에 하나의 값이 변경되면 그 값의 인덱스부터 수열의 끝까지 다시 누적합을 구해야하는 치명적인 단점이 있다. 만약 제일 처음 원소가 변경되었다면 모든 누적합 배열을 처음부터 다시 계산해야한다.O(N)이 걸린다. 기본적으로 트리라는 자료구조는 O(logN)의 시간복잡도를 위한 자료구조이다. 시간복잡도를 얻는 대신 공간복잡도를 살짝 trade-off하긴 하지만 요즘 메모리는.. c++/알고리즘 2023. 2. 1.

• 

  [c++] 백준-퇴사2 (dynamic programming) 1. 문제 2. 입출력 3. 문제 해설 이 문제는 그냥 퇴사와 퇴사2가 존재한다. 두 문제는 완전 같은데 다른 점이 하나 있다. 바로 N의 범위가 1000에서 1500000으로 늘어났다는 점이다. 이는 완전탐색으로 O(N^2) 시간 복잡도가 가능했었는데 N이 증가함에 따라 완전탐색 알고리즘은 사용하지 못한다는 뜻이다. N의 범위가 1500000으로 늘어났으니 가능한 알고리즘 시간 복잡도는 O(N) or O(NlogN)정도가 되겠다. 그러면 가자 대표적인 것이 dp-> dynamic programming을 이용해보기로 했다. 위와 같이 dp를 사용해보기로 한 것은 이전 값의 입력들이 그 다음 입력에 영향을 미치는 관계가 있다고 생각이 들었기 때문이다. 1일차의 상담을 선택하거나 선택하지 않을 수 있는데 이.. c++/알고리즘 2023. 2. 1.

• 

  [c++] 백준 - 단어수학 1. 문제 2. 입출력 3. 문제 해설 처음엔 완전 해맸다. 처음엔 단어의 개수가 N(1> N; for (int i = 0; i > temp; int idx = 1; for (int i = temp.size()-1; i >= 0; i--) { alphabet[temp[i] - 'A'].val += idx; alphabet[temp[i] - 'A'].idx = temp[i] - 'A'+1; idx *= 10; } } } void sol() { sort(alphabet, alphabet + 26, cmp); int num = 9; for (int i = 0; i < 26; i++) { if (alphabet[i].idx == 0) break; ans +=.. c++/알고리즘 2023. 1. 31.

• 

  [C++] 백준 - 전구 문제 2. 입출력 3. 문제 해설 문제를 읽어보면 최대 K가지의 서로 다른 색을 표현할 수 있는 전구들이 존재하고 이 전구 N개를 한 줄로 배치한다. 한 줄로 배치한다는 것은 고리 형태가 아닌 자신의 양 옆의 전구만이 자신에게 영향을 줄 수 있다는 뜻이다. 또한 임의의 전구를 하나 잡아 색을 바꾼다. 그런데 이 임의의 전구와 인접한 전구가 같은 색이라면 이 전구 또한 색상이 변한다. 그러면 이 문제는 최소 문제로 쪼갤 수 있다. 바로 옆의 전구가 변했을 때 색이 같다면 변하고 색이 다르다면 변하지 않는 것이다. 그러면 이 문제는 dp를 적용해 memoization 해 가면서 풀 수 있을 거 같다고 생각했다. 이 문제에서 제일 까다로운 점은 임의의 전구부터 시작할 수 있다는 점이다. 또한 dp를 이용하려면.. c++/알고리즘 2023. 1. 30.

• 

  [C++] 백준 - 두 배열의 합 1. 문제 2. 입 출력 3. 문제 해설 처음엔 투포인터로 풀려고 노력했다. 양수만 있었다면 투포인터로 충분히 풀 수 있었을텐데 음수가 섞이는 바람에 포인터의 이동 로직이 복잡해져서 다른 방법을 생각해보았다. N의 제한은 1000 생각보다 크지 않았다. 더 많은 작업을 brute Force하게 수행해도 될 거 같다는 생각이 들었다. 따라서 모든 부분합의 경우의 수를 구해보기로 했다. map amap; for(int i=1; i c++/알고리즘 2023. 1. 30.

• 

  [c++] 위상정렬 백준-게임개발 1. 문제 2. 입 출력 1. 생각해볼 것 처음엔 위상정렬을 한 후 누적합을 구하는 문제인 줄 알았다.. 하지만 하나 놓치고 있었던 것이 있었다. 건물이 동시 다발적으로 건설 될 수 있었다는 것이다. 즉, 4 1 4 3 2 -1 2 4 -1 1 4 -1 1 -1 위와 같은 입력이 있을 때 누적합으로 구한다면 1번 건물은 4 3 2가 선행되어야 하므로 dist[4]+dist[3]+dist[2]+dist[1] = 5가 되어야한다. 2번 건물은 4가 선행되어야 하므로 dist[2] + dist[4] = 3 3번 건물은 4가 선행되어야하므로 dist[3] + dist[4] = 2 4번 건물은 선행되어야하는 건물이 없으므로 그대로 dist[1] = 1이 된다. 그러나 답은 4 3 2 1이 된다. 왜일까? 위의 그.. c++/알고리즘 2023. 1. 27.

• 

  [c++]벨만포드 알고리즘 - 백준 타임머신 11657 벨만포드 알고리즘이란? 벨만포드 알고리즘이란 음의 가중치가 존재할 때 최단 경로를 구하는 알고리즘이다. 양의 가중치만이 존재할 때 다익스트라 알고리즘을 이용해 최단 경로를 구한 것과는 다르게 벨만포드에는 음의 가중치가 존재한다. 다익스트라 알고리즘은 현재 선택한 것이 최선의 선택이라는 greedy알고리즘을 기반으로 한다. 하지만 음의 가중치가 존재한다면 음의 가중치를 여러번 지날 수록 최단 경로는 오히려 줄어들게 되는 경우가 존재한다. 따라서 greedy 알고리즘에 위배된다. 특징 음의 가중치를 가지는 간선도 가능하다. 음의 사이클의 존재 여부를 확인할 수 있다. 최단 거리를 구하기 위해서 v-1번 E개의 모든 간선을 확인한다.(다익스트라가 노드 중심의 알고리즘이라면 벨만포드는 간선 중심이다.) 총 연산.. c++/알고리즘 2023. 1. 26.