백준
1.[백준] 1927 최소 힙 [C++]
처음에 힙을 직접 구현해서 풀었는데, 시간초과를 해결하지 못하고 결국 C++ STL을 사용하였다. priority_queue [C++ / STL] > C++에 STL로 우선순위 큐가 있는데, 최대 힙으로 구성되어 있다. 핵심 메소드 > push() : 우선순위 큐에
2.[백준] 1931 회의실 배정 [C++]
이 문제는 그리디 알고리즘으로 풀 수 있다. 가능한 많은 회의를 겹치지 않게 배정하는 문제로, 그리디 알고리즘의 Interval Scheduling Problem에 해당한다. 회의의 끝나는 시간이 빠른 순서로 정렬한 후, 정렬된 순서대로 겹치지 않는 회의들을 골라 배정
3.[백준] 17298 오큰수 [C++]
오큰수: 수열에서 해당 수의 오른쪽에 있으면서 큰 수 중에서 가장 왼쪽에 있는 수로, 오큰수가 없는 경우 -1을 삽입. 처음에는 스택을 사용하지 않고 그냥 벡터에 넣고 단순히 현재 오큰수를 구하는 인덱스의 다음 인덱스부터 탐색하면서 큰 수가 나오면 바로 벡터에 넣고 b
4.[백준] 9095 1,2,3 더하기 [java]
https://www.acmicpc.net/problem/9095DP n을 1,2,3의 합으로 나타낼 수 있는 방법의 수를 구하는 것으로, 전형적인 dp문제이다. 따라서, dp 테이블을 만들고, 초반에 구할 수 있는 수들의 값을 구하고 그 후부터는 문제를 쪼개
5.[백준] 1715 카드 정렬하기 [java]
https://www.acmicpc.net/problem/1715그리디 알고리즘 문제이다. 항상 작은 값들을 골라서 더해야 최종 더한 값이 가장 작은 값이 나오기 때문이다. local optimal == global optimal이 성립한다. 따라서 처음에는
6.[백준] 11723 집합 [java]
https://www.acmicpc.net/problem/11723중복을 제거하여 자료를 저장해야 한다 -> set 처음에 시간 초과가 났는데 check일때마다 sout을 찍는 것이 문제가 되었다. 입출력이기 때문에 느리다. 따라서, 이를 해결하기 위해 Str
7.[백준] 1202 보석도둑 [java]
https://www.acmicpc.net/problem/1202무게와 가치가 다른 보석을 한 가방에 담는 대표적인 그리디 알고리즘 문제를 살짝 변형한 문제이다. 다른 점은, 무게가 정해진 가방에 하나의 보석만 담을 수 있고, 여러개의 보석을 담을 수 있다는
8.[백준] 2493 탑 [java]
https://www.acmicpc.net/problem/2493위 그림으로 이해하면 될 것 같다. 쉽게 생각하면 그냥 뒤에서부터 2중 반복문을 돌면서 본인보다 큰 탑이 있다면 크 탑의 인덱스를 저장하고, 없다면 0을 저장하는 식으로 풀면 될 것이라고 생각된다
9.[백준] 1697 숨바꼭질 [java]
https://www.acmicpc.net/problem/1697수평선에 시작점에서 끝점까지 이동하는 최소 거리를 구하는 것으로 전형적인 dp 문제이다. 생각해보면, 시작점에서 왼쪽으로 가는 방법은 한 칸씩 이동하는 방법밖에 없으므로, dp배열에서 시작점부터
10.[백준] 3474 교수가 된 현우 [java]
https://www.acmicpc.net/problem/3474주어진 n의 n!의 오른쪽 끝에 있는 0의 갯수를 구하면 된다. 쉽게 생각하면, n! 수를 모두 탐색하면서 2와 5의 갯수를 구하면 될 것 같다. ex) 10! --> 1, 2, 3, 4, 5,
11.[백준] 16234 인구 이동 [java]
https://www.acmicpc.net/problem/16234구현 + 완전탐색 문제이다. 완전탐색은 BFS로 구현하였다. BFS는 평균적인 성능(시간)이 DFS보다 좋다. 현재 위치에서 상하좌우를 탐색하면서 |현재 칸 인구 수 - 탐색 칸 인구 수| 가
12.[백준] 2805 나무 자르기 [java]
문제 > https://www.acmicpc.net/problem/2805 풀이법 > 이분탐색 문제로, 톱의 높이를 이분탐색하여 답을 찾으면 된다. 이때 시작은 start = 0, end = 나무 중 가장 높은 것의 높이 로 하고, 만약, mid로 자른 나무들이 목표
13.[백준] 2193 이친수 [java]
https://www.acmicpc.net/problem/2193완전탐색으로 풀면 솔직히 쉬울 것 같았다. 탐색하고 조건에 맞는 것들의 수를 세면 되기 때문. 하지만, dp 연습을 하기 위해 이 문제를 선택했고, dp로 문제를 풀었다. 맨 앞은 1로 시작해야
14.[백준] 9465 스티커 [java]
https://www.acmicpc.net/problem/9465지그재그로 선택하면 칸을 많이 선택할 수 있으니, 두 경우중 하나를 선택하면 되나.. 했는데, 그렇게 간단할 리가 없고,,, 이런 경우도 있다. 이렇게 하면 겹치는거 없이 모든 스티커를 뗄 수 있
15.[백준] 5427 불 [java]
문제 > https://www.acmicpc.net/problem/5427 DFS vs BFS > 문제에서, 몇 초만에 탈출하는지, 최소 시간을 구해야 하기 때문에, 직관적으로 보면 DFS를 사용하는게 편하다. 왜냐면, DFS는 깊이 우선 탐색으로, 깊이를 측정하면서
16.[백준] 1522 문자열 교환 [java]
https://www.acmicpc.net/problem/1522start와 end 지점을 설정해 놓고, start++ / ++end를 진행하며 옆으로 이동하는 알고리즘이다. 배열이나 리스트에서 한 칸씩 이동하면서 어떤 조건을 확인할 때, 사용하면 좋다. 한
17.[백준] 14501 퇴사 [java]
https://www.acmicpc.net/problem/14501그리디 ? 단위 상담(하루) 당 금액이 큰 순으로 정렬해서 풀어볼까 했지만, 상담을 쪼갤 수 없기에 그리디가 아닌 DP로 판단했다. bottom-up 방식으로 생각하다보니, 너무 어려웠다. 따라
18.[백준] 2579 계단 오르기 [java]
https://www.acmicpc.net/problem/25791 or 2 계단씩 올라갈 수 있다. 중요한 것은, 연속으로 세 계단을 올라가지 못한다는 것이다. 완전탐색으로 모든 경우의 수를 따지면 좋겠지만, 시간 초과가 난다. DP로 해결해야 한다. 세 계
19.[백준] 1976 여행 가자 [java]
https://www.acmicpc.net/problem/1976연결 그래프를 탐색하면서 해당 그래프 안에 도시가 모두 포함되는지 확인하면 되는 문제이다. 쉽다고 생각해서 그냥 풀었으나, 생각하지 못한 반례때문에 이렇게 되었다. 이 실수를 반복하지 않기 위해
20.[백준] 2225 합분해 [java]
https://www.acmicpc.net/problem/22250부터 n까지 k개를 뽑아 n을 만드는 경우의 수를 구하는 문제이다. 순열을 이용하여 완전탐색으로 풀면 최대 200P200 -> 무조건 시간초과 DP로 해결해야 한다. k = 1일 때, 숫자 한개
21.[백준] 13335 트럭 [java]
https://www.acmicpc.net/problem/13335다리를 큐라고 생각한다. 다리에 트럭이 올라갈 수 있으면 트럭의 무게를 큐에 저장한다. (트럭이 다리에 올라감)다리에 트럭이 올라갈 수 없으면 0을 큐에 저장한다. (무게가 0인 트럭을 다리에
22.[백준] 1520 내리막 길 [java]
https://www.acmicpc.net/problem/1520dp 배열 "현재 위치까지 오는 경우의 수" 를 저장하기로 하고현재 위치에서 갈 수 있는 위치를 탐색하며 dp 배열을 갱신하려 했는데, 생각해보니까 이미 탐색한 위치를 다시 탐색을 안하는 것도 아
23.[백준] 2096 내려가기 [java]
https://www.acmicpc.net/problem/2096위 그림의 규칙으로 밑으로 내려가면서 최소 , 최대 비용을 저장하는 것인데, BFS + dp로 풀면 메모리 초과가 난다. 따라서, 슬라이딩 윈도우로 풀었다. 현재까지의 최대, 최소를 저장하는 배열