알고리즘/문제풀이 - 프로그래머스

프로그래머스 레벨3 여행경로

문제 : https://programmers.co.kr/learn/courses/30/lessons/43164 서론 DFS+완전탐색+백트래킹을 이용해서 구현 풀이 이동가능한 모든 경로를 DFS+완전탐색으로 구현하는데, 현재 항공권의 도착지가 다음 항공권의 출발지와 같을 수 있도록 백트래킹을 추가 여행의 출발은 무조건 ICN이다. tickets중 출발지가 ICN을 찾아서 DFS를 시작한다. for (int i = 0; i < ticketNum; i++) { if (tickets[i][0].compare("ICN") == 0) { dfs(...); } } 현재 항공권의 도착지와 다음 항공권의 출발지가 같으며 아직 사용하지 않은 항공권일때 DFS를 이어간다. 항공권의 사용여부를 파악하는 이유는 예제2번의 ['..

2019. 11. 2. 12:50
알고리즘/문제풀이 - 백준

백준 2580 스도쿠

문제 : https://www.acmicpc.net/problem/2580 서론 정답이 여러개가 나오면 전부 출력을 하는 문제가 있었는데, 발견이 쉽지 않았다. 다른분들의 코드에서 'exit(0)'을 발견하고 알아낼 수 있었다. 풀이 이 문제는 DFS 문제다. 처음 만나는 0의 좌표에 1~9까지 각각 넣어보고 조건에 맞으면 두번째 만나는 0도 1~9까지 넣어보고 이를 반복하다가 마지막에 만나는 0도 1~9까지 중 하나를 넣었더니 답을 만족하면 출력한다. 만약 두번째 만나는 0을 1~9까지 전부 넣어봤는데 조건에 맞는게 없다면 첫번째 만난 0에서 값을 잘못 넣은 것이므로 리턴하는 방식이다. 조건은 3개가 주어지는데 셋 다 함수로 만들고 리턴값은 boolean으로 줬다. 세 함수의 리턴값이 전부 true면 ..

2019. 8. 28. 22:01
알고리즘/문제풀이 - 백준

백준 15652 N과 M (4)

문제 : https://www.acmicpc.net/problem/15652 풀이 N과 M (1), (2), (3) 문제를 합한다. N과 M (1) : https://hydroponicglass.tistory.com/64 N과 M (2) : https://hydroponicglass.tistory.com/65 N과 M (3) : https://hydroponicglass.tistory.com/66 (1)을 통해 전체적인 코드를 구현한다. (2)를 통해 내림차순인 수열은 제거한다. (3)을 통해 중복 수열도 출력하게 만든다. 구현 //c++ #pragma warning(disable:4996) #include #include int n, m; int visited[9]; int seq[9]; void df..

2019. 8. 28. 12:20
알고리즘/문제풀이 - 백준

백준 15651 N과 M (3)

문제 : https://www.acmicpc.net/problem/15651 서론 N과 M (1)번 문제에서 중복 되면 안되는 조건이 빠졌는데, 마찬가지로 코드에서도 중복조건을 주석처리하면 끝난다. 나와 다른 방향으로 푼 사람들을 위한건지 문제의 의도를 잘 모르겠다. 아이디어 N과 M (1)을 풀고 난 후 중복조건을 주석처리하면 된다. N과 M (1) : https://hydroponicglass.tistory.com/64 구현 //c++ #pragma warning(disable:4996) #include #include int n, m; int visited[9]; int seq[9]; void dfs(int value, int idx) { //std::cout

2019. 8. 28. 12:13
알고리즘/문제풀이 - 백준

백준 15650 N과 M (2)

문제 : https://www.acmicpc.net/problem/15650 풀이 N과 M (1)을 풀고 난 후 수정하면 된다. N과 M (1) : https://hydroponicglass.tistory.com/64 1번문제에서 수열을 오름차순으로 출력하라는 조건이 추가되었다. 만약 1 2 1 3 1 4 2 1 2 3 2 4 ... 로 출력되면 1 2 1 3 1 4 1 2 2 3 2 4 ... 로 바꿔줘야한다. 위에서 2 1을 1 2로 바꿔주면 기존에 이미 출력했던 1 2 와 중복된다. 오름차순으로 정렬하면 중복되는 수가 반드시 존재한다. 그러므로 내림차순으로 출력된다면 그냥 출력하지 않으면 되는 조건문을 추가해주면 된다. 구현 //c++ #pragma warning(disable:4996) #incl..

2019. 8. 28. 12:06
알고리즘/문제풀이 - 백준

백준 15649 N과 M (1)

문제 : https://www.acmicpc.net/problem/15649 서론 DFS와 백트래킹 문제 아이디어 n이 4이고 m이 2인 예제면 DFS를 이용해서 위 그림과 같이 모든 경우의 수를 출력하게 할 수 있다. DFS함수는 반복문으로 1~n의 값을 가지는 DFS를 불러오고 DFS를 불러올 때마다 우측으로 자리수를 한자리씩 옮기도록 인덱스를 1씩 증가시켜주면 된다. 그런데 문제에서 중복없이 출력하라는 조건을 줬기 떄문에 우측으로 인덱스가 증가할때마다 선택된 값은 방문처리해주고 만약 방문처리 된 값을 다시 접근하면 그대로 리턴시킨다. 구현 //c++ #pragma warning(disable:4996) #include #include int n, m; int visited[9]; int seq[9]..

2019. 8. 27. 16:50