본문 바로가기

알고리즘106

[프로그래머스 lv2] 방문 길이 풀이 ✅ 프로그래머스의 모든 문제와 해설 보기[클릭] 해설 좌표를 이동시키면서, 중복되지 않은 이동경로의 개수를 세는 문제이다. 이동하며 특정 루트를 방문했었는지 확인하는 과정이 필요하다. 방문했던 좌표 (x, y)를 저장하는 vector나 set을 쓸 수도 있지만, 주어진 좌표평면의 크기가 작아 bool 타입의 배열을 선언하면 간단히 처리할 수 있다. 주어진 문자열을 순회하면서, U, D, L, R에 따라 새로운 이동 좌표를 구한다. 만약, 새 좌표가 주어진 범위를 넘어간다면 이를 무시하라고 했으므로 아무런 일도 없었던 것처럼 넘어간다. 새 좌표가 주어진 범위 내에 있을 때 좌표를 이동하고, 해당 경로를 방문한적이 없다면 cnt 변수를 1 증가시킨다. 모든 문자를 순회한 후 최종 cnt 값을 리턴하면 정답이.. 2022. 8. 10.
[프로그래머스 lv2] 기능개발 풀이 ✅ 프로그래머스의 모든 문제와 해설 보기[클릭] 해설 문제의 조건을 요약하면, 1. 각 기능들은 완성도가 100%가 되었을 떄 배포된다. 2. 배포는 주어진 순서대로 이루어진다. 즉, 뒤의 기능이 먼저 완성되었다 할지라도 앞에 있는 기능이 배포되지 않았다면 먼저 배포될 수 없다. 가장 먼저, 각 기능에 대하여 배포까지 며칠이 남았는지 구할 수 있다. progresses[i]가 현재까지 진행된 완성도, speeds[i]가 하루에 채워지는 완성도이므로 (100-progress[i])를 speeds[i]로 나눈 몫의 올림값이 배포까지 필요한 일수가 된다. n을 k로 나눈 결과를 올림한 값은 (n+k-1)/k로 구한다. (외워두면 가끔 유용하게 쓸 수 있다!) 따라서, 각 기능에 대하여 배포까지 남은 날은 (1.. 2022. 8. 9.
[프로그래머스 lv2] 124나라의 숫자 풀이 ✅ 프로그래머스의 모든 문제와 해설 보기[클릭] 해설 모든 숫자를 (1, 2, 4) 3가지 수로 나타낸다고 했으므로 3진법과 관련있음을 유추할 수 있다. 10진법을 3진법으로 나타내기 위해서는 3으로 계속 나누어가며 나머지가 무엇인지 살펴야 한다. 나머지가 1일 떄는 1, 나머지가 2일 때는 2, 나머지가 0일 떄는 4를 문자열에 붙이고 맨 마지막에 이를 뒤집어 결과를 리턴한다. 단 주의할 것은, 3으로 나누어떨어질 경우(나머지가 0일 경우) 몫을 1 감소시키고 나머지를 3 증가시켜 3을 4로 변환시키자. 예를 들어, 10을 1, 2, 4 숫자로 변환할 때 10 / 3 = 몫 3 ... 나머지 1 => 1 3 / 3 = 몫 1 ... 나머지 0 => 몫에 1을 뺴주면 나머지는 3이 된다. 나머지 3을 4.. 2022. 8. 9.
[프로그래머스 lv2] 멀쩡한 사각형 ✅ 프로그래머스의 모든 문제와 해설 보기[클릭] 해설 문제를 처음 딱 보고, 아 뭔가 규칙을 찾는 문제구나 하는 생각이 든다. h*w의 직사각형에서 대각선이 지나가는 칸 수를 알 수 있다면 전체 블럭의 개수에서 해당 칸의 개수를 빼 정답을 구할 수 있다. 그렇다면 대각선이 지나가는 칸 수는 어떻게 알 수 있을까? 예제로 나온 8*12의 직사각형을 보면, 일정한 패턴이 반복되는 것을 알 수 있다. 8과 12의 최대공약수 4로 가로와 세로를 각각 나누어보면 2*3의 직사각형이 나온다. 이 직사각형은 전체 직사각형 안에 최대공약수(4개) 만큼 반복된다. 이 작은 직사각형을 보면, 대각선이 지나는 칸의 개수는 2+3-1 = 4개가 된다. 즉, W*H 의 전체 직사각형이 있고, W와 H의 최대공약수를 g라 할 때.. 2022. 8. 9.
[백준 11727번] 2×n 타일링 2 풀이 문제  11727번: 2×n 타일링 22×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×17 직사각형을 채운 한가지 예이다.www.acmicpc.net 입력채워야 하는 직사각형의 가로 길이 N 출력2*N 직사각형을 1x2, 2x1, 2x2 타일로 채울 수 있는 방법의 수 풀이 방법DP[N] = 2*N 직사각형을 채울 수 있는 방법의 수로 놓고, 이를 작은 문제들로 나누어 동적 프로그래밍으로 풀이한다. 2*N 직사각형을 만드는(채우는) 방법은 3가지가 있다.1) 2*(N-1) 직사각형의 오른쪽에 2*1 크기의 타일을 한개 놓는 것  2) 2*(N-2) 직사각형의 오른쪽에 1*2 크기의 타일을 두개 놓는 것  3) 2*(N-2) 직사각형의 오.. 2021. 11. 18.
동적계획법(Dynamic Programming) 동적계획법에 대한 이해 피보나치 수열은 첫째항이 0, 둘째항이 1이고 이전 두항을 더해가며 새로운 항의 값을 구해나가는 수열이다. 0, 1, 1, 2, 3, 5, 8, 13 ... 과 같이 이어지며, 점화식은 다음과 같다. F(N) = F(N-1) + F(N-2) (N >= 2) F(0) = 0, F(1) = 1 N번째 항의 값을 구하는 문제는, N-1번째 항을 구하는 문제와 N-2번째 항을 구하는 문제로 나누어질 수 있다. 이렇게 큰 문제를 작은 문제로 나누어 풀 수 있는 경우를 최적 부분 구조(Optimal Structure) 라고 한다. 최적 부분 구조에 대해 자세히 말하면, 문제의 최적 해결 방법이 부분 문제에 대한 최적 해결 방법으로 구성되는 경우를 말한다. 최적 부분 구조를 가지는 피보나치 수.. 2021. 11. 17.

티스토리툴바