알고리즘25

• 

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

• 

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

• 

  [c++ 프로그래머스] 문자열 압축 문제 프로그래머스 KAKAO 2020 Blind문제이다. 여기에서 나는 c++을 이용하여 작성했으며 for문을 두 번 돌며 문제를 해결하여 O(n^2)으로 해결하였다. 핵심은 substr함수를 얼마나 잘 사용하느냐와 인덱스의 이동을 얼마나 수학적으로 잘 표현할 수 있는가 였다. 처음에 테스트 케이스를 돌릴 때 계속 3개가 틀려서 왜일까 고민했는데 처음에 중복되는 문자의 개수가 1자리 수일 때만을 고려해서 실패한 사례가 존재하는 것이었다. int solution(string s) { int m = s.size() / 2; string temp; string copy = s; int si = 1; int minlength = copy.length(); for (int i = 1; i c++/알고리즘 2022. 5. 8.

• 

  [C++]완전탐색 1. 완전탐색이란? 제목에서도 알 수 있듯이 가능한 모든 경우의 수를 탐색하는 것을 의미한다. 알고리즘 문제에서는 크게 6가지 유형 정도가 있다. 1)Brute Force 진짜 말 그대로 가능한 모든 방법을 단순히 찾는 방법이다. 흔히 패턴매칭 같은 곳에서 사용되는데 예를 들어 txt파일에서 abcd라는 패턴을 찾을 때 텍스트 파일의 첫 번째부터 찾다가 패턴이 매치가 안되는 순간 두 번째로 이동하여서 다시 비교하고 아니라면 세번째 문자부터 시작하여 다시 비교하는 무식한 알고리즘을 의미한다. 또한 4자리의 비밀번호를 푸는 문제에서 brute force알고리즘을 적용하게 되면 가능한 모든 경우의 수는 10 * 10 * 10 * 10 = 10000번을 비교해야 풀리는 그런 방식이다. 2) 백트래킹 백트래킹은 .. c++/알고리즘 2022. 4. 29.

• 

  백준-1012번 - 유기농 배추 내가 백준 문제를 풀면서 느낀 점은 채점을 할 때 맞게 하고 싶다면 문제에서 변수들을 잘 파악해야한다는 것이다. 우선 문제를 살펴보면 테스트 케이스를 의미하는 변수 T가 존재한다. 또한 배추를 심은 배추밭의 가로길이 M, 세로 길이 N, 배추를 심은 개수 K가 존재한다. 또한 그 후 배추의 위치를 나타내는 변수론느 x, y가 존재한다. 그럼 일단 6개의 변수가 존재하는 것이다. 그 후 반복문 안에서 다음 배열 인덱스를 담아 줄 ny, nx변수와 최종 개수를 ret할 ret 변수까지 9개가 존재한다. 또한 이 문제는 깊이 탐색 문제이므로 배추의 위치를 표현할 map과 그 배열과 같은 크기의 방문 여부 배열이 필요하다. #include #include #include using namespace std; i.. c++/알고리즘 2022. 3. 29.