목록분류 전체보기 (246)

영벨롭 개발 일지

[백준 BOJ][C++]2667번 단지번호붙이기: BFS/DFS

https://www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net BFS 알고리즘을 사용하여 1을 만나면 연결된 모든 1들을 모두 탐색 후, 다음 1을 찾아서 연결된 모든 1들을 탐색하는 과정을 반복하면 됩니다. BFS는 그래프를 탐색하는 과정에서 queue를 사용합니다. 이 문제에서 queue에 push 할 원소는 지도에서의 위치 좌표이기 때문에 편의를 위해 pair를 pp로 typedef 해주었습니다. map에서 '1'을 만나면 단지에 속하는 집의 수를 계산하..
알고리즘 문제 풀이/BOJ 2022. 2. 26. 16:52
[백준 BOJ][C++]2193번 이친수 풀이: DP

https://www.acmicpc.net/problem/2193 2193번: 이친수 0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다. 이친수는 0으로 시작하지 않 www.acmicpc.net 이 문제는 Dynamic Programming, DP를 이용하여 해결할 수 있습니다. 이친수 성질인 (1) 0으로 시작하지 않는다. (2) 1이 연속되지 않는다. 를 만족하는 dp를 설정하는 것은 간단합니다. dp[n][2]를 dp로 설정합니다. dp[n][0]은 n번째 자리에서 0이 올 수 있는 경우의 수, dp[n][1]은 n번째 자리에서 1이 올 수 있는 경우의 수를 나타냅니다. ..
알고리즘 문제 풀이/BOJ 2022. 2. 25. 22:57
[알고리즘]그래프 탐색하기: BFS & DFS

그래프의 특정 정점에서 시작하여 나머지 모든 정점을 방문하는 문제를 그래프 순회 문제(graph traversal problem)이라고 합니다. 그래프 순회 문제는 그래프에서 특정 정점을 찾기 위한 용도로 사용될 수 있기 때문에 그래프 탐색 문제(graph search problem)이라고도 합니다. 그래프 탐색에서 아직 방문하지 않은 노드들 중 다음으로 살펴볼 노드들의 리스트를 open list, 방문한 노드들의 리스트를 closed list라고 말합니다. 그래프 탐색 알고리즘으로 너비 우선 탐색(BFS, Breadth-First Search)와 깊이 우선 탐색(DFS, Depth-First Search)가 있습니다. 너비 우선 탐색(BFS, Breadth-First Search) BFS는 탐색 과정에..
CS/알고리즘 2022. 2. 25. 20:31
[백준 BOJ][C++]15990번 1, 2, 3 더하기 5: DP

https://www.acmicpc.net/problem/15990 15990번: 1, 2, 3 더하기 5 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 1,000,000,009로 나눈 나머지를 출력한다. www.acmicpc.net 이 문제는 Dynamic Programming, DP 알고리즘으로 해결할 수 있습니다. dp[n]은 숫자 n을 1, 2, 3의 합으로 나타낸 모든 경우의 수를 나타냅니다.(단, 같은 수가 연속 되면 안됨) 이 문제와 비슷한 문제인 9095번은 어떠한 조건도 없이 단지 1, 2, 3의 합으로 나타낸 모든 경우의 수를 찾으면 됩니다. (풀이: https://iridescent-zeal.tistory.com/19?category=1261302) 이때의 ..
알고리즘 문제 풀이/BOJ 2022. 2. 25. 16:28
[백준 BOJ][C++]11052번 카드 구매하기: DP

https://www.acmicpc.net/problem/11052 11052번: 카드 구매하기 첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000) www.acmicpc.net 이 문제는 Dynamic Programming, DP를 사용하여 해결할 수 있습니다. dp[n] 은 카드 n장을 만들기 위해 필요한 금액의 최댓값을 나타냅니다. 카드 i개가 포함된 팩의 가격 P[i]와 dp에 저장되어 있는 수들을 조합하여 해결할 수 있습니다. 그렇다면 dp[1]은 카드 1장을 만들기 위한 금액의 최댓값이므로 자동으로 P[1]이 되는 것이지요. 다음으로 dp[2]의 값은 어떻게 될까요? ..
알고리즘 문제 풀이/BOJ 2022. 2. 25. 14:00
[백준 BOJ][C++]11047번 동전 0 풀이: 그리디 알고리즘

https://www.acmicpc.net/problem/11047 11047번: 동전 0 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수) www.acmicpc.net 입력으로 주어지는 동전의 가치 Ai가 오름차순으로 주어졌음으로 제일 가치가 큰 동전부터 비교해가며 풀이를 진행하면 됩니다. 가치 k를 만들기 위해 필요한 동전의 수가 최소가 되기 위해선, 먼저 k보단 작은 수들 중에서 가장 큰 수를 뽑아 k를 나눈 몫이 그 동전의 개수를 의미합니다. 그 나머지는 남은 가치의 합을 나타내고 위 과정을 ..
알고리즘 문제 풀이/BOJ 2022. 2. 24. 21:51
이전 Prev 1 ··· 35 36 37 38 39 40 41 Next 다음