-

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV14vXUqAGMCFAYD&categoryId=AV14vXUqAGMCFAYD&categoryType=CODE&&& SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com dfs 알고리즘을 활용한 완전탐색 문제다. 주어진 조건대로 0이거나 목적지인 3인 경우만 갈 수 있게 설정하고, 방문하지 않은 곳에 대해서만 방문하도록 했다. 문자 -> 숫자 변환은 '0'을 빼는 것이므로 47번째 줄에서 처리해주었다. 아래는 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 ..

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV15Khn6AN0CFAYD&categoryId=AV15Khn6AN0CFAYD&categoryType=CODE SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 조건이 붙은 완전탐색 문제다. dfs 알고리즘으로 풀 수 있다. 단, 단순히 뒤의 숫자가 앞의 숫자보다 같거나 큰 경우에 대해서 진행한다면 시간초과가 난다. 바꾼 뒤에 기준이 되는 베이스 포인트를 넘겨주고 2중 for문의 바깥 루프에서 이 값부터 기준으로 삼아 탐색을 하면 시간초과가 나지 않고 풀 수 있다. 아래는 전..

https://programmers.co.kr/learn/courses/30/lessons/43164 코딩테스트 연습 - 여행경로 | 프로그래머스 [[ICN, SFO], [ICN, ATL], [SFO, ATL], [ATL, ICN], [ATL,SFO]] [ICN, ATL, ICN, SFO, ATL, SFO] programmers.co.kr DFS유형의 문제다. 갈 수 있는 경로를 미리 정렬해서 오름차순의 경로를 반환하면 된다. 현재 경로를 저장하고 계속 가보면서 답을 구하면 된다. void형으로 하지 말고 bool 형으로 해서 했더니 segmentation fault가 나질 않았다. 스택 메모리의 크기에 주의해서 이렇게 bool 형으로 구현하는 방식도 연습이 필요하다. * 22번째줄은 삭제해도 전혀 지장..

https://programmers.co.kr/learn/courses/30/lessons/43165 코딩테스트 연습 - 타겟 넘버 | 프로그래머스 n개의 음이 아닌 정수가 있습니다. 이 수를 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다. -1+1+1+1+1 = 3 +1-1+1+1+1 = 3 +1+1-1+1+1 = 3 +1+1+1-1+1 = 3 +1+1+1+1-1 = 3 사용할 수 있는 숫자가 담긴 배열 numbers, 타겟 넘버 target이 매개변수로 주어질 때 숫자를 적절히 더하고 빼서 타겟 넘 programmers.co.kr 전형적인 DFS 문제다. 현재 인덱스의 숫자를 더한 것의 재귀와 현재 인..

https://www.acmicpc.net/problem/2210 2210번: 숫자판 점프 111111, 111112, 111121, 111211, 111212, 112111, 112121, 121111, 121112, 121211, 121212, 211111, 211121, 212111, 212121 이 가능한 경우들이다. www.acmicpc.net 백준 DFS 문제다. set 컨테이너를 활용해 풀면 쉽게 풀 수 있다. 갈 수 있는 방향으로 중복허용해 5번 이동하여 만들 수 있는 문자열의 개수를 출력하는 문제다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 3..

https://www.acmicpc.net/problem/2573 2573번: 빙산 첫 줄에는 이차원 배열의 행의 개수와 열의 개수를 나타내는 두 정수 N과 M이 한 개의 빈칸을 사이에 두고 주어진다. N과 M은 3 이상 300 이하이다. 그 다음 N개의 줄에는 각 줄마다 배열의 각 행을 나타내는 M개의 정수가 한 개의 빈 칸을 사이에 두고 주어진다. 각 칸에 들어가는 값은 0 이상 10 이하이다. 배열에서 빙산이 차지하는 칸의 개수, 즉, 1 이상의 정수가 들어가는 칸의 개수는 10,000 개 이하이다. 배열의 첫 번째 행과 열, 마지 www.acmicpc.net 정답률이 26%인 것에 비해서는 기다지 난이도가 있는 문제는 아니다. 이 문제는 시뮬레이션 + DFS 문제로 시간의 흐름에 따라 빙산을 녹여..

https://programmers.co.kr/learn/courses/30/lessons/42895?language=cpp 코딩테스트 연습 - N으로 표현 | 프로그래머스 programmers.co.kr DFS 완전탐색으로 풀 수 있는 문제다. 깊이가 최대 8이므로 충분히 시간 내에 탐색할 수 있다. 특이한 점은 19행 ~ 29행으로 5, 55, 555, 5555와 같은 수를 더하거나 빼거나 곱하거나 나눌 수 있다는 것이다. 이 때 해당하는 숫자 만큼 dfs count변수에 더해줘야 한다. 어느 dfs 문제와 동일하게 백트래킹에도 신경을 잘 써줘야 한다. 기본적으로 깊이 초과시 리턴, 답을 찾을 시 리턴하는 것과 더불어 0에 곱하거나 나누는 것을 하지 않도록 25,26행에 설정해주는 것이 필요하다. D..