C++47

• [c++] 카카오 개인정보 수집 유효기간 (문자열 다루기) 1. 문제 문제 설명 고객의 약관 동의를 얻어서 수집된 1~n번으로 분류되는 개인정보 n개가 있습니다. 약관 종류는 여러 가지 있으며 각 약관마다 개인정보 보관 유효기간이 정해져 있습니다. 당신은 각 개인정보가 어떤 약관으로 수집됐는지 알고 있습니다. 수집된 개인정보는 유효기간 전까지만 보관 가능하며, 유효기간이 지났다면 반드시 파기해야 합니다. 예를 들어, A라는 약관의 유효기간이 12 달이고, 2021년 1월 5일에 수집된 개인정보가 A약관으로 수집되었다면 해당 개인정보는 2022년 1월 4일까지 보관 가능하며 2022년 1월 5일부터 파기해야 할 개인정보입니다. 당신은 오늘 날짜로 파기해야 할 개인정보 번호들을 구하려 합니다. 모든 달은 28일까지 있다고 가정합니다. 다음은 오늘 날짜가 2022.0.. c++/알고리즘 2023. 4. 27.

• 

  [c++] 백준-최대공약수 하나 빼기 ( 누적합, 정수론) 1. 문제 2. 입출력 및 예제 3. 문제 해설 하나를 뺐을 때 최대공약수가 최대가 되어야한다. 이 문제를 해결하기 위해서는 누적합의 개념을 적용해야한다. 사실 누적합은 누적해서 합을 구하는 것에만 쓰이는 개념은 아니다. 여태까지 나온 값들의 대표값을 의미하기도 한다. 그래서 세그먼트 트리나 인덱스드 트리로도 풀 수 있을 거 같은 문제였다. 핵심 아이디어는 다음과 같다. LtoR : 왼쪽서부터 최대 공약수를 구해 저장하는 배열 RtoL : 오른쪽서부터 최대 공약수를 구해 저장하는 배열 두 배열이 존재한다면 예제의 경우 다음과 같다. index 0 1 2 3 4 nums 8 12 24 36 48 LtoR 8 4 4 4 4 RtoL 12 12 12 12 48 세 가지의 경우로 나눌 수 있겠다. 먼저 맨 처음.. c++/알고리즘 2023. 2. 28.

• 

  [c++] 백준 - 1655 가운데를 말해요(우선순위 큐) 1. 문제 2. 입력 및 출력 3. 문제 해설 priority_queue를 적절히 사용하여 중간값을 찾아내면 되는 문제였다. 우선 중간값을 찾아야한다는 점에서 pq가 두 가지가 필요하다는 것을 알 수 있었다. 우리는 최대힙과 최소힙을 각각 하나씩 선언하여 중간을 찾아내면 된다. 그런데 문제에서 만약 짝수개가 들어갔을 경우에는 더 작은 값을 찾아내라 했으니 정답은 최대 힙에 들어있을 수 있을 것이다. 왜냐하면 pq에서 접근할 수 있고 의미가 있는 값은 pq.top()에 해당하는 부분이다. top()이 항상 답이 되게 하려면 우리는 다음과 같이 pq를 구성해야한다. 만약 1 5 2 10 이라는 수열을 기준으로 봤을 때 정렬을 하면 1 2 5 10이 되고 이 기준에서 중간값은 2에 해당한다. pq.top()이.. c++/알고리즘 2023. 2. 16.

• 

  [c++] 백준-10999 구간합구하기2 (세그먼트트리, lazy_loading) 1. 문제 2. 입출력 및 예제 3. 문제 해설 이 문제는 백준 2042 구간합구하기 문제와 거의 동일하다. 단 하나 차이점이 있다면 이 문제에서는 단 하나의 수를 교체하는 것이 아니라 2번째 수부터 8번째 수를 9로 변경해 등과 같이 구간이 업데이트 된다는 점이다. 이 경우 최악의 시간복잡도는 처음부터 끝 구간을 변경하는 경우가 되고 update하는 데 드는 시간이 O(NlogN)이 된다. 이 문제에서 N은 백만이고 O(NlogN) 은 백만 * 1000 = 10억 번의 연산을 해야한다는 것이다. 대략적으로 c++언어로 1초라는 제한시간안에 통과하려면 1억번 정도의 연산을 수행해야하는데 위의 연산 횟수는 터무니 없다고 할 수 있다. 따라서 이 문제는 일반적인 세그먼트 트리의 update를 적용해서는 안된.. c++/알고리즘 2023. 2. 15.

• 

  [c++] 백준 - 11066 파일 합치기 (dp) 1. 문제 2. 예제 입출력 3. 문제 해설 다이나믹 프로그래밍 문제이다. 나는 한 번 최소의 값을 구하는 과정을 생각해보았다. 내가 풀어본 대부분의 dp문제 중 이 문제는 dp[x][y]를 x번째에서 y번째까지의 파일 합치기의 최소값을 기억해두는 문제였다. (백준-전구)에서 사용한 dp배열과 비슷하다. 대부분 이렇게 x ~ y에서의 최소 값을 dp배열에 저장하면 중간에 k라는 구간을 두어 for문을 반복하며 최소 값을 찾아내는 형태로 많이 나온다. 이 문제 또한 동일했다. dp문제 정의 dp배열 정의 : dp[x][y] : x번째 파일에서 y번째 파일까지 합치기의 최소 값 점화식 : dp[i][i+j] = min(dp[i][j] , dp[i][k] + dp[k+1][i+j]) k 는 i부터 i+j-1까.. c++/알고리즘 2023. 2. 14.

• 

  [c++] 백준 - 단절점(11266) [단절점 이론] 1. 문제 2. 입출력 3. 예제 입출력 4. 문제 해설 혼자 푼 문제는 아니다. 애초에 특수한 단절점과 단절선에 대한 이론을 알고 있어야해서 인터넷에서 단절점과 단절선에 대한 이론을 찾아본 후 풀었다. https://jason9319.tistory.com/119 단절점(Articulation Point)와 단절선(Bridge) 하나의 컴포넌트로 이루어진 무방향 그래프에서 한 정점을 제거했을 때 그래프가 두개 이상의 컴포넌트로 나누어지는 정점을 단절점이라고 합니다.다음과 같은 무방향 그래프가 있다고 해봅시 jason9319.tistory.com 위의 블로그에서 많은 도움을 얻었다. 내가 이해한 바를 다시 정리해 말하면 다음과 같다. 무엇이 단절점인가? 어떤 조건을 만족해야 단절점이 될 수 있을까?를 먼저.. c++/알고리즘 2023. 2. 13.

• 

  [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++] 백준-행렬곱셈순서 (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++] 백준 - 특정한 최단 경로 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.