문제 풀이 프로그래머스 등굣길 문제입니다. 문제 출처 (1) 문제 파악 최단 경로의 개수를 구하는 문제입니다. (2) 문제 풀이 방법 생각하기 최단 경로 문제이며, 이동은 오른쪽 혹은 아래쪽으로 가능하니 DP를 활용해서 풀 수 있을 것 같은데요! 점화식은 [dp[i][j] = dp[i-1][j] + dp[i][j-1]] 로 세웠습니다. ...

문제 풀이 프로그래머스 석유 시추 문제입니다. 문제 출처 (1) 문제 파악 이어져 있는 석유의 개수를 파악하고 열에 걸쳐있는 석유를 모두 더했을 때 최댓값을 구하는 문제입니다. (2) 문제 풀이 방법 생각하기 가장 먼저 이어져있는 석유 칸의 개수가 몇 개씩인지 파악해야 합니다. -> 그래프 탐색 이후 모든 열을 돌며 최대 석유의 값을 ...

문제 풀이 백준의 20055번 문제입니다. 문제 출처 (1) 문제 파악 (2) 문제 풀이 방법 생각하기 구현 문제이므로 문제에 나온 순서대로 차근히 구현해주면 됩니다! [1] 로봇과 함께 회전하기 int temp = belt[2*N-1]; for(int i=2*N-1; i>0; i--) { belt[i] = belt[i-1];...

다익스트라란? 다익스트라 알고리즘은 최단 거리를 구하는 알고리즘입니다. 조건 다익스트라 알고리즘을 사용하여 문제를 풀기 위해서는 조건이 있습니다. 음수 가중치가 없어야 한다. 음수 가중치가 있는 그래프에서 최단 거리를 구하기 위해서는 벨만-포드 알고리즘을 사용하면 됩니다. 다익스트라 알고리즘 방식 그렇다면 어떻게 그래프의 최단 거리를 구...

문제 풀이 백준의 20529번 문제입니다. 문제 출처 (1) 문제 파악 (2) 문제 풀이 방법 생각하기 가장 먼저 떠오르는 방법은 완전 탐색입니다. 조합을 사용해서 3명씩 뽑은 후 심리적 거리를 계산하는 방법이죠! 그러나.. 거리를 계산하고자 하는 사람의 최대 인원 수는 10만명이기 때문에 시간 초과가 날 것이 분명합니다..! 그런데 잘 생...

문제 풀이 백준의 2630번 문제입니다. 문제 출처 (1) 문제 파악 (2) 문제 풀이 방법 생각하기 이 문제는 분할 정복을 사용해서 풀 수 있습니다. (큰 문제가 작은 문제로 쪼개지기 때문에 가능합니다!) 특정 사각형 범위가 모두 같은 색상인지를 확인하고, 다른 색이 섞여있다면 절반 사이즈의 사각형 4곳을 동일한 방식으로 조사하면 되는 것이...

중복 조합 조합은 n개의 숫자 중에서 r개를 뽑아야 할 때 순서를 고려하지 않고 뽑는 것을 말합니다. 오늘 살펴볼 중복 조합은 n개의 숫자 중에 중복을 신경쓰지 않고 r개를 뽑는 것을 뜻합니다. 구현 방법 그렇다면 이 중복 조합은 코드 상에서 어떻게 구현할 수 있을까요? 조합에서는 boolean[] vistied 를 사용해서 선택 여부에 대한 조...

조합 조합은 n개의 숫자 중에서 r개를 뽑아야 할 때 순서를 고려하지 않고 뽑는 것을 말합니다. 구현 방법 그렇다면 이 조합은 코드 상에서 어떻게 구현할 수 있을까요? 가장 중요한 포인트는 해당 인덱스의 숫자를 선택하냐, 안하냐의 두 가지가 경우가 존재한다는 것입니다! 백트래킹 백트래킹을 사용해서 조합을 구현할 때에는 start 변수를 사용합니다...

문제 풀이 백준의 9375번 문제입니다. 문제 출처 (1) 문제 파악 (2) 문제 풀이 방법 생각하기 이 문제에서는 옷의 종류마다 몇 개의 옷이 있는지 확인하는 것이 중요합니다. 같은 이름을 가진 옷은 없다고 했으니 중복 관련 처리는 신경쓰지 않아도 되겠네요! 예제를 통해 이해를 해보자면.. 옷의 종류는 headgear, eyewear 두 ...

문제 풀이 백준의 1074번 문제입니다. 문제 출처 (1) 문제 파악 (2) 문제 풀이 방법 생각하기 제일 간단하게 생각해보면 count를 하나씩 증가시키면 모든 map을 돌아 숫자를 넣어주면 됩니다. 하지만 N의 최대 값은 15이기 때문에 map의 사이즈는 최대 2^15 X 2^15가 되며 이 값은 1,1,073,741,824로 10억번을 넘...