본문 바로가기

프로그래머스lv263

[프로그래머스 lv2] 하노이의 탑 풀이 ✅ 프로그래머스의 모든 문제와 해설 보기[클릭] 해설 n개의 원판들을 1번 기둥에서 3번 기둥으로 옮기는 하노이 문제이다. 처음 하노이 문제를 보는 사람이라면 규칙을 찾아서 절차적으로 해결하려고 노력하게 된다. 하지만 절차적으로 생각하면 할 수록 더욱 미궁 속으로 빠지게 되고... 이 문제는 재귀의 가장 대표적인 유형으로 재귀적 사고를 통해 해결해야 한다. func(int n, int f, int t)는 n개의 원판을 f 기둥에서 t 기둥으로 옮길 때 필요한 이동 방법을 리턴한다. 원판을 옮길 때 큰 원판은 절대 작은 원판보다 먼저 움직일 수 없다. 따라서, n개의 원판을 f에서 t로 옮기려면, n-1개까지의 원판을 f, t가 아닌 다른 기둥에 옮겨놓고 가장 마지막에 있는 n번째 원판을 f에서 t로 이동.. 2022. 8. 17.
[프로그래머스 lv2] 큰 수 만들기 풀이 ✅ 프로그래머스의 모든 문제와 해설 보기[클릭] 해설 숫자의 순서를 유지하면서 k개의 수를 제거했을 때 얻을 수 있는 가장 큰 숫자를 구하는 문제이다. numbers 길이에서 k개를 선택하는 모든 경우의 수를 탐색하면 TLE가 발생할 것이 분명하므로 더 간단한 풀이를 찾아야 한다. 어떻게 해결하면 좋을까 하다가 이런 생각이 들었다. "만약, 앞에 있는 수가 현재 수보다 작으면 앞에 있는 수를 제거해서 한자리씩 앞으로 당기는 것이 더 큰 수를 구하는 방법이지 않을까?" 예를 들어, 17725.... 가 있다고 했을 때 7은 1보다 크고, 1을 제거해서 7을 앞당기는 것이 가장 큰 수를 만드는데 유리하다. 해서, 숫자의 각 자리를 순회하면서 스택에 넣되, 스택에 이미 들어있는 수 중에서 현재 스택에 넣으려고.. 2022. 8. 17.
[프로그래머스 lv2] 숫자의 표현 풀이 ✅ 프로그래머스의 모든 문제와 해설 보기[클릭] 해설 연속된 숫자들의 합이 n이 되는 경우의 수를 구하는 문제이다. 결론적으로, (n-i*(i-1)/2)%i == 0 && (n-i*(i-1)/2)/i > 0 이면 연속된 i개 수의 합이 n이 되는데, 해당 수식의 도출과정을 살펴보자. i개의 연속된 수의 합이 n이 된다는 것을 다음과 같이 표현할 수 있다. x + (x+1) + (x+2) ... (x+i-1) = n 이를 정리해보면, 다음과 같다. i*x + (1+2+3+...+i-1) = n i*x + (i-1)*i/2 = n (등차수열의 합 공식) i*x = n-i*(i-1)/2 이 때, x가 존재하려면 n-i*(i-1)/2 를 i로 나눈 나머지가 0이어야 하고, 몫이 0보다 커야 한다. 따라서, (n.. 2022. 8. 17.
[프로그래머스 lv2] 피보나치 수 풀이 ✅ 프로그래머스의 모든 문제와 해설 보기[클릭] 해설 첫째항 f[0] = 0, 둘째항 f[1] = 1을 초기화 하고, 나머지항들은 f[i] = (f[i-2]+f[i-1])%1234567 로 구한다. n번쨰 항을 물어보고 있으므로 f[n]을 리턴하면 정답이다. 코드 #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; using ii = pair; using iii = tuple; #define X first #define Y second int solution(int n) { int.. 2022. 8. 17.
[프로그래머스 lv2] 게임 맵 최단거리 풀이 ✅ 프로그래머스의 모든 문제와 해설 보기[클릭] 해설 map이 있을 때, (0, 0)에서 (n-1, m-1) 까지의 최단 거리를 구하는 문제이다. BFS를 이용하여 탐색가능한 좌표를 따라 이동하고 최단거리를 구해보자. 먼저, 큐에 출발 위치 (0,0)을 삽입하고, dist[0][0]을 0으로 초기화 한다. dist[i][j]는 (0, 0)에서 (i, j)까지의 최단거리를 기록하는 배열로, 좌표를 방문하지 않은 경우 -1로 초기화되어있다. 이후, 큐에서 좌표를 하나씩 꺼내면서 이동가능한 좌표를 확인하고 새로운 좌표를 큐에 넣는다. 이동가능한 좌표는 현재 좌표의 동서남북에 있는 좌표 중, (0, 0) ~ (n-1, m-1) 내에 있고, 아직 방문한 적이 없으며, maps[i][j] 값이 1인 좌표이다. 새로.. 2022. 8. 17.
[프로그래머스 lv2] 타겟 넘버 풀이 ✅ 프로그래머스의 모든 문제와 해설 보기[클릭] 해설 DFS 유형으로 분류되어있지만, 결국 가능한 모든 부호에 대해 완전탐색을 하는 문제이므로 반복문으로 해결할 수 있다. numbers 의 길이가 n 일 때, 가능한 모든 부호 조합은 2^n 이다. (자리마다 +, - 중 하나 선택) n의 최대 입력 범위가 20이므로, 모든 부호 조합을 확인해도 TLE가 발생하지 않는다. 따라서 0부터 2^n-1 까지의 수를 n자리의 이진법으로 나타내면, n개의 자리에 대해 부호를 탐색할 수 있다. 이진법으로 나타내었을 때, 해당 자리가 1이면 + 부호를, 0이면 - 부호를 붙여 덧셈 결과를 구한다. 덧셈 결과가 target과 같을 때 cnt를 1 증가시키고, 최종 cnt 값을 리턴하면 정답이다. 코드 #include #.. 2022. 8. 17.
[프로그래머스 lv2] 최솟값 만들기 풀이 ✅ 프로그래머스의 모든 문제와 해설 보기[클릭] 해설 곲의 합이 최소이려면, 가장 큰수는 가장 작은 수와 곱해져야 한다. A는 오름차순, B는 내림차순으로 정렬한 뒤 일치하는 인덱스의 수끼리 곱하여 더하면 정답이다. 코드 #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; using ii = pair; using iii = tuple; #define X first #define Y second int solution(vector A, vector B) { sort(A.begin().. 2022. 8. 16.
[프로그래머스 lv2] 줄서는 방법 풀이 ✅ 프로그래머스의 모든 문제와 해설 보기[클릭] 해설 가장 먼저, next_permutation()이나 재귀 함수를 이용해서 모든 경우의 수를 탐색하고 K번째 순열을 리턴하는 방법이 떠오른다. 하지만, 이 방법으로 제출하면 효율성 테스트에서 TLE 가 발생한다. 규칙을 찾아 더 간단한 방법으로 문제를 해결해보자. 예를 들어, n = 4, k = 10 일 때 순열은 다음과 같다. [0 번째] 1 2 3 4 [1 번째] 1 2 4 3 [2 번째] 1 3 2 4 [3 번째] 1 3 4 2 [4 번째] 1 4 2 3 [5 번째] 1 4 3 2 ---------------------- [6 번째] 2 1 3 4 [7 번째] 2 1 4 3 [8 번째] 2 3 1 4 [9 번째] 2 3 4 1 [10번째] 2 4 1.. 2022. 8. 16.
[프로그래머스 lv2] 올바른 괄호 풀이 ✅ 프로그래머스의 모든 문제와 해설 보기[클릭] 해설 올바른 괄호 짝을 판별하는 문제는 스택 유형의 대표 문제이다. 문자열을 순회하면서 '('가 등장하면 이를 스택에 넣는다. ')'가 등장할 때, 스택이 비어있다면 짝이 맞는 '('가 없다는 뜻이므로 false를 리턴한다. ')'가 등장할 때, 스택이 비어있지 않다면 '('를 스택에서 하나 제거한다. '('와 ')'를 짝 맞춰 제거한 후, 최종적으로 스택이 비어있으면 true를 리턴한다. 코드 #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespa.. 2022. 8. 16.
[프로그래머스 lv2] 땅따먹기 풀이 ✅ 프로그래머스의 모든 문제와 해설 보기[클릭] 해설 가장 먼저 떠오르는 풀이는 모든 경우의 수에 대해 점수를 구하고, 이 중 최댓값을 리턴하는 방법이다. 그러나 해당 방법의 시간 복잡도를 계산해보면, 4^100000 정도로 시간 초과가 100% 발생한다. 완전탐색 풀이는 시간초과가 발생할 때, 한번쯤 dp(동적프로그래밍) 방법을 떠올려보면 좋다. dp[i][j]를 i번째 행, j번째 열에 도착할 떄까지의 최대 점수 라 정의하면, dp[i][j] = max(dp[i-1][k]) + land[i][j] (단, k는 0, 1, 2, 3 중 j가 아닌 수) 가 된다. max(dp[i-1][k])는 i-1 번째 행을 밟을 때까지 점수의 최댓값이다. 동일한 열은 두 번 연속 밟을 수 없다고 했으므로, i행, j열.. 2022. 8. 16.

티스토리툴바