Heecheol's blog

문제 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..

문제 https://www.acmicpc.net/problem/2468 2468번: 안전 영역 재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 www.acmicpc.net 풀이 region 변수에 높이 정보를 담으면서 동시에 height라는 배열에도 입력값을 넣어주었다. 이후에 height에 Set을 씌워 중복을 제거하면 입력에 들어온 모든 높이를 배열에 담을 수 있다. 물이 잠기는 높이마다 영역이 얼마나 생길지는 다 확인해봐야 알 것 같았다. 그래서 위에서 구한 height의 원소별로 각각 영역을 구해주었다. 이후의 풀이는 다른 기본적인 bfs문제들과 동일하다. 일..