profile
Military service - May 31, 2022 ~ Nov. 30, 2023

18246. 색종이와 쿼리

시간 제한: 1초메모리 제한: 512MB각 cell 별로 종이의 수를 구하고, 범위 내에서 최대를 빠르게 구하기 위해 Segment Tree를 이용하면 된다.그러나, Navie 하게 색종이가 주어질 때마다 위와 같이 해당 영역에 값을 더하면, 전처리 과정에서만 너무 많

2022년 5월 30일
·
0개의 댓글

11658. 구간 합 구하기 3

시간 제한: 1초메모리 제한: 256MB이 문제는 기본적인 Segment Tree 개념을 기반으로, 2D Segment Tree를 구현해야 한다.column을 기준으로 각 범위마다, row 기준 ST를 갖도록 만든다.이후, update와 getSum을 column 기준

2022년 5월 29일
·
0개의 댓글

1849. 순열

시간 제한: 0.5초메모리 제한: 512MB이처럼, ai 만큼 앞에 빈칸을 둔 자리에 i를 배치하면, 문제를 해결할 수 있다. 이때 빈칸을 Naive 하게 세면 O(N^2)이 걸린다. 이를 개선하기 위해, Segment Tree를 이용하면, 구간의 크기를 쉽게 구할 수

2022년 5월 26일
·
0개의 댓글

Strongly Connected Components (SCC)

Directed Graph의 모든 정점이 다른 모든 정점에 도달 가능한 경우, "Strongly Connected" 라고 한다. Strongly Connected Components(SCC)는 가장 큰 strongly connected subgraph이다. 예를 들어

2022년 5월 24일
·
0개의 댓글

5419. 북서풍

시간 제한: 256MB메모리 제한: 1초Naive 하게 풀면, N(N-1) 가지 쌍을 모두 조사하면 되지만 오래 걸린다. 대신, Segment Tree로 원하는 범위에 존재하는 섬을 조사할 수 있다면, 시간을 단축시킬 수 있을 것이다.남쪽 섬부터 시작해서 북쪽 섬 순서

2022년 5월 21일
·
0개의 댓글

1949. 우수 마을

시간 제한: 2초메모리 제한: 128MBNaive 하게 각 마을을 포함시키거나 빼면서 모든 경우를 조사하여 풀 수 있다. 그러나 시간 복잡도는 O(2^N)이다. 대신, xxoxA oxoxA 두 순서로 이루어진 경우가 존재할 때, 뒤에 A 순서는 중복되므로 다시 계산해

2022년 5월 20일
·
0개의 댓글

1781. 컵라면

시간 제한: 2초메모리 제한: 256MB마지막에 풀 문제부터 시작해서 거꾸로 조사하면, 매 단계에서 풀 수 있는 최적의 문제를 선택할 수 있다. 즉, Greedy 하게 풀면 된다.마지막 시간부터, 시간 0까지 단위 시간별로 풀 문제를 다음에 따라 선택한다.1\. 현재

2022년 5월 19일
·
0개의 댓글

1202. 보석 도둑

시간 제한: 1초메모리 제한: 256MB논리적으로, 작은 가방부터 가능한 최대 가치를 담으면 효율적이다. 이때, Navie 하게 찾으면 시간이 오래 걸린다. 빠르게 후보 보석들을 찾아내고 선택해야 한다.작은 가방부터 순차적으로 다음을 반복한다.1\. 현재 가방 무게에서

2022년 5월 18일
·
0개의 댓글

2104. 부분배열 고르기

시간 제한: 2초메모리 제한: 128MB가능한 양 끝 i,j의 모든 경우는 n(n+1)/2 가지이다. 대신에, Divide and Conquer로, 좌우로 분할하여 각 구간에서 최대를 찾고, 구간을 합칠 때 경계선에서 만들어지는 경우만 조사하면, 시간 복잡도를 개선할

2022년 5월 16일
·
0개의 댓글

2213. 트리의 독립집합

시간 제한: 2초메모리 제한: 128MBNaive 하게 풀려면, 다음과 같이 DFS를 진행하면서, 각 node를 포함시킬 때와 포함시키지 않을 때를 모두 조사하여 가능한 최대를 구하면 된다. 그러나, 이 경우 시간 복잡도는 O(2^N)이다.이때, 각 node에서의 최대

2022년 5월 15일
·
0개의 댓글

1517. 버블 소트

시간 제한: 1초메모리 제한: 512MBAi보다 작은 값이 Ai+1, ...., N-1 중에 k 개가 있다면 k 번 swap 해야 한다. 각 i 별로 K를 모두 구해 합해주면 된다. 이때, 매번 Naive 하게 수를 비교하면 O(N^2)이 된다. 대신에, Segment

2022년 5월 14일
·
0개의 댓글

1700. 멀티탭 스케줄링

시간 제한: 2초메모리 제한: 128MB멀티탭이 꽉 차서 무언가를 빼야 할 때, 당장 필요하지 않은, 우선순위가 낮은 것부터 빼면 된다.매 차례마다 멀티탭을 조사하여, 다음 중 하나를 선택하여 수행한다.1\. 비어있다면 그냥 꼽는다.2\. 이미 꽂혀 있다면 넘어간다.3

2022년 5월 13일
·
0개의 댓글

2250. 트리의 높이와 너비

시간 제한: 2초메모리 제한: 128MB먼저, 각 node의 위치를 구해야 한다. 이는 (왼쪽 자손의 수) + (현 node의 범위 왼쪽 끝)으로 구할 수 있다. In-Order DFS를 이용하면 된다.(l, .., ) 구간에 존재할 수 있는 현재 node의 위치를 다

2022년 5월 12일
·
0개의 댓글

3109. 빵집

시간 제한: 1초메모리 제한: 256MB파이프를 최대한 벽에 밀착시켜 건설하면 된다. 따라서 Greedy로 풀 수 있다.DFS(https://velog.io/@smsh0722/Graph - 현재 칸을 벽으로 채운다 (파이프를 건설할 수 있는 경로이든 아니든

2022년 5월 3일
·
0개의 댓글

1339. 단어 수학

시간 제한: 2초메모리 제한: 256MBABBC는 A 1000 + B 100 + B 10 + C 1로 나눌 수 있다. 이렇게 나누었을 때, A는 1000, B는 110, C는 1로 볼 수 있다. 이 논리에 따라, 모든 단어에 포함된 각 알파벳들의 값을 순서대로

2022년 5월 2일
·
0개의 댓글

1506. 경찰서

시간 제한: 2초메모리 제한: 128MBu, v가 서로 도달할 수 있다면 SCC에 해당한다.SCC 마다 각각 최소 비용의 경찰서 하나를 지으면 된다.SCC 를 구한다.각 SCC 별로 최소 비용의 경찰서 하나씩을 찾아 합한다.GraphOther

2022년 4월 29일
·
0개의 댓글

1103. 게임

문제 시간 제한: 2초 메모리 제한: 512MB Problem Analysis Algorithm Data Structure 결과 other

2022년 4월 28일
·
0개의 댓글

4991. 로봇 청소기

시간 제한: 1초메모리 제한: 256MB다음과 같은 상황을 분석해 보자.Greedy로 풀 수 없고, 문제를 풀만한 특별한 규칙을 찾을 수 없다. 따라서, 모든 경우의 수를 조사하는 수밖에 없다.BFS를 통해 물체(오염, 로봇 청소기) 간의 거리를 모두 조사한다.도달할

2022년 4월 27일
·
0개의 댓글

1027. 고층 건물

시간 제한: 2초메모리 제한: 128MB각 빌딩에서 볼 수 있는 빌딩의 수를 구해 그 중에서 최대를 찾는 방법 외에는 특별한 방법이 없다. 기울기를 이용하여 문제를 풀면 되는데, double은 부정확하기 때문에, 분모 분자를 나누어 비교해 주면 된다.각 빌딩에서 왼쪽과

2022년 4월 26일
·
0개의 댓글

5639. 이진 검색 트리

문제 시간 제한: 1초 메모리 제한: 256MB Problem Analysis 어떤 순서로 출력하든 간에, 당연히 tree를 갖고 있어야 한다. 이때, 예를들어, 한 node의 값이 30이고 구간이 [20, 50]이라면, right-subtree는 구간이 [31,

2022년 4월 25일
·
0개의 댓글