티스토리

호정s 개발 일기

검색하기

블로그 홈

호정s 개발 일기

hojung-testbench.tistory.com/m

inha univ junior frontend developer

구독자: 6

방명록 방문하기

728x90

반응형

주요 글 목록

[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 공감수 1 댓글수 0 2023. 5. 27.
[c++] 카카오 개인정보 수집 유효기간 (문자열 다루기) 1. 문제 문제 설명 고객의 약관 동의를 얻어서 수집된 1~n번으로 분류되는 개인정보 n개가 있습니다. 약관 종류는 여러 가지 있으며 각 약관마다 개인정보 보관 유효기간이 정해져 있습니다. 당신은 각 개인정보가 어떤 약관으로 수집됐는지 알고 있습니다. 수집된 개인정보는 유효기간 전까지만 보관 가능하며, 유효기간이 지났다면 반드시 파기해야 합니다. 예를 들어, A라는 약관의 유효기간이 12 달이고, 2021년 1월 5일에 수집된 개인정보가 A약관으로 수집되었다면 해당 개인정보는 2022년 1월 4일까지 보관 가능하며 2022년 1월 5일부터 파기해야 할 개인정보입니다. 당신은 오늘 날짜로 파기해야 할 개인정보 번호들을 구하려 합니다. 모든 달은 28일까지 있다고 가정합니다. 다음은 오늘 날짜가 2022.0.. 공감수 0 댓글수 0 2023. 4. 27.
[AWS] AWS-SAA-C03(Solutions Architect Associate) 합격 후기 1. 계기 나는 AWS에 대해 잘 알지 못했다. 클라우드 기술도 잘 알지 못했다. 왜냐하면 나는 프론트 엔드를 공부하고 있었고 화면 내의 컴포넌트 간의 통신에만 집중하면 됐을 뿐 전체적인 인프라는 내 몫이 아니라고 생각했었기 때문이다. 하지만 개발 공부를 점점 더 하고 깊어질수록 근본적인 의문들이 지워지지 않았다. 어떻게 웹 서비스가 서빙되는 지, 장애 조치는 어떻게 하는지, AWS로의 배포가 대세가 된 요즘 가장 효율적인 네트워크 구성은 어떻게 되는지 등 많은 질문들에 대한 답을 찾고 싶었고 이 자격증을 공부하며 많은 답을 찾을 수 있었다. 또한 클라우드 기술은 근본적으로 네트워크의 정점이라고 생각하는 기술이라 준비를 하며 네트워크에 대한 많은 지식도 얻을 수 있었다. 나는 2023-04-01일 AWS.. 공감수 3 댓글수 0 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();.. 공감수 1 댓글수 0 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 세 가지의 경우로 나눌 수 있겠다. 먼저 맨 처음.. 공감수 1 댓글수 1 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 .. 공감수 0 댓글수 0 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()이.. 공감수 0 댓글수 1 2023. 2. 16.
[c++] 백준 - 2014 소수의 곱 (우선순위 큐) 1. 문제 2. 입출력 및 예제 3. 문제 해설 우선순위 큐를 이용해 푸는 문제였다. 처음에는 아무런 생각도 하지 못하고 있다가 알고리즘 분류를 봤더니 우선순위 큐 분류에 있는 것을 확인한 후 풀 수 있었던 문제이다. 이 문제의 핵심아이디어는 다음과 같다. 우선 주어진 수들을 모두 우선순위 큐 안에 집어 넣는다. 우리는 오름차순으로 수를 구해야하므로 우선순위 큐는 오름차순으로 선언해준다. #include #include #define ll long long priority_queue pq; 그 후 오름차순 우선 순위 큐에 집어넣고 pq.top()에 해당하는 값들을 계속 원래 입력으로 받았던 소수에 곱을 해주면서 다시 우선순위큐에 집어넣어주면 그 횟수를 N번 반복했을 때의 pq의 top이 정답이 된다. 4.. 공감수 0 댓글수 0 2023. 2. 16.
[C++] 백준 - 11779 최소비용구하기2 (다익스트라) 1. 문제 2. 입출력 및 예제 3. 문제 해설 백준 - 1916 최소비용 구하기 문제와 비슷한 문제이다. 하지만 추가된 것은 몇 개의 노드를 거치면서 왔는 지에 대한 정보와 지나온 path에 대한 정보도 출력을 해야한다는 것이다. 처음에 예제 답안을 살펴보면 경로가 1 3 5로 나와있는 것을 확인할 수 있다. 하지만 위의 그래프를 그려보면 1 3 5 뿐만 아니라 1 4 5도 된다는 것을 알 수 있다. 그리고 경로에 대한 제약사항은 존재하지 않는다. 따라서 이 문제는 도달할 수 있는 경로가 여러가지일 경우에는 그냥 아무거나 출력하면 되는 문제였다. 여태까지 많은 경로를 기억했다가 출력하는 문제들을 풀어본 결과 경로를 기억하는 문제들은 대게 그 경로에 추가되는 로직이 있기 마련이다. 또한 위의 문제는 다익.. 공감수 0 댓글수 0 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를 적용해서는 안된.. 공감수 0 댓글수 0 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까.. 공감수 0 댓글수 0 2023. 2. 14.
[c++] 백준 - 1520 내리막길 (DFS + DP) 1. 문제 2. 입출력 및 예제 3. 문제 해설 상하좌우가모두 탐색이 가능하다. 그리고 제약조건이 존재한다. 바로 현재 위치보다 낮은 수로만 이동할 수 있다는 점이다. 기본적으로는 dfs탐색을 해야할 거 같았다. 결국 자신의 네 방향 중 자신보다 낮은 수가 존재한다면 이동 횟수는 상관없이 이동할 수 있는 것이고 결국 오른쪽 맨 아래 칸에 도달할 수 있는 지에 대한 여부가 중요했기 때문이다. 따라서 나는 상태를 3가지로 나누었다. -1 : 아직 방문하지 않은 곳이다. 0 : 방문한 경우이다. 0보다 큰 수 : 현재 지점에서 목적지까지 도달 할 수 있는 경우의 수가 존재하는 곳이다. 처음에는 이 문제를 백트래킹으로 접근했는데 시간초과가 났다. 물론 4가지 방향 ^ (500 * 500)이 최악의 경우라 당연히.. 공감수 0 댓글수 0 2023. 2. 14.
[c++] 백준 - 단절점(11266) [단절점 이론] 1. 문제 2. 입출력 3. 예제 입출력 4. 문제 해설 혼자 푼 문제는 아니다. 애초에 특수한 단절점과 단절선에 대한 이론을 알고 있어야해서 인터넷에서 단절점과 단절선에 대한 이론을 찾아본 후 풀었다. https://jason9319.tistory.com/119 단절점(Articulation Point)와 단절선(Bridge) 하나의 컴포넌트로 이루어진 무방향 그래프에서 한 정점을 제거했을 때 그래프가 두개 이상의 컴포넌트로 나누어지는 정점을 단절점이라고 합니다.다음과 같은 무방향 그래프가 있다고 해봅시 jason9319.tistory.com 위의 블로그에서 많은 도움을 얻었다. 내가 이해한 바를 다시 정리해 말하면 다음과 같다. 무엇이 단절점인가? 어떤 조건을 만족해야 단절점이 될 수 있을까?를 먼저.. 공감수 0 댓글수 0 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배열 .. 공감수 0 댓글수 0 2023. 2. 13.
[c++] 백준 - 공장 (인덱스드 트리) 1. 문제 2. 입출력 및 예제 3. 문제 해설 어떠한 힌트도 받지 않고 푼 첫번째 플레티넘 문제였다. 개인적으로는 백준-달리기(2517) 문제와 상당히 유사하다. 문제를 이해하면 다음과 같다. 어떤 N개의 물체들이 특정한 번호를 가지면서 존재하는데 그 밑엔 다시 N개의 물체가 동일한 수를 가지며 순서가 섞여서 존재한다. 기존 N개에 써져있던 수가 동일한 물체끼리 연결을 하는데 이 때 교차한 쌍의 수를 구하면 된다. 단순히 생각해보면 원래 물체에 써져있던 수는 하나도 중요하지 않다. 중요한 것은 그 물체가 원래 몇 번째에 존재했냐는 것이다. 위의 예제를 생각해보면 다음과 같다. 132 392 311 351 231 392 351 132 311 231 다음과 같은 물체가 존재할 때 꼬인 쌍의 수는 3이된다... 공감수 1 댓글수 0 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번째로 가능한 곱셈의 경.. 공감수 0 댓글수 0 2023. 2. 9.
[c++] 백준-집배원 한상덕(이분탐색 , 투포인터) 1. 문제 2. 입출력 및 예제 3. 문제 해설 이 문제는 난이도가 플레5였기 때문에 맞출 수 있었던 거 같다. 생각 자체는 어렵지 않았지만 이렇게까지 해야한다고...? 라는 생각이 들었다. 만약 골드하위나 실버였다면 분명 이게 아니라 다른 방법이 있을거야..라고 계속 생각만 했을 거 같았다. 이 문제의 핵심은 고도차를 최소로 모든 집을 방문해야한다는 것이다. 또한 문제를 읽어보니 N이 50으로 아주 작았다. 대부분의 경우 N이 작으면 완전탐색으로 풀어야하는 경우가 많지만 map으로 나타내면 50*50의 노드를 갖기 때문에 완전탐색의 경우의 수로 풀릴 것 같진 않았다. 따라서 생각해낸 아이디어는 이것이다. 입력받은 고도를 모두 담아 중복을 제거하고 sort한다. 우체국의 고도와 집의 고도 중 가장 큰 것.. 공감수 0 댓글수 0 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를 사용해야한다.... 어떤 문제건 두 가지 알고리즘이 섞이면 어렵지만 이 두개는 어려운 것이 두 개가 섞여 더 어려웠다. 한 번에 풀지는 못하고 이 문제의 핵심 아이디어를 찾아 본 후 구현할 수 있었다. .. 공감수 0 댓글수 0 2023. 2. 8.
[c++] 백준-1865 웜홀 (벨만포드) 1. 문제 2. 입 출력 3. 예제 4. 문제 해설 벨만 포드 알고리즘을 이용해서 (음의 가중치가 있기 때문이다! 웜홀) 음의 사이클이 존재하는 지를 판단하면 되는 문제였다. 이 문제는 그러나 일반적인 벨만포드 알고리즘과는 다른 점이 두 가지가 존재한다. 웜홀이 아닌 도로의 경우 양방향 도로이다. 출발 노드가 정해져있지 않다. 벨만포드 알고리즘은 모든 간선을 노드 수 -1 만큼 탐색하면서 한 노드로부터 다른 노드들의 최단 거리를 갱신해가는 알고리즘이다. 원래는 간선의 시작 노드에 해당하는 노드를 방문한 적이 없다면 continue를 통해 넘기는 로직이 존재한다. 왜냐하면 시작 노드가 존재하기 때문에 시작노드로부터 간선이 도착한 적이 있어야 최단 경로를 계산할 수 있기 때문이다. 하지만 이 문제에서는 시작.. 공감수 0 댓글수 0 2023. 2. 7.
[c++] 백준-1956 운동 (플로이드 워셜) 1. 문제 2. 입출력 및 예제 3. 문제 해설 플로이드 워셜 알고리즘에서 사이클을 찾는 문제였다. 플로이드 알고리즘은 2차원 배열을 선언해두고 진행하는데 대각선에 있는 값들은 대게 0으로 초기화해두고 진행하는 것이 일반적이다. 하지만 이는 사이클이 존재하지 않을 때에 해당하고 사이클이 존재한다면 자기 자신으로 돌아오는 경우의 수가 있기 때문에 2차원 배열의 대각선 값이 0이 되지 않고 다른 값으로 변할 것이다. 따라서 조건을 추가해주어햐 하는 것들이 존재한다. 0 INF INF INF 0 INF INF INF 0 플로이드 알고리즘은 위와 같이 정사각형의 배열을 대각선의 값은 0 대각선을 제외한 값은 INF(무한대)값으로 초기화해두고 진행한다. 그 후 입력을 받으면 배열이 다음과 같이 된다. (플로이드 .. 공감수 0 댓글수 0 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를 그냥 지나가기만 하면 되었다. ... 그래서 생각 방향을 바꾸어 다시 생각을 해보니 이 문제가 오히려 갔던 길을 다시 가도 된다고.. 공감수 0 댓글수 0 2023. 2. 6.
[c++] 백준 - 합이 0인 네 정수 ( 이분탐색) 1. 문제 2. 입출력 및 예제 3. 문제 해설 처음에 이 문제를 접했을 때 비슷한 문제가 생각났다. 백준-피자판매 문제와 백준-두배열의 합 문제였다. 따라서 처음엔 두 문제와 같이 map을 사용해서 풀면 쉽게 풀릴 줄 알았다. 위의 두 문제의 경우 가능한 모든 합의 경우의 수를 미리 구해두어 map에 그 합과 그 합이 나오는 경우의 수를 모두 저장해둔다. 그 후 다른 배열을 돌면서 합이 K가 되는 경우를 구해야한다면 cnt += map[K - 다른배열[i]]와 같은 로직으로 경우의 수를 모두 구해 더해주면 되었다. unordered_map의 경우 정렬을 하지 않는 map이고 hash table을 기반으로 하는 자료구조이기 때문에 O(1)의 시간복잡도로 원하는 자료에 접근이 가능했다. 하지만 위의 접근 .. 공감수 0 댓글수 0 2023. 2. 6.
[c++] 백준- 보석도둑 (Greedy) 1. 문제 2. 입출력 및 예제 3. 문제 해설 이 문제를 처음 봤을 때 완전탐색으로는 아주 쉬운 알고리즘으로 풀 수 있겠다는 생각을 했다. 담을 수 있는 무게가 다른 가방이 여러개 있고 보석의 무게와 가치가 여러개 존재한다면 당연히 보석을 최대한의 가치로 가져가는 방법은 담을 수 있는 무게가 가장 작은 가방부터 최대로 채워가는 것이다. 다시 말하면 가장 담을 수 있는 무게가 작은 가방부터 담을 수 있는 보석 중 가장 높은 가치를 가지고 있는 보석을 차례대로 담아가면 되는 것이다. 이것을 완전탐색으로 풀면 for문을 두 번 돌면서 그냥 이 보석이 이 가방에 담을 수 있는 것인지 아닌지를 판별한다음 담을 수 있다면 담을 수 있는 것 중 가장 가치가 큰 것을 선택해 답에 포함시켜주고 선택된 것을 제외시켜주면.. 공감수 0 댓글수 0 2023. 2. 5.
[c++] 백준 - lca (그래프 이론) 1. 문제 2. 입 출력 3. 예제 입출력 4. 문제 해설 처음 이 문제를 마주했을 때 나는 대강 풀이법을 들어서 알고 있었다. 따라서 조금 빨리 구현할 수 있었던 거 같다. 그런데 한 가지 고민했던 점은 부모노드와 자식노드를 어떻게 판별하는 것일까였다. 처음에는 입력의 순서가 부모-자식 순인가 했었지만 다시 생각해보니 부모-자식 순으로 입력이 들어오는 것은 아닌 거 같았다. 처음에 들어오는 입력이 더 클 수도 나중에 들어오는 입력이 더 큰 경우도 존재했기 때문이다. 그래서 그 다음 생각했던 것은 입력의 순서대로 트리가 구성되는 것인가?를 고민해보았다. 그러면 입력이 어떻게 들어오든 앞선 입력에 존재하는 노드가 부모가 되겠거니 했다. 그래서 양방향으로 벡터에 푸쉬해주었다. 1. 입력 (양방향으로 연결성을.. 공감수 0 댓글수 0 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)정도였다. 결국 알고리즘 분류를 봐버렸.. 공감수 0 댓글수 0 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); // 왼쪽 자식 노드의 값이 구하고자 하는 값보다 부족하다면 오른쪽 자식 노드로 이동 } } .. 공감수 0 댓글수 2 2023. 2. 2.
[c++] 인덱스드 트리에 관하여 1. 인덱스드 트리란? 인덱스드 트리란 어떤 수열이 존재할 때 각 구간의 대표값들로 이루어진 트리를 의미한다. 주로 부분합, 부분 곱, 부분 차 등 구간 별 값을 구해야하는 상황에서 많이 사용된다. 또한 수열의 값이 자주 변경되는 상황에서도 많이 사용된다. 누적 합 배열과 같이 처음부터 순서대로 누적되는 합의 배열을 구하는 방식의 경우 중간에 하나의 값이 변경되면 그 값의 인덱스부터 수열의 끝까지 다시 누적합을 구해야하는 치명적인 단점이 있다. 만약 제일 처음 원소가 변경되었다면 모든 누적합 배열을 처음부터 다시 계산해야한다.O(N)이 걸린다. 기본적으로 트리라는 자료구조는 O(logN)의 시간복잡도를 위한 자료구조이다. 시간복잡도를 얻는 대신 공간복잡도를 살짝 trade-off하긴 하지만 요즘 메모리는.. 공감수 1 댓글수 2 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일차의 상담을 선택하거나 선택하지 않을 수 있는데 이.. 공감수 0 댓글수 0 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 +=.. 공감수 0 댓글수 0 2023. 1. 31.
[C++] 백준 - 전구 문제 2. 입출력 3. 문제 해설 문제를 읽어보면 최대 K가지의 서로 다른 색을 표현할 수 있는 전구들이 존재하고 이 전구 N개를 한 줄로 배치한다. 한 줄로 배치한다는 것은 고리 형태가 아닌 자신의 양 옆의 전구만이 자신에게 영향을 줄 수 있다는 뜻이다. 또한 임의의 전구를 하나 잡아 색을 바꾼다. 그런데 이 임의의 전구와 인접한 전구가 같은 색이라면 이 전구 또한 색상이 변한다. 그러면 이 문제는 최소 문제로 쪼갤 수 있다. 바로 옆의 전구가 변했을 때 색이 같다면 변하고 색이 다르다면 변하지 않는 것이다. 그러면 이 문제는 dp를 적용해 memoization 해 가면서 풀 수 있을 거 같다고 생각했다. 이 문제에서 제일 까다로운 점은 임의의 전구부터 시작할 수 있다는 점이다. 또한 dp를 이용하려면.. 공감수 0 댓글수 1 2023. 1. 30.

728x90

반응형

문의안내

티스토리
로그인
고객센터

티스토리는 카카오에서 사랑을 담아 만듭니다.