문제 : 1577 도로의 개수유형 : DP풀이 : (i,j)에서의 경로의 수를 저장하면서 모든 경우의 수를 재귀적으로 구해준다. 메모이제이션이 없으면 시간초과가 난다. 갈 수 없는 경로는 set에 저장해뒀다가 경로 탐색할 때 확인한다. 주의할 점은 갈 수 없는 경로가

문제 : 2109 순회강연유형 : 그리디, 유니온 파인드풀이 : 다른 여러 그리디 문제들과 같이 강연으로 벌 수 있는 최대 비용을 먼저 가져가는 방식으로 풀이하였다.10775번 문제와 풀이가 동일코드

문제 : 1082 방 번호유형 : dfs, 메모이제이션, dp풀이 : 최대 2^50개 숫자를 선택하야 하는 경우가 있기 때문에 메모이제이션을 통한 시간 단축이 필수였고 50자리 숫자를 저장하기 위해 문자열로 관리하였다. 깊이(인덱스)와 남은 비용을 가지는 map을 이용

Travel Card 10456DP혼자힘으로 풀려고 하였지만 실패해서 풀이를 참조하였다. 어려운 dp문제였다고 생각한다.한번에 여러 티켓을 사용할 수 있고 꼭 7일 30일을 전부 채우지 않아도 티켓을 사용하는게 이득이라면 그렇게하는 것이 최소 비용을 찾을 수 있는 방법

이분탐색보통 냅색문제와는 다르게 dp로 풀 수 없는 범위가 주어져 있다. 최대 무게가 1^10이기 때문에 다른 풀이 방법이 필요했다.일단 가방에 넣을 수 있는 모든 경우의 수를 구해야하는데 2^30은 너무 큰 숫자가 나온다 그래서 반으로 나누어 각각 경우의 수를 전부

스택자료구조스택을 이용한 풀이는 항상 바로 안떠오르는 것 같다. 스택을 이용하면 쉽게 풀이할 수 있다.문제의 규칙은 p로 시작해서 p -> ppap로 바꾸는 과정에서 생기는 모든 문자열을 ppap문자열이라고 정의한다. p도 ppap 문자열입력 문자열을 처음부터 stac

구현각 좌표에 들어갈 숫자를 찾는 식을 얻어내면 더 빨리 풀 수 있겠지만 그냥 시뮬레이션으로 해도 된다고 생각해서 시뮬레이션으로 풀이하였다. 전체 크기가 10000x10000 이므로 전부 저장하기 보다는 출력해야하는 크기는 50x5 이기 때문에 그 부분만 저장하여 출력

DP메모이제이션이 필요한 dp문제였다. 일단 높이 오름 -> 가격 내림차순으로 정렬하고 시작하였다.테이블은 1차원으로 dpi는 i번째까지 최대 가격합으로 설정하였다. 점화식은 dpi(i번째까지 최대합)은 현재보다 높이가 S이상으로 낮은 물건의 인덱스들 중 가장 큰 값을

bfs단순 반복 bfs문제 같지만 R,C 범위가 크기 때문에 반복적으로 bfs를 돌리다 보면 메모리 초과나 시간 초과가 발생할 수 있다. 우선 2단계로 풀이가 나누어지는데 1단계는 백조끼리 서로 만날 수 있는지 체크하고 그 다음 물과 인접해있는 얼음을 녹이는 과정이 필

그리디정렬가방에 넣을 수 있는 보석 중에서 가격이 비싼 순서대로 가져가게 되면 총 가격의 최대값을 구할 수 있다. 보석의 가격 기준으로 내림차순하고 순회하면서 넣을 수 있는 가방이 있는지 확인하면 된다. 가방 크기를 벡터에 저장하고 사용하면 지우는 방식으로 하려고 하였

그리디주유소에 들리는 횟수를 최소화해야 하기 때문에 현재 연료로 갈 수 있는 주유소 중에서 최대한 멀리 또는 주유소를 갔을 때 연료가 가장 많아지는 경우 둘 중에 하나로 가야 최소가 되는 경우를 찾을 수 있을 것이라고 생각이 들었다.우선 현재 연료로 가장 멀리 간다고

백준 5557dfsDP단순 dfs로 풀이하면 시간 복잡도가 O(2^100)이므로 메모이제이션을 섞어서 풀이하여야 한다. 테이블 dpi를 i번째에서 값이 j일 때의 경우의 수로 설정하였다.값이 0이상 20이하 일 때만 재귀를 실행하면서 총 경우의 수를 구해준다. 총 경우

백준 2228DP일단 테이블(dpi)을 i개의 배열로 j개의 구간을 선택했을 때 최대 값이라고 설정하였다.그럼 dpi가 되는 경우는 i번째를 포함하지 않으면서 j개의 구간을 선택했을 때와 i번째를 포함하면서 j-1번째 구간이 i-2를 넘지 않는 경우 중 가장 큰 값을

백준 2212그리디생각의 전환이 필요했던 문제라고 생각한다. 일단 정렬 후 인접한 센서의 거리 차이를 전부 구하고 거기서 제일 큰 k-1개의 거리를 제거하면 정답을 얻을 수 있었다.만약 예제와 같이 k가 2이고 주어지는 센서의 위치가 1 6 9 3 6 7이라면 중복되는

백준 8980그리디트럭은 일직선으로 계속 이동하고 이전 마을을 다시 돌아가지 않기 때문에 받는 마을이 작은 순으로 정렬해서 배달할 수 있는 만큼 배달해야 최대로 많은 박스를 배송할 수 있다.먼저 받는 마을이 작은 순으로 정렬한 뒤 각 마을을 트럭의 최대 용량으로 초기화

백준 1781그리디유니온 파인드백준 10775번 문제와 거의 똑같은 문제였다. 이전에 풀어봤던 유형이지만 같은 풀이로 풀 수 있는 문제라고 바로 알아채지는 못했다. 조금 더 이런 유형의 문제풀이에 익숙해져야할 것 같다.먼저 컵라면 수를 기준으로 내림차순으로 정렬하고 각

백준 10254컨벡스 헐rotate calipers컨벡스 헐을 이용한 볼록껍질 구하기 문제를 풀어봐서 문제를 보자마자 그런류의 문제라는 느낌은 들었지만 그 이상은 접근할 수 없었다. O(n^2)으로 모든 정점의 거리를 비교하면 답을 찾을 수 있지만 n이 20만이기 때문

백준 16562유니온 파인드dfs정해는 유니온 파인드를 이용해서 푸는 것으로 보이지만 나는 dfs로 풀이하였다.일단 입력을 받고 친구관계를 양방향 그래프로 만들어 주었다. 그리고 1~n까지 for문으로 순회하면서 서로 연결된 친구들 중 비용이 가장 낮은 값을 받아와서

백준 9328BFS구현입력을 빈공간(.)로 둘러쌈현재 가지고 있는 열쇠로 열 수 있는 모든 문을 빈공간(.)으로 바꿈(0,0)에서 BFS 시작열쇠를 획득하면 큐에 모든 값을 빼고, 현재 좌표를 넣어서 다시 BFS 시작조건이 많기 때문에 큐에는 무조건 넣고 다음 좌표로

백준 2933구현bfs좌우 번갈아 가면서 미네랄을 없애고 없어진 미네랄 4방향을 순회하면서 바닥에 붙어 있지 않은 클러스터가 있으면 해당 클러스터를 한 칸 씩 내릴 수 있는지 확인하면서 이동시킨다.