c++/알고리즘54

• 

  [c++] 백준-스도쿠 1520 - 백트래킹 1. 문제 2. 입출력 3. 예제 입 출력 4. 문제 해설 우리가 흔히 알고 있는 스도쿠 문제를 백트래킹을 이용해서 푸는 문제였다. 생각해보면 우리가 스도쿠를 푸는 과정도 백트래킹과 같다. 내가 문제를 푼 과정은 다음과 같다. 입력을 받는다. rows라는 2차원 배열에 각 행마다 1 ~ 9가 나왔는 지에 대한 정보를 저장해준다. cols라는 2차원 배열에 각 열마다 1 ~ 9가 나왔는 지에 대한 정보를 저장해준다. square라는 2차원 배열에 각각의 작은 4각형마다 1 ~ 9가 나왔는 지에 대한 정보를 저장해준다. vector에 0에 해당하는(우리가 구해야하는) 좌표를 저장해주었다. 깊이 우선탐색을 이용한다. 깊이 우선 탐색을 이용해 1 ~ 9까지 순서대로 그 칸에 해당하는 rows배열과 cols배열 .. c++/알고리즘 2023. 2. 13.

• 

  [c++] 백준 - 공장 (인덱스드 트리) 1. 문제 2. 입출력 및 예제 3. 문제 해설 어떠한 힌트도 받지 않고 푼 첫번째 플레티넘 문제였다. 개인적으로는 백준-달리기(2517) 문제와 상당히 유사하다. 문제를 이해하면 다음과 같다. 어떤 N개의 물체들이 특정한 번호를 가지면서 존재하는데 그 밑엔 다시 N개의 물체가 동일한 수를 가지며 순서가 섞여서 존재한다. 기존 N개에 써져있던 수가 동일한 물체끼리 연결을 하는데 이 때 교차한 쌍의 수를 구하면 된다. 단순히 생각해보면 원래 물체에 써져있던 수는 하나도 중요하지 않다. 중요한 것은 그 물체가 원래 몇 번째에 존재했냐는 것이다. 위의 예제를 생각해보면 다음과 같다. 132 392 311 351 231 392 351 132 311 231 다음과 같은 물체가 존재할 때 꼬인 쌍의 수는 3이된다... c++/알고리즘 2023. 2. 9.

• 

  [c++] 백준-행렬곱셈순서 (dynamic programming) 1. 문제 2. 입출력 및 예제 3. 문제 해설 dp문제이다. 그리고 여태까지 dp배열을 채우던 방식과는 조금 다른 형태이다. 대부분의 dp문제에서는 가로 방향으로 dp배열을 채우거나 세로 방향으로 dp배열을 채워갔다. 하지만 이 문제는 대각선으로 채워가야하는 문제이다. dp문제를 풀 때는 세 가지 과정을 거쳐야한다고 했다. dp 배열의 정의 점화식 찾기 초기값 설정 나는 dp[i][i]를 i번째 배열에서 j번째 배열까지의 곱셈 연산 최소 횟수로 정의했다. 내가 생각한 점화식은 다음과 같다. 우선 행렬곱셈에 대해 알아보면 5 * 3 , 3 * 2, 2 * 6과 같이 세 행렬이 존재할 때 1번째로 가능한 곱셈의 경우는 앞의 두 행렬을 먼저 계산하고 마지막 행렬을 계산하는 것이다. 2번째로 가능한 곱셈의 경.. c++/알고리즘 2023. 2. 9.

• 

  [c++] 백준-집배원 한상덕(이분탐색 , 투포인터) 1. 문제 2. 입출력 및 예제 3. 문제 해설 이 문제는 난이도가 플레5였기 때문에 맞출 수 있었던 거 같다. 생각 자체는 어렵지 않았지만 이렇게까지 해야한다고...? 라는 생각이 들었다. 만약 골드하위나 실버였다면 분명 이게 아니라 다른 방법이 있을거야..라고 계속 생각만 했을 거 같았다. 이 문제의 핵심은 고도차를 최소로 모든 집을 방문해야한다는 것이다. 또한 문제를 읽어보니 N이 50으로 아주 작았다. 대부분의 경우 N이 작으면 완전탐색으로 풀어야하는 경우가 많지만 map으로 나타내면 50*50의 노드를 갖기 때문에 완전탐색의 경우의 수로 풀릴 것 같진 않았다. 따라서 생각해낸 아이디어는 이것이다. 입력받은 고도를 모두 담아 중복을 제거하고 sort한다. 우체국의 고도와 집의 고도 중 가장 큰 것.. c++/알고리즘 2023. 2. 8.

• 

  [c++] 백준-LCA2 (Least Common Ancestor) 1. 문제 2. 입출력 및 예제 3. 문제 해설 백준 - lca와 문제는 같다. 그러나 달라진 점이 있다면 노드의 개수가 10000개로 늘었다. 그리고 알아내야하는 노드의 쌍의 수도 늘었다. 이 문제는 그러면 이전 lca문제처럼 bfs나 dfs로 tree의 depth를 알아낸다. depth가 더 큰 쪽을 parent배열을 이용해 작은쪽과 depth를 맞춘다. 한칸 씩 올리다가 만나는 것이 lca에 해당한다. 위의 알고리즘을 사용하면 시간초과가 나게 된다. 그래서 이 문제는 dp를 적용해 lca + dp를 사용해야한다.... 어떤 문제건 두 가지 알고리즘이 섞이면 어렵지만 이 두개는 어려운 것이 두 개가 섞여 더 어려웠다. 한 번에 풀지는 못하고 이 문제의 핵심 아이디어를 찾아 본 후 구현할 수 있었다. .. c++/알고리즘 2023. 2. 8.

• 

  [c++] 백준-1865 웜홀 (벨만포드) 1. 문제 2. 입 출력 3. 예제 4. 문제 해설 벨만 포드 알고리즘을 이용해서 (음의 가중치가 있기 때문이다! 웜홀) 음의 사이클이 존재하는 지를 판단하면 되는 문제였다. 이 문제는 그러나 일반적인 벨만포드 알고리즘과는 다른 점이 두 가지가 존재한다. 웜홀이 아닌 도로의 경우 양방향 도로이다. 출발 노드가 정해져있지 않다. 벨만포드 알고리즘은 모든 간선을 노드 수 -1 만큼 탐색하면서 한 노드로부터 다른 노드들의 최단 거리를 갱신해가는 알고리즘이다. 원래는 간선의 시작 노드에 해당하는 노드를 방문한 적이 없다면 continue를 통해 넘기는 로직이 존재한다. 왜냐하면 시작 노드가 존재하기 때문에 시작노드로부터 간선이 도착한 적이 있어야 최단 경로를 계산할 수 있기 때문이다. 하지만 이 문제에서는 시작.. c++/알고리즘 2023. 2. 7.

• 

  [c++] 백준-1956 운동 (플로이드 워셜) 1. 문제 2. 입출력 및 예제 3. 문제 해설 플로이드 워셜 알고리즘에서 사이클을 찾는 문제였다. 플로이드 알고리즘은 2차원 배열을 선언해두고 진행하는데 대각선에 있는 값들은 대게 0으로 초기화해두고 진행하는 것이 일반적이다. 하지만 이는 사이클이 존재하지 않을 때에 해당하고 사이클이 존재한다면 자기 자신으로 돌아오는 경우의 수가 있기 때문에 2차원 배열의 대각선 값이 0이 되지 않고 다른 값으로 변할 것이다. 따라서 조건을 추가해주어햐 하는 것들이 존재한다. 0 INF INF INF 0 INF INF INF 0 플로이드 알고리즘은 위와 같이 정사각형의 배열을 대각선의 값은 0 대각선을 제외한 값은 INF(무한대)값으로 초기화해두고 진행한다. 그 후 입력을 받으면 배열이 다음과 같이 된다. (플로이드 .. c++/알고리즘 2023. 2. 7.

• 

  [c++] 백준 - 특정한 최단 경로 1. 문제 2. 입출력 및 예제 3. 문제 해설 처음 이 문제를 읽었을 때 잘못 이해해서 얼마나 고생을 했던지... 나는 v1, v2를 이어주는 간선을 무조건 지나야한다는 줄 알고 처음에는 1 ~ v1, v2의 다익스트라를 1번 수행하고 N ~ v1,v2를 수행해서 1 ~ v1 + v1 ~ v2 + v2 ~ N과 1 ~ v2 + v2 ~ v1 + v1 ~ N 값 중 더 작은 값을 구하려고 했다. .. 다익스트라 2번이면 되었기 때문이다. 하지만 계속 틀렸다...! 그래서 왜일까 문제를 다시 읽어보니 v1, v2를 이어주는 간선을 무조건 지나가야 하는 것이 아니라 v1, v2를 그냥 지나가기만 하면 되었다. ... 그래서 생각 방향을 바꾸어 다시 생각을 해보니 이 문제가 오히려 갔던 길을 다시 가도 된다고.. c++/알고리즘 2023. 2. 6.

• 

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