깊이 우선 탐색(DFS)6 [Programmers] 타겟 넘버 https://school.programmers.co.kr/learn/courses/30/lessons/43165 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 해결 과정 착안 주어지는 숫자들을 하나씩 순차적으로 더하거나 뺀 결과값을 구하는 재귀 함수를 만들어 문제를 해결한다. 구현 [스포 주의] 아래 '더보기'를 누르면 코드가 나오니 주의하세요~ 더보기 #include using namespace std; void Add(const vector& v, const int& t, int& cnt, int i, int sum) { if (i == v.s.. 2024. 1. 7. [Baekjoon] 1012번: 유기농 배추 https://www.acmicpc.net/problem/1012 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net 문제 해결 과정 착안 상하좌우로 연결된 배추들 사이에는 하나의 배추흰지렁이만 있어도 해충 예방이 가능하므로, 이를 표현하기 위해 편의상 아래와 같은 과정을 주어지는 배추밭 모양에 따라 반복적으로 수행하여 필요한 총 배추흰지렁이의 수를 계산한다. 배추가 심어진 땅이 발견되면 필요한 배추흰지렁이의 수를 1만큼 증가시킨다. 깊이 우선 탐색(depth-first search, DFS) 또는 너비 우선 탐색(bread.. 2023. 8. 24. [Baekjoon] 14500번: 테트로미노 https://www.acmicpc.net/problem/14500 14500번: 테트로미노 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변 www.acmicpc.net 문제 해결 과정 착안 표현 가능한 테트로미노의 경우의 수는 아래의 그림과 같이 총 19 가지이므로, 이에 대한 경우의 수를 모두 계산해봄으로써 문제를 해결하고자 하였다. 위와 같이 매우 다양한 테트로미노 케이스에 대해 일일이 계산하는 함수를 작성하여 문제를 해결하는 것은 비효율적이라고 판단하였다. 따라서, 어느 정도의 중복 계산을 허용하기로 하고 깊이 우선 탐색(depth-first search).. 2023. 7. 11. [Baekjoon] 1260번: DFS와 BFS https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 문제 해결 과정 착안 문제에서 주어지는 간선 정보를 바탕으로 깊이 우선 탐색(depth-first search, DFS)과 너비 우선 탐색(breadth-first search, BFS) 알고리즘을 구현하는 것을 요구하는 문제이므로, 두 알고리즘의 특징에 유의하여 구현하고자 하였다. 깊이 우선 탐색 알고리즘은 스택(stack) 자료 구조를 활용하여 구현(또는 .. 2023. 5. 8. [Baekjoon] 2606번: 바이러스 https://www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어 www.acmicpc.net 문제 해결 과정 착안 문제를 보자마자 그래프 자료구조를 이용해 시작 정점으로부터 연결되어 있는 모든 정점을 순회하는 알고리즘인 깊이 우선 탐색 알고리즘(depth-first search, DFS), 또는 너비 우선 탐색 알고리즘(breadth-first search, BFS)을 이용해야할 것으로 판단되었다. 마침 지난 포스트에서 깊이 우선 탐색 알고리즘을 구현했었던 것을 활용(...)하여, 해당 코드를.. 2023. 5. 7. [Baekjoon] 24479번: 알고리즘 수업 - 깊이 우선 탐색 1 https://www.acmicpc.net/problem/24479 24479번: 알고리즘 수업 - 깊이 우선 탐색 1 첫째 줄에 정점의 수 N (5 ≤ N ≤ 100,000), 간선의 수 M (1 ≤ M ≤ 200,000), 시작 정점 R (1 ≤ R ≤ N)이 주어진다. 다음 M개 줄에 간선 정보 u v가 주어지며 정점 u와 정점 v의 가중치 1인 양 www.acmicpc.net 문제 해결 과정 착안 간선(edge)의 가중치가 모두 일정한 무향(undirected) 그래프(graph) 자료 구조에서의 깊이 우선 탐색 알고리즘을 구현하는 문제이므로, 간단한 그래프 클래스와 문제에서 요구하는 깊이 우선 탐색(depth-first search, DFS) 알고리즘을 구현하였다. 이때, 한 정점에 대한 간선의.. 2023. 5. 7. 이전 1 다음
