boj

[백준 8980] 택배 C++

8980번: 택배 입력의 첫 줄은 마을 수 N과 트럭의 용량 C가 빈칸을 사이에 두고 주어진다. N은 2이상 2,000이하 정수이고, C는 1이상 10,000이하 정수이다. 다음 줄에, 보내는 박스 정보의 개수 M이 주어진다. M은 1이 www.acmicpc.net 그리디 | 정렬 1. 문제 해결 아이디어 [백준 1700] 멀티탭 스케줄링 C++ 1700번: 멀티탭 스케줄링 기숙사에서 살고 있는 준규는 한 개의 멀티탭을 이용하고 있다. 준규는 키보드, 헤어드라이기, 핸드폰 충전기, 디지털 카메라 충전기 등 여러 개의 전기용품을 사용하면 hyeo-noo.tistory.com 위 문제와 비슷한 느낌이다. 미래에 배송될 정보들을 모두 알고 있으므로 마을에 도착해서 박스를 받을 때마다, 먼저 도착하는 마을에 배..

[백준 1167] 트리의 지름 C++

1167번: 트리의 지름 트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. 정점 번호는 1부터 V까지 www.acmicpc.net 트리, DFS 약 7개월 전에 자료구조 수업에서 트리를 공부하고 풀어보려고 시도했었지만 실패했었던 문제 알고리즘 수업에서 트리의 지름을 구하는 '머리끄댕이' 알고리즘을 배우고 이 문제가 생각나서 적용해서 풀어보았더니 바로 풀림! 1. 문제 해결 아이디어 트리의 지름을 구하기 위한 ㅈㅎㄱ 교수님의 '머리끄댕이' 알고리즘을 알아보자 이러한 트리가 존재하고 지름을 구하기 위해 쭉 늘려보았다 여기서 X는 트리에 있는 임의의 정점이다. X를 잡고 쭉 늘어..

[백준 1328] 고층 빌딩 C++

1328번: 고층 빌딩 상근이가 살고있는 동네에는 빌딩 N개가 한 줄로 세워져 있다. 모든 빌딩의 높이는 1보다 크거나 같고, N보다 작거나 같으며, 같은 높이를 가지는 빌딩은 없다. 상근이는 학교 가는 길에 가장 왼 www.acmicpc.net 다이나믹 프로그래밍 1. 문제 해결 아이디어 일반적인 dp문제는 작은 부분 문제들을 해결하면서 큰 문제의 답을 찾는 느낌인데 이 문제는 조금 다른 느낌이다. (도저히 안 풀려서 힌트를 얻었다) 일단 dp배열은 dp[최대 높이][왼쪽에서 보이는 건물 수][오른쪽에서 보이는 건물 수] 이렇게 설정했다. dp배열을 정해주는 건 어렵지 않았다. 그리고 bottom up 방식으로 푸는 게 좋을 것 같다는 느낌이 크게 들었었다. 그런데 점화식을 도출하기가 정말 어려웠다. ..

[백준 4811] 알약 C++

4811번: 알약 입력은 최대 1000개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄이며, 병에 들어있는 약의 개수 N ≤ 30 가 주어진다. 입력의 마지막 줄에는 0이 하나 주어진다. www.acmicpc.net 다이나믹 프로그래밍 1. 문제 해결 아이디어 dp[한 조각 알약의 개수][반 조각 알약의 개수]를 통해서 메모이제이션을 해주면 쉽게 풀린다. 한 조각 알약이 0개라면 앞으로 반 조각을 먹는 경우밖에 없으므로 return 1을 하는 기저 조건이 된다. 재귀 함수 내부에서는 한 조각 알약의 개수가 0보다 크면 한 조각을 빼고 반 조각을 추가해서 재귀 호출을 하고 마찬가지로 반 조각 알약의 개수가 0보다 크면 반 조각만 빼고 재귀호출을 하는 식으로 구현을 했다. 2. 코드 top d..

[백준 2240] 자두나무 C++

2240번: 자두나무 자두는 자두를 좋아한다. 그래서 집에 자두나무를 심어두고, 여기서 열리는 자두를 먹고는 한다. 하지만 자두는 키가 작아서 자두를 따먹지는 못하고, 자두가 떨어질 때까지 기다린 다음에 떨어 www.acmicpc.net 다이나믹 프로그래밍 1. 문제해결 아이디어 cnt초가 지났고, s번 움직였고, 사람 자두가 loc에 있을 때의 최댓값을 메모이제이션 해주었다. 사람의 위치가 그대로 라면 cnt가 T가 되기 전까지 진행이 가능하다. 사람의 위치를 바꾼다면 s가 W가 되기 전까지 위치를 바꿀 수 있다. 현재 위치에 따라서 자두를 먹는지, 못 먹는지를 판단해서 결과에 1을 더할지 말지를 결정한다. 2. 코드 top-down 방식으로 구현 1 2 3 4 5 6 7 8 9 10 11 12 13 ..

[백준 14442] 벽 부수고 이동하기2 C++

14442번: 벽 부수고 이동하기 2 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000), K(1 ≤ K ≤ 10)이 주어진다. 다음 N개의 줄에 M개의 숫자로 맵이 주어진다. (1, 1)과 (N, M)은 항상 0이라고 가정하자. www.acmicpc.net BFS 1. 문제해결 아이디어 매번 칸을 이동할 때마다 지금까지 몇 개의 벽을 부쉈는지 정보를 가지고 있어야한다. struct P를 만들고 해당 객체를 queue에서 가지고 다니게 하였다. 가장 중요한 visited배열이다. visited[r][c][k] = 1 : r, c를 방문할 때 총 k번 벽을 부수고 방문했음을 의미한다. 만약 다음 좌표가 3, 5이고 지금까지 부순 벽이 2개라면 visited[3][5][3]이 0인지 확..

[백준 1007] 벡터 매칭 C++

1007번: 벡터 매칭 평면 상에 N개의 점이 찍혀있고, 그 점을 집합 P라고 하자. 집합 P의 벡터 매칭은 벡터의 집합인데, 모든 벡터는 집합 P의 한 점에서 시작해서, 또 다른 점에서 끝나는 벡터의 집합이다. 또, P에 속 www.acmicpc.net 브루트 포스 1. 문제해결 아이디어 처음에 단순히 최대 20개의 점 중에서 2개씩 묶어 나가는 방법으로 풀려고 했다. 위 방법대로 하면 O(20 * 18 * ... * 4 * 2) 같은 끔찍한 시간복잡도가 나와 불가능함을 알 수 있었다. v1, v2 이라는 벡터가 있다고 가정해보자 v1 + v2 = = 이 된다. 여기서 알 수 있는점은 N개의 점 중에서, N/2개의 점은 시작점이 될 것이고, 나머지 N/2개의 점은 도착점이 되는 것을 알 수 있다. 따라..

[백준 1005] ACM Craft C++

1005번: ACM Craft 첫째 줄에는 테스트케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다. 첫째 줄에 건물의 개수 N 과 건물간의 건설순서규칙의 총 개수 K이 주어진다. (건물의 번호는 1번부 www.acmicpc.net 위상 정렬, 다이나믹 프로그래밍 1. 문제해결 아이디어 indegree를 활용한 위상 정렬을 하는 문제이다. 위 그림에서 각각의 phase는 다음 phase로 넘어가기위해 모두 해결해야하는 과제와도 같다. 예를 들어서 phase2에서 phase3로 넘어가려면 phase2에 있는 건물을 모두 건설해야 넘어갈 수 있다. 따라서 phase2에서 가장 오래걸리는 건물이 해당 phase에서 걸리는 시간이 되고, 이전 phase의 최대 시간만큼만 next phase의..

[백준 14939] 불 끄기 C++

14939번: 불 끄기 전구 100개가 10×10 정사각형 모양으로 늘어서 있다. 전구에 달린 스위치를 누르면 그 전구와 위, 아래, 왼쪽, 오른쪽에 있는 전구의 상태도 바뀐다. 전구 100개의 상태가 주어지면 모든 전구를 끄 www.acmicpc.net 그리디 알고리즘 1. 문제해결 아이디어 전구의 가장 윗 라인에서 스위치를 누르는 모든 경우(2^10=1024)를 시도해 본다. 그리고 두 번째 라인을 부터는 현재 열의 바로 윗 행의 전구가 켜져있는지 꺼져있는지에 따라서 스위치를 누를지 말지가 결정된다. 만약 바로 윗 행의 전구가 켜져있는데 현재 열의 스위치를 누르지 않는다면 앞으로 윗 행의 전구를 끌 방법은 없기 때문이다.(방향 : 왼쪽 상단부터 오른쪽 하단) 이렇게 하면 1~9 행은 모든 전구가 꺼질..

[백준 2011] 암호코드 C++

2011번: 암호코드 나올 수 있는 해석의 가짓수를 구하시오. 정답이 매우 클 수 있으므로, 1000000으로 나눈 나머지를 출력한다. 암호가 잘못되어 암호를 해석할 수 없는 경우에는 0을 출력한다. www.acmicpc.net 다이나믹 프로그래밍 1. 문제해결 아이디어 현재 자릿수에서 어떤 암호가 만들어 질 수 있는지 dp를 이용해서 해결해야한다. 우선 0은 암호로 바꿀 수 없다. 하지만 0 이전에 1 또는 2가 있다면 암호로 바뀔 수 있다. 숫자 3 이상과 이어지는 암호는 없다. 현재 숫자가 2인 경우 다음 숫자가 0 ~ 6 인 경우만 숫자 2개를 사용해서 암호를 만들 수 있다. dp배열 : dp[i][2] -> i번 자리수 이후로 숫자를 1개 또는 2개를 사용해서 만들 수 있는 경우를 저장하는 배열..