목록알고리즘 문제 풀이/BOJ (77)

영벨롭 개발 일지

[백준 BOJ][C++]10026번 적록색약 풀이: BFS/DFS

https://www.acmicpc.net/problem/10026 10026번: 적록색약 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록) www.acmicpc.net 이 문제는 BFS 알고리즘을 사용하여 해결할 수 있습니다. 먼저 init_visit() 함수와 all_visit() 함수는 각각 visit 배열을 0으로 초기화하는 함수와 모든 구역을 방문했는지를 체크하기 위한 함수입니다. 먼저 적록색약이 아닌 사람을 기준으로 탐색을 시작합니다. 모든 구역을 탐색해야지만 구역의 수를 알아낼 수 있겠죠? 그렇기 때문에 all_visit() 함수를 사용하여 모..
알고리즘 문제 풀이/BOJ 2022. 2. 27. 00:09
[백준 BOJ][C++]1012번 유기농 배추: BFS/DFS

https://www.acmicpc.net/problem/1012 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net 이 문제는 BFS 또는 DFS로 해결할 수 있습니다. 먼저 배추밭을 나타낼 2차원 배열 map[][]과 각 배추의 방문 표시할 2차원 배열 visit[][]을 n*m 사이즈로 0으로 초기화 합니다. 각 테스트 케이스마다 배추밭의 모양이 달라지기 때문입니다. 이 과정을 init()이라는 함수를 따로 정의하여 테스트 케이스마다 호출하겠습니다. k개의 배추의 위치를 입력 받으면 map에서 해당 위치에 해당하는 원소..
알고리즘 문제 풀이/BOJ 2022. 2. 26. 23:05
[백준 BOJ][C++]2606번 바이러스 풀이: BFS/DFS

https://www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어 www.acmicpc.net 첫 번째 입력은 그래프의 노드 수, 두 번째 입력은 그래프의 엣지 수를 의미합니다. 그 다음 입력으로 엣지 수 만큼의 연결된 두 노드가 주어집니다. 처음 문제를 접했을 때, 엣지 정보를 저장하는 2차원 배열을 선언하고 이를 바탕으로 인접리스트로 전체 그래프를 만들었으나 틀렸습니다 ㅠㅠ 아마 시간이 너무 걸린듯 합니다. 때문에 두 노드 u, v 입력이 주어지면 그래프 g[u][v]와 g[v][u]를 1로..
알고리즘 문제 풀이/BOJ 2022. 2. 26. 17:53
[백준 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
[백준 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
이전 Prev 1 ··· 8 9 10 11 12 13 Next 다음