Heecheol's blog

문제 https://www.acmicpc.net/problem/15652 15652번: N과 M (4) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 풀이 이 문제에서도 이전 문제와 같이 depth를 이용해 숫자의 개수를 count하여 출력하는 것은 동일하다(파라미터로 문자열을 받기 때문에). 다만, 이번 문제처럼 현재 숫자를 기준으로 이후의 숫자만 받아오기 위해서는 추가적인 파라미터가 필요하다고 생각했다. 그래서 num이라는 파라미터에 반복문의 i를 받아오도록 하였다. [4,2]의 경우에서 dfs("",0,1)로 시작하면 dfs("1 ..

문제 https://www.acmicpc.net/problem/15651 15651번: N과 M (3) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 풀이 시간초과가 나와서 놀랬다. 기존에 arr로 만들어서 문자열로 다시 변경한 뒤 출력하는 과정때문인 것 같아서 바로 문자열로 만들어서 출력하도록하였따. 이전 문제들에서 배열로 받던 arr를 current라는 문자열로 바꾼 뒤, 반복문의 i를 이용해서 문자열 뒤에 더해주는 식으로 구현했다. 아무튼 이번 문제에서는 input[1]만큼 수를 출력해주는 것은 같지만 중복이 허용되므로 check같..

문제 https://www.acmicpc.net/problem/15650 15650번: N과 M (2) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 풀이 N과 M(1)과 마찬가지로 기본적으로 DFS를 이용해 모든 경우를 구하는 것을 베이스로, 제시된 조건을 만족하는 경우만 출력하도록 하였다. 우선, depth를 매번 파라미터로 받지 않고 전역변수로 두었다. 물론 메모리를 더 쓰겠지만 매번 적어주지 않아도 됐다. 그래서 arr.count가 이 depth와 같다는 것은 arr의 원소의 수가 input[1]과 같다는 것이므로 바로 출력하고 ..

문제 https://www.acmicpc.net/problem/15649 15649번: N과 M (1) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 풀이 백트래킹의 대표 문제를 풀어보려고 했는데, 기존에 dfs라고 생각했던 코드와 동일하게 푸는 것을 보고 헷갈리기 시작했다. 백트래킹과 DFS 모두 탐색하는 알고리즘이지만, 백트래킹의 경우는 탐색을 하다가 조건에 맞지 않는다면 더 이상 탐색을 하지 않고 다시 돌아와 다른 노드를 탐색한다. DFS는 모든 경우를 탐색하기때문에 DFS를 이용해 모든 경우를 탐색하다가 불필요한 것들에 대해서는 ..

문제 https://www.acmicpc.net/problem/6593 6593번: 상범 빌딩 당신은 상범 빌딩에 갇히고 말았다. 여기서 탈출하는 가장 빠른 길은 무엇일까? 상범 빌딩은 각 변의 길이가 1인 정육면체(단위 정육면체)로 이루어져있다. 각 정육면체는 금으로 이루어져 있어 www.acmicpc.net 풀이 어렵지 않게 BFS로 풀었지만 갑자기 입력받는게 헷갈려서 시간이 좀 걸렸다... 2차원배열에서는 dx, dy로 상하좌우를 생각했지만 이번 문제는 층까지 있으므로 3차원으로 생각해야한다. 2차원배열일때의 풀이에서 dz만 추가하면 된다. 반복문을 통해 building에서 "S"를 찾고 위치를 큐에 넣어준다. 출발점이 하나이므로 "S"를 찾았다면 break를 통해 반복문을 탈출해준다. 이후에는 2..