분류 전체보기154

• 

  [C++] 백준 - 12784 인하니카 공화국 1. 문제 2. 입출력 3. 문제 해설 이 문제는 DFS 중에서 Leaf 노드를 판별하고 리프노드의 전체 합과 자신을 비교해 잘라주면서 돌아오면 되는 문제이다. 따라서 나는 다음과 같이 해결했다. 우선 다리가 양방향 다리이므로 그래프는 양방향으로 설정해주었다. for (int j = 0; j < M; j++) { int s, e, c; scanf("%d %d %d", &s, &e, &c); AL[s].push_back({ e,c }); AL[e].push_back({ s, c }); } 그 후 모든 다리를 입력받았을 때 원소의 개수가 1개일 때는 Leaf 노드에 해당한다. for (int i = 2; i c++/알고리즘 2023. 5. 27.

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

• 

  [AWS] AWS-SAA-C03(Solutions Architect Associate) 합격 후기 1. 계기 나는 AWS에 대해 잘 알지 못했다. 클라우드 기술도 잘 알지 못했다. 왜냐하면 나는 프론트 엔드를 공부하고 있었고 화면 내의 컴포넌트 간의 통신에만 집중하면 됐을 뿐 전체적인 인프라는 내 몫이 아니라고 생각했었기 때문이다. 하지만 개발 공부를 점점 더 하고 깊어질수록 근본적인 의문들이 지워지지 않았다. 어떻게 웹 서비스가 서빙되는 지, 장애 조치는 어떻게 하는지, AWS로의 배포가 대세가 된 요즘 가장 효율적인 네트워크 구성은 어떻게 되는지 등 많은 질문들에 대한 답을 찾고 싶었고 이 자격증을 공부하며 많은 답을 찾을 수 있었다. 또한 클라우드 기술은 근본적으로 네트워크의 정점이라고 생각하는 기술이라 준비를 하며 네트워크에 대한 많은 지식도 얻을 수 있었다. 나는 2023-04-01일 AWS.. deployment/AWS 2023. 4. 26.

• 

  [c++] 백준 - 도로 네트워크(lca) 1. 문제 2. 입 출력 3. 예제 4. 문제 해설 이 문제는 lca를 이용한 문제였다. 문제 자체에서 가장 root노드가 무엇인지 주진 않았지만 1번 노드를 root로 삼아 (왜냐하면 1번 노드는 항상 나오기 때문이다.) 트리를 구성하고 그 후 효율적인 lca풀이를 이용하면 충분히 구할 수 있는 문제이다. 이 문제는 또한 lca를 구성하는 과정에서 구간의 최댓값과 최솟 값을 저장하며 가야하는 문제이다. 따라서 dp문제의 성향이 강하다고 할 수 있겠다. 우선 효율적인 lca 풀이를 위해 tree를 구성해준다. 나는 bfs를 통해 트리를 만들어주었다. void makeTree() { depth[1] = 1; q.push({ 1 }); while (q.size()) { int curr = q.front();.. c++/알고리즘 2023. 3. 3.

• 

  [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++] 백준 - 케이크 자르기2 10714 1. 문제 2. 입 출력 3. 예제 입출력 4. 문제 해설 dp의 문제이다. 백준 - 카드게임 문제와 비슷하다. 이 문제는 직접 게임의 형태를 구현하는 방향으로 dp를 구성해야했다. 우선 문제를 읽어보면 ioi와 joi가 번갈아가면서 케이크를 가져간다. 하지만 ioi의 경우에는 둘 중 더 큰 조각만을 가져간다. 무조건 정해져있는 것이다. 하지만 이 경우 greedy처럼 더 큰 것만을 가져간다고 더 최적의 결과가 보장되는 것은 아니다. 따라서 joi가 가져갈 때는 dp값을 통해 더 좋은 결과를 가져가야한다. 또한 재귀를 이용해 dp를 구성해야한다. 우선 환형태를 어떻게 구현해야하는 지에 대해 고민을 해보았다. 2가지 방법이 떠올랐었는데 하나는 2 5 7 8 10의 조각이 있을 경우 2 5 7 8 10 2 .. c++/알고리즘 2023. 2. 27.

• 

  [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++] 백준 - 2014 소수의 곱 (우선순위 큐) 1. 문제 2. 입출력 및 예제 3. 문제 해설 우선순위 큐를 이용해 푸는 문제였다. 처음에는 아무런 생각도 하지 못하고 있다가 알고리즘 분류를 봤더니 우선순위 큐 분류에 있는 것을 확인한 후 풀 수 있었던 문제이다. 이 문제의 핵심아이디어는 다음과 같다. 우선 주어진 수들을 모두 우선순위 큐 안에 집어 넣는다. 우리는 오름차순으로 수를 구해야하므로 우선순위 큐는 오름차순으로 선언해준다. #include #include #define ll long long priority_queue pq; 그 후 오름차순 우선 순위 큐에 집어넣고 pq.top()에 해당하는 값들을 계속 원래 입력으로 받았던 소수에 곱을 해주면서 다시 우선순위큐에 집어넣어주면 그 횟수를 N번 반복했을 때의 pq의 top이 정답이 된다. 4.. c++/알고리즘 2023. 2. 16.

• 

  [C++] 백준 - 11779 최소비용구하기2 (다익스트라) 1. 문제 2. 입출력 및 예제 3. 문제 해설 백준 - 1916 최소비용 구하기 문제와 비슷한 문제이다. 하지만 추가된 것은 몇 개의 노드를 거치면서 왔는 지에 대한 정보와 지나온 path에 대한 정보도 출력을 해야한다는 것이다. 처음에 예제 답안을 살펴보면 경로가 1 3 5로 나와있는 것을 확인할 수 있다. 하지만 위의 그래프를 그려보면 1 3 5 뿐만 아니라 1 4 5도 된다는 것을 알 수 있다. 그리고 경로에 대한 제약사항은 존재하지 않는다. 따라서 이 문제는 도달할 수 있는 경로가 여러가지일 경우에는 그냥 아무거나 출력하면 되는 문제였다. 여태까지 많은 경로를 기억했다가 출력하는 문제들을 풀어본 결과 경로를 기억하는 문제들은 대게 그 경로에 추가되는 로직이 있기 마련이다. 또한 위의 문제는 다익.. c++/알고리즘 2023. 2. 15.

• 

  [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++] 백준 - 1520 내리막길 (DFS + DP) 1. 문제 2. 입출력 및 예제 3. 문제 해설 상하좌우가모두 탐색이 가능하다. 그리고 제약조건이 존재한다. 바로 현재 위치보다 낮은 수로만 이동할 수 있다는 점이다. 기본적으로는 dfs탐색을 해야할 거 같았다. 결국 자신의 네 방향 중 자신보다 낮은 수가 존재한다면 이동 횟수는 상관없이 이동할 수 있는 것이고 결국 오른쪽 맨 아래 칸에 도달할 수 있는 지에 대한 여부가 중요했기 때문이다. 따라서 나는 상태를 3가지로 나누었다. -1 : 아직 방문하지 않은 곳이다. 0 : 방문한 경우이다. 0보다 큰 수 : 현재 지점에서 목적지까지 도달 할 수 있는 경우의 수가 존재하는 곳이다. 처음에는 이 문제를 백트래킹으로 접근했는데 시간초과가 났다. 물론 4가지 방향 ^ (500 * 500)이 최악의 경우라 당연히.. c++/알고리즘 2023. 2. 14.