완전 탐색과 백트래킹을 활용한 기본 문제. https://www.acmicpc.net/problem/1182 1182번: 부분수열의 합 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net 사람 허파 뒤집는 문제였다..진심 부분 수열의 합 문제 풀이 Check point 1. 재귀함수를 사용하여 푸는 문제. 현재 인덱스에 있는 값을 더하는 경우와, 더하지 않고 다음 인덱스로 넘어가는 경우를 나누어 구현 2. 리스트 내의 숫자에 따라 모든 조합을 확인하지 않을 수 있으므로 depth == N 의 조건문을 넣..

https://school.programmers.co.kr/learn/courses/30/lessons/1844 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr DFS 문제 풀이 시 Check Point 1. 2차원 배열에서 최단 거리를 구해야하므로 dist[][]배열을 선언한다. 2. vector 형 배열은 vector.size()가 행, vector[0].size()가 열이다. 3. (1,1) 좌표에서 시작하지만 사실상 (0,0)에서부터 탐색을 시작하므로 dist[n-1][m-1] 을 확인해야한다. 4. 따라서 nx와 ny도 N,M과 동일하면 탐색하지않..

기존 문제인 숨바꼭질 문제와 유사하지만, 최단 시간에 도착한 경로의 개수를 찾아야된다는 점에서 차이가 있다. https://www.acmicpc.net/problem/12851 12851번: 숨바꼭질 2 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 www.acmicpc.net 따라서 해당 노드와 탐색 깊이를 모두 저장할 수 있는 pair 자료형 queue를 선언해 while loop를 실행한다. 최단 시간을 찾은 이후에도 계속해서 최단시간을 만족하는 경로를 추가해야하기때문에, Queue에 들어온 도착 노드가 최단 시간을 만족..

DFS 혹은 BFS 를 사용하여 풀 수 있는 간단한 문제. https://www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어 www.acmicpc.net BFS 를 사용한 풀이 #include #include #include using namespace std; const int MAX = 101; int N, M; int answer=0; vector network[MAX]; bool visited[MAX]; deque Q; int DFS(int v) { Q.push_back(v); visit..

DFS 혹은 BFS로 풀 수 있는 문제다. 비슷한 백준 문제로는 단지번호 붙이기(2667), 토마토(7576)가 있다. https://www.acmicpc.net/problem/1303 1303번: 전쟁 - 전투 첫째 줄에는 전쟁터의 가로 크기 N, 세로 크기 M(1 ≤ N, M ≤ 100)이 주어진다. 그 다음 두 번째 줄에서 M+1번째 줄에는 각각 (X, Y)에 있는 병사들의 옷색이 띄어쓰기 없이 주어진다. 모든 자리에는 www.acmicpc.net BFS/DFS문제에서 좌표에 관련된 문제를 풀이할 때 check point 해당 매트릭스를 저장할 인접 리스트(혹은 인접 행렬)을 선언할 것. 특정 좌표를 기점으로 주변을 탐색하는 문제의 경우 dx,dy 리스트를 선언할 것. 좌표를 저장하는 큐의 경우 자..

DFS를 사용하여 푸는 대표적인 문제중 하나. 순열 문제도 DFS를 사용하여 풀 수 있다는 것에 유의! 문제의 조건에 따라 케이스를 손으로 직접 쓰고, 눈에 보이는 규칙을 정리해서 그대로 코드로 구현하는 과정이 재밌다 :) 더보기 Check Point 1. DFS에서 재귀를 사용할 때의 기본 조건과, 배열 내 데이터를 삽입하고 삭제할때를 유의하여 코드를 구현한다. https://www.acmicpc.net/problem/15649 15649번: N과 M (1) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net #include #include..