c++/알고리즘54

• 

  [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.

• 

  [c++] 다익스트라 알고리즘 (백준-최단경로 1753) 다익스트라 알고리즘이란? 다익스트라 알고리즘이란 한 지점에서 그래프 상의 나머지 모든 지점으로의 최단 경로를 구할 수 있는 알고리즘이다. 다익스트라 알고리즘은 그래프 상의 어느 한 간선의 가중치라도 음수가 존재하면 안된다. 이는 다익스트라 알고리즘이 현재 선택하는 것이 최선의 방법이라는 greedy를 기반으로 한 알고리즘이기 때문이다. 만약 음수의 가중치가 있다면 이 경로를 계속 지나갈수록 더욱 최선의 값을 가지게 되므로 다익스트라 알고리즘에 위배된다. (음수의 가중치를 가질 수 있을 때는 벨만 포드 알고리즘을 이용해야한다.) 다익스트라 알고리즘을 구현하기 위해서는 2가지의 과정을 반복해주면 된다. /* 1. 방문하지 않은 정점 중 가장 가중치 값이 작은 정점을 방문한다. -> 이를 위해 처음 배열을 무.. c++/알고리즘 2023. 1. 25.

• 

  [c++] 알고리즘 그래프 - 위상 정렬 - 백준 - 줄 세우기 2252 위상 정렬이란? 위상 정렬이란 어떤 집합에서 원소들의 우선 순위 정렬이라고 할 수 있겠다. 또한 위상정렬은 비순환 방향 그래프 즉 (DAG : Directed Acyclic Graph)에서 가능하다. 즉 그래프를 이루는 노드들 간의 순환이 존재하지 않게 방향이 존재할 때 가능한 정렬이다. DAG 위와 같은 DAG그래프를 선형적 그래프로 변경하는 것을 위상정렬이라고 한다. 위상정렬은 말 그대로 위상을 정렬한다는 뜻으로 이 정렬에는 각 노드들의 우선 순위가 중요하다. 또한 우선 순위만을 고려하기 때문에 최종 결과 값이 여러 개가 될 수 있다. 즉 위의 비선형 그래프는 다음과 같은 뜻을 내포한다. 1보다는 0이 선행되어야한다. 1보다는 4가 선행되어야한다. 2보다는 1이 선행되어야한다. 2보다는 4가 선행되어.. c++/알고리즘 2023. 1. 25.

• 

  [c++] 백준-제단 5626 문제 입력과 출력 사실 이 문제를 풀 때 DP를 이용해서 푸는 문제라는 것을 알고 있었기 때문에 쉽게 접근할 수 있었다. (물론 난이도 자체는 어렵다 매우) DP는 점화식을 세우면 끝나는 문제다. 문제를 파악해보면 다음과 같다. 문제 해설 우선 제단을 세울 수 있는 경우를 생각해보았다. x 가능 가능 x x 가능 가능 가능 가능 x 점화식은 대부분 memoization된 이전 상태에서 현재의 값을 찾아낼 수 있기에 두 가지의 경우만을 고려해보았다. 2층의 가능한 경우는 1층의 경우에 따라 가능할 수도 불가능할 수도 있다. 따라서 이는 현재 상태가 이전 관계에 영향을 받는 점화식으로 풀 수 있는 DP문제이다. 그렇다면 현재 상태는 이전 상태의 어떠한 영향을 받을까? 다음 세 가지 경우가 있을 수 있다. 현.. c++/알고리즘 2023. 1. 25.

• 

  [c++] Floyd의 알고리즘 - 가중치가 다른 길찾기 문제는 다음과 같다. 가중치가 같은 최단 경로의 알고리즘으로는 BFS를 사용할 수 있지만 이 같은 경우에서는 경로마다 가중치가 다르기 때문에 BFS로 접근하면 안된다. 대신 DP 다이나믹 프로그래밍을 사용하여 부분 최적해를 구해가며 진행할 수 있겠다. 1. map만들기 우선 배열에 map을 만들어주어야 한다. 이 때 중요한 것은 갈 수 없는 방향에 대해서는 infinite한 값- 매우 큰 값으로 이루어져야 한다는 것이다. 따라서 위의 그래프를 이용해 map을 만들면 다음과 같다. int w[6][6] = { {0,0,0,0,0,0}, {0,0,1,1000,1,5}, {0,9,0,3,2,1000}, {0,1000,1000,0,4,1000}, {0,1000,1000,2,0,3}, {0,3,1000,1000,.. c++/알고리즘 2022. 5. 25.