백준

https://www.acmicpc.net/problem/1931문제는 여러 회의 시간이 주어지고, 최대한 많은 회의가 진행할 수 있는 최대 회의의 수를 구하는 것이다. 이 때, 회의 시간이 시작 시간과 종료 시간이 같을 수도 있다.ex) 31 11 22 2

백준 2457이 문제는 회의실 배정 문제와 비슷한데, 비교해야할 대상이 4개로 나누어져 있어 비교하기 쉽게 만드는 것이 관건이다. 월과 일을 월에 100을 곱하고 일을 더함으로써 mmdd 형태로 만들면 비교하기가 편하다.그리고 문제에서 원하는 시작하는 날짜보다 빨리 피

백준 11501일단 이 문제는 최대로 얻을 수 있는 주식의 이익을 구하는 문제이다. 최대 이익을 얻기 위해서는 단순하게 고점보다 낮은 가격일 때, 다 사들여서 고점에 파는 주식 문제이다. 그럼 최고점이 나오기 전까지는 계속 주식을 사고 최고점이 나왔을 때, 주식을 다

백준 11000 이 문제는 회의실 배정 문제와 비슷한데, 그 문제에서는 하나의 회의실만을 정해두고 하나의 회의실에서 회의할 수 있는 최대의 회의 수를 구하는 것이라면 이 문제는 강의실의 개수와 상관없이 주어진 강의를 모두 할 수 있는 필요한 최소한의 강의실 수를 구하

백준 1744 이 문제는 수열이 주어졌을 때, 숫자들의 합의 최대값을 구하는 문제이다. 이 때, 수열에서 숫자 2개를 묶어서 곱할 수가 있다. 각 숫자는 한번만 묶을 수 있다. 숫자 두개를 묶어 곱할 때, 무조건 양수가 나와야 한다. 그리고 큰 숫자끼리 곱해야 최대

백준 15903 이 문제는 n번의 카드가 주어지고, 임의의 x번카드와 y번카드를 골라 둘에 쓰여있는 숫자를 더한 뒤, x번카드와 y번카드 위의 숫자에 덮어 쓴다. 이걸 m번 반복해서 나올 수 있는 n번 카드들에 쓰여있는 숫자들의 합의 최소를 구하는 문제이다. 우선순

백준 1700이 문제는 n개의 멀티탭 구멍이 있고, k개의 전기용품 순서가 있을 때 최소한으로 플러그를 뽑는 횟수를 구하는 문제이다.처음에 k개의 전기용품을 chk 배열을 둬서 n개의 구멍에 콘센트를 꽂는 것을 체크한다. 만약 n개의 구멍에 다 꽂혀 있다면 현재 꽂아

백준 11055이 문제는 n개의 수열이 주어졌을 때, 수열의 증가 부분 수열 중에서 합이 가장 큰 것을 구하는 문제이다.dpi는 i번째 인덱스를 포함하고, i번째 숫자가 가장 큰 증가 부분 수열의 최대합이다. 0부터 i보다 작은 인덱스까지 숫자를 비교해서 arri>ar

백준 11055n개의 수열이 주어졌을 때, 증가하는 부분 수열 중 가장 길이가 긴 수열의 길이를 구하는 문제이다.dpi는 i번째 인덱스 수를 포함하고, 그 수가 최대값인 증가하는 부분 수열 중에서 최대 길이이다.증가하는 수열을 만족하면 길이를 하나씩 더해가는 식이다.

백준 12852자연수 n이 주어졌을때, 주어진 규칙에 맞춰서 1로 만드는 횟수의 최솟값과 순서를 구하는 문제이다.dpi는 숫자 i가 1이 되는 횟수의 최솟값이다. 점차적으로 3부터 n까지 포문을 돌리면서 숫자들이 1이 되는 횟수의 최솟값을 구하면 된다. dpi=min(

백준 11659누적합(prefix sum)을 dp로 나타내서 구하는 문제dpi는 0부터 i번째 인덱스까지의 합

백준 2504'(' 이면 2를 곱한다'\[' 이면 3을 곱한다')' 이면 스택의 top이 '(' 일 때 닫아서 sum에 합하고 pop해주고, 스택이 비었다면 0을 호출하고 종료한다.']' 이면 스택의 top이 '\[' 일 때 닫고 sum에 합하고 pop해주고, 스택이

백준 7570이 문제는 번호가 주어진 학생들이 있을 때, 학생을 맨 앞이나 맨 뒤로 보냄으로써 번호순대로 만드는 최소의 값을 구하는 문제이다. 학생들의 번호들 중에 오른쪽으로 증가하는 방향이면서 연속되어 만들 수 있는 최댓값을 구해서 n에서 빼주면 답이 나온다.n이 백

백준 1697

백준 1926

백준 2178

백준 7576

백준 4179

백준 2206

백준 2573

백준 13549이 문제는 숨바꼭질1 문제와 달리 원래 거리에서 2배를 해서 0초 안에 갈 수 있다. 이 숨바꼭질 문제들은 이동하는 순서에 따라 답이 틀려지게 된다. 숨바꼭질1에서는 2배를 해서 갈 때, 1초가 걸린다. 그래서 n과 k에 0과 2가 입력 됐을 때, cur

백준 2075그냥 우선순위 큐에 다 넣고 하나씩 pop해서 제출하면 메모리 초과가 난다.어차피 찾는 수가 고정되어 있고 nxn 배열에서 두번째 행은 첫번째 행보다 무조건 크기 때문에 n개씩 우선순위 큐에 삽입하고 행끼리 계속해서 비교해주면 된다.

백준 13975백준 1715인 카드 정렬하기와 같은 문제 우선순위 큐에 모든 원소를 넣고 두개씩 빼서 더해주는 것을 우선순위 큐에 원소가 하나가 남을 때까지 반복하면 된다.

백준 1655이 문제는 고민해서 풀어도 여러번 틀려서 다른 분들의 풀이를 참고했다.최대힙과 최소힙인 두가지 우선순위 큐를 만들고 규칙 2가지에 맞춰서 원소를 삽입하고 최대힙의 top만 확인해주면 답이 된다.1\. 최대힙의 크기는 최소힙의 크기보다 같거나 하나 더 크다.

백준 1781데드라인을 첫번째 , 컵라면 수를 두번째 우선순위로 해서 오름차순으로 정렬한다. 그리고 그리디하게 매초마다 최대의 컵라면 수를 얻기 위한 선택을 하면 된다. 이 때 주의해야 할 점이 ex) 5 3 13 13 14 204 20=> 최대 컵라면을 얻기 위해서

백준 7785

백준 1620

백준 13414

백준 17219

백준 9375

백준 16165

백준 11478string 라이브러리에 있는s.substr(i,j) => i번째 인덱스부터 i+j-1인덱스까지 문자열

백준 19583시간이나 날짜 나오면 하나의 수로 표현=> ex) 12월 30일 => 12 100 + 30 => 1230 6시 42분 => 6 100 + 42 => 642

백준 20166일반적인 bfs 문제와 달리 왔던 곳을 다시 방문할 수 도 있기 때문에 vis 배열은 안둬도 되고, 중복된 문자열이 올 수 있기 때문에 map 을 이용해서 처리해야한다. 그냥 bfs로 풀게되면 최악의 경우 1000 10^2 8^5으로 시간초과가 된다.

백준 135110^12 이기 때문에 배열로는 메모이제이션 하기에는 불가능=> map을 이용처음에 bottom-up 방식으로 풀려고 했지만 메모리 초과가 났다top-bottom 방식으로 바꿔서 풀었다.

백준 7662set을 이용해서 풀었다.우선순위 큐를 최대힙과 최소힙 두개 준비해서 풀어도 된다.

백준 21939

백준 1202이 문제의 알고리즘은 다음과 같다.1\. 보석의 가격을 1순위로 해서 가격과 무게를 내림차순 정렬을 한다2\. set에 가방의 최대 무게들을 담는다. 3\. set의 lower_bound 함수를 이용해서 각 보석의 무게를 감당할 수 있는 최소한의 가방을 선

백준 23326set을 이용해서 i번 구역이 명소인 것만 set에 i를 넣음으로써 표시한다. 따로 현재 위치를 now라는 변수를 둬서 계속해서 기록해둔다. 3번에서는set의 lower_bound 함수를 이용해서 now라는 현재위치에 가장 가까운 명소의 i를 찾아준다.

백준 21944백준 21939 이 문제에서 recommend,recommend3가 추가된 형태이다.

백준 1920

백준 10816uppper_bound랑 lower_bound를 구현하는 문제

백준 18870vector의 중복된 원소를 제거할 때, unique 사용하면 편리unique 함수는 연속된 같은 숫자를 다 날려준다.unique 함수는 제거되지 않은 마지막 원소의 다음 원소의 iter 값이 반환됨 ( 필요 없는 값들의 첫 번째 원소의 iter)으로 e

백준 16401파라메트릭 서치 문제. 구하고자 하는 것(막자 과자의 최대 길이)을 고정으로 해서 역으로 이분탐색을 응용하면 된다.

백준 2295ai+aj+ak=at를 만족하는 at를 구하면 된다.그냥 구하면 N^3 으로 시간초과가 발생한다. 그럼 적어도 N^2logN으로 답을 도출해야 하는데, 이분탐색을 이용했다.ai+aj=at-ak의 식도 만족하므로 ai+aj를 따로 sum이라는 vector에

백준 2467두 수의 합이 0에 가까운 두 용액을 구하는 문제이다.ai+aj=0의 식은 ai=-aj이다. \-aj에 대한 lower_bound를 구한다. 구한 index에서 index-1 , index, index+1 중에 ai와의 합이 그나마 0에서 제일 가까운 값이

백준 2473백준 2467이나 백준 14921에서 약간 응용한 문제그 전의 문제와 달리 두 개의 용액이 아닌 세 개의 용액의 합이 0에 가까운 세 용액을 구하는 문제이다.이중포문으로 두 용액의 합을 구해서 그 합의 -sum 값에 lower_bound를 이용한다. 이 때

백준 3151n명의 학생들 중에 합이 0이 되는 3인 그룹을 만들 수 있는 경우의 수를 구하면 된다. 이 때 코딩 실력이 동일한 학생들도 따로 카운팅을 해줘야 함으로 upper_bound - lower_bound를 해주면 된다.

백준 74534 개의 배열에서 합이 0인 순서쌍을 구하는 문제이다.완전탐색으로 구하면 O(N^4)으로 시간초과이다. 그래서 배열 두 개를 미리 합해서 하나의 벡터에 다 넣어주고 정렬을 한다.나머지 두 개의 배열을 이중포문으로 돌리면서 미리 전처리 해둔 벡터에 이분탐색을

백준 1253

백준 2636n,m이 최대 100개라 최악의 경우를 고려해도 아마 O(N^2M^2) 정도.. 시간초과 날 일은 없다. 일단 치즈가 바깥치즈인지 확인하는 bfs를 돌리고 그 위치들을 따로 vis1이라는 배열에 기록한다.board에 녹은 치즈를 반영한다.1,2번을 반복하면

백준 920550m 당 맥주 한병씩 총 20병씩 박스에 담아둘 수 있으므로 총 1000m씩 갈 수 있다. 편의점에 가기만 하면 계속해서 20병씩 채워두면 되기 때문에 방문하는 곳마다 1000미터 이내에 편의점이 있으면 큐에 넣고 페스티벌에 도착할 수 있으면 끝내면 된다

백준 16953n이 최대 10억까지 가능 하기 때문에 vis 배열을 두기엔 불가능=> map을 이용! 메모리적으로 유리map 배열 대신 쓸 수 도 있음 (배열의 크기가 말도 안되게 클 때)

백준 2512파라메트릭 서치를 이용해서 풀었다. search 함수는 x가 배정된 예산들 중 최댓값일 때 나올 수 있는 총 예산이다. 요청한 모든 금액들의 합이 총예산보다 적을 경우 예외처리를 해줘야 한다.

백준 12015최장 증가 부분 수열 (LIS,Longest Increasing Subsequence)의 알고리즘은 두개가 있는데, 하나는 dp를 이용하는 방법이고 하나는 이분탐색을 이용하는 방법이다. n이 매우 클 때, 시간 복잡도를 개선하기 위해 후자의 방법을 사용하

백준 9935

백준 2638가장자리에 치즈가 놓이지 않아서 괜찮았던 문제bfs(0,0)을 돌려서 외부 공기층을 visi = 2로 만들고 치즈 상하좌우에 2가 2개이상 있는지 확인하면 끝나는 문제

백준 11003N이 최대 오백만개이기 때문에 적어도 NlogN으로 풀어야 시간초과가 나지 않는다. 그러기 위해서는 우선순위 큐를 이용한 풀이법이 필요하다.Di는 A(i-L+1) ~ Ai 까지의 최솟값을 도출해내야한다. i-l+1은 음수값이 나올 수 있지만 Di에 무조건

백준 1520그냥 dfs로 풀면 시간 초과가 발생한다. dp를 이용해 메모이제이션을 사용해서 시간을 줄여줘야 한다.이 때 visi이라는 dp 배열을 선언했다. 이 값은 (i,j) 좌표에서 (n-1,m-1) 좌표까지 도달 가능한 경로의 갯수이다. vis 배열을 모두 -1

백준 15486퇴사 1에서는 n이 크지 않아 재귀로 풀어도 됐지만 n이 최대 백오십만개이기 때문에 dp도 함께 이용해야 한다. 재귀로 풀려면 dp로 메모이제이션 사용해서 풀수도 있다. bottom-up 방식에서 dpi는 i번째 날까지의 최대 이익이다.첫 번째 날부터 일

백준 15686처음에 문제이해를 잘못해서 bfs로 풀다가 실패해서 다시 풀었던 문제조합을 사용해서 계산을 해주면 된다. ex) 치킨집 1, 2 ,3 이 있을 때, 최대 2개의 치킨집을 열 수 있다고 가정하면 1 개의 치킨 집을 열었을 때\-> {1}, {2} , {3}

백준 1043이 문제는 지민이가 과장된 이야기를 할 수 있는 파티의 갯수를 구하는 문제이다. 이 때 지민이의 이야기의 진실을 알고 있는 사람이 주어지고 각 파티에 어떤 사람들이 오는지가 번호로 주어진다.이 문제를 풀기 위해서는 결국 진실을 알고 있는 사람이 속한 파티들