profile
김동근
post-thumbnail

[백준 1577] 도로의 개수

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

2일 전
·
0개의 댓글
post-thumbnail

[백준 2109] 순회강연

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

2일 전
·
0개의 댓글
post-thumbnail

[백준 1082] 방 번호

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

2일 전
·
0개의 댓글
post-thumbnail

[백준 10456] Travel Card

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

2021년 2월 21일
·
0개의 댓글
post-thumbnail

[백준 1450] 냅색문제

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

2021년 2월 20일
·
0개의 댓글
post-thumbnail

[백준 16120] PPAP

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

2021년 2월 19일
·
0개의 댓글
post-thumbnail

[백준 1022] 소용돌이 예쁘게 출력하기

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

2021년 2월 19일
·
0개의 댓글
post-thumbnail

[백준 2515] 전시장

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

2021년 2월 18일
·
0개의 댓글
post-thumbnail

[백준 3197] 백조의 호수

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

2021년 2월 18일
·
0개의 댓글

[백준 1202] 보석 도둑

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

2021년 2월 17일
·
0개의 댓글

[백준 1826] 연료 채우기

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

2021년 2월 17일
·
0개의 댓글
post-thumbnail

[백준 5557] 1학년

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

2021년 2월 15일
·
0개의 댓글
post-thumbnail

[백준 2228] 구간 나누기

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

2021년 2월 15일
·
0개의 댓글
post-thumbnail

[백준 2212] 센서

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

2021년 2월 15일
·
0개의 댓글
post-thumbnail

[백준 8980] 택배

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

2021년 2월 15일
·
0개의 댓글
post-thumbnail

[백준 1781] 컵라면

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

2021년 2월 15일
·
0개의 댓글
post-thumbnail

[백준 10254] 고속도로

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

2021년 2월 15일
·
0개의 댓글
post-thumbnail

[백준 16562] 친구비

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

2021년 2월 15일
·
0개의 댓글
post-thumbnail

[백준 9328] 열쇠

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

2021년 2월 6일
·
0개의 댓글
post-thumbnail

[백준 2933] 미네랄

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

2021년 2월 6일
·
0개의 댓글