# Problem Solving

427개의 포스트

백준 1918: 후위 표기식 [C++]

후위 표기식의 규칙피연산자는 그냥 출력한다.연산자의 경우, 우선 순위를 따지면서 스택에 push, pop 한다.stack이 비어있으면 pushstack의 top이 현재 연산자보다 우선순위가 같거나 높으면 pop 후 출력stack의 top이 현재 연산자보다 우선순위가 낮

2일 전
·
0개의 댓글

5419. 북서풍

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

3일 전
·
0개의 댓글

1949. 우수 마을

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

4일 전
·
0개의 댓글

1781. 컵라면

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

5일 전
·
0개의 댓글

1202. 보석 도둑

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

6일 전
·
0개의 댓글

백준 2346: 풍선 터뜨리기 [C++]

보자마자 원형 큐인 것을 알았다.문제는... 원형 큐를 어떻게 구현할 것인가..?vector를 이용해야하나 생각했는데 deque으로 푸는 문제였다.

6일 전
·
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개의 댓글

백준 1966: 프린터 큐 [C++]

"우선순위"에 따른 출력 순서를 알아내야 하므로 우선순위 큐를 쓴다.우선순위 큐(Priority Queue)는 들어온 순서가 아닌 우선순위에 따라 먼저 처리되는 구조이다.우선순위 큐 - https://zoosso.tistory.com/993 참고

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

백준 10799: 쇠막대기 [C++]

쇠막대기 규칙 레이저는 여는 괄호와 닫는 괄호의 인접한 쌍 ‘( ) ’ 으로 표현된다. 또한, 모든 ‘( ) ’는 반드시 레이저를 표현한다. 쇠막대기의 왼쪽 끝은 여는 괄호 ‘ ( ’ 로, 오른쪽 끝은 닫힌 괄호 ‘) ’ 로 표현된다. 레이저와 막대기를 어떻게 구분할

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개의 댓글

프로그래머스 - 조이스틱 [Python]

문제 보기level 2 치고 상당히 까다로웠던 것 같다.우선 조이스틱의 (위, 아래) 조작과 (왼쪽, 오른쪽) 조작을 나누어 생각하는 것으로 전체적인 방향을 잡았다. 특정 위치의 문자를 바꾸는 것인 (위, 아래) 조작과 다른 위치로 이동하는 것인 (왼쪽, 오른쪽) 조작

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

1027. 고층 건물

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

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