백엔드 개발자

그래프 최단 거리 알고리즘벨만 포드 알고리즘은 그래프 최단 거리를 구하는 알고리즘 중 하나이다.대표적으로 다익스트라 알고리즘은 모든 간선의 가중치가 양수일 때만 가능하다.다익스트라다익스트라가 어떻게 동작하는지 간단하게 살펴보자.이런 그래프가 있다고 가정한다. A에서 E까지의 최단거리를 구할 것이다.A에서 가능한 경로 중 가장 빠른 경로를 선택하여 이동할 것이다. A에서 B로 가는 경로가 선택되어 A에서 B까지의 경로는 최단 거리가 3인 것을 알 수 있다.이후 B에서 갈 수 있는 경로를 큐에 넣고 다시 탐색을 반복할 것이다. 이렇게 각 최단거리를 구하다 보면 E까지의 최단거리가 11이라는 것을 알 수 있다.그런데 이 방법은 모든 가중치가 양수일 때만 가능하다. 그림처럼 D에서 B로 가는 경로는 -100이기..

문제 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점수를 얻게 된다. 예를 들어 와 같이 시작점에서부터 첫 번째, 두 번째, 네 번째, 여섯 번째 계단을 밟아 도착점에 도달하면 총 점수는 10 + 20 + 25 + 20 = 75점이 된다. 계단 오르는 데는 다음과 같은 규칙이 있다. 계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 즉, 한 계단을 밟으면서 이어서 다음 계단이나, 다음 다음 계단으로 오를 수 있다. 연속된 세 개의 계단을 모두 밟아서는 안 된다. 단, 시작점은 계단에 포함되지 않는다. 마지막 도착 계단은 반드시 밟아야 한다. 따라서 첫 번째 계단을 ..

문제 수빈이는 TV를 보고 있다. 수빈이는 채널을 돌리려고 했지만, 버튼을 너무 세게 누르는 바람에, 일부 숫자 버튼이 고장났다. 리모컨에는 버튼이 0부터 9까지 숫자, +와 -가 있다. +를 누르면 현재 보고있는 채널에서 +1된 채널로 이동하고, -를 누르면 -1된 채널로 이동한다. 채널 0에서 -를 누른 경우에는 채널이 변하지 않고, 채널은 무한대 만큼 있다. 수빈이가 지금 이동하려고 하는 채널은 N이다. 어떤 버튼이 고장났는지 주어졌을 때, 채널 N으로 이동하기 위해서 버튼을 최소 몇 번 눌러야하는지 구하는 프로그램을 작성하시오. 수빈이가 지금 보고 있는 채널은 100번이다. 입력 첫째 줄에 수빈이가 이동하려고 하는 채널 N (0 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 고장난 버튼의 개..

문제 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 0초 후에 2*X의 위치로 이동하게 된다. 수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오. 입력 첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다. 출력 수빈이가 동생을 찾는 가장 빠른 시간을 출력한다. 시간 초과 -> 메모리 초과 -> 틀림 -> 맞음 순으로 되었다. 물..

유클리드 호제법 a 와 b의 최대공약수는 b와 (a%b)의 최대 공약수와 같다 (a>b 일 경우) ex) 12 와 8의 최대 공약수는 12나누기 8의 나머지 값인 4와 8의 최대 공약수와 같다. gcd(12,8) == gcd(8,12 mod 8 ) 확장 유클리드 호제법 전혀 어렵지 않다. 유클리드 호제법과 유사하다. 선형 방정식 ax + by = gcd(a,b) 일 경우 x와 y의 값을 구할 수 있다. 유클리드 호제법을 적용한다. 위 식에서 gcd(a,b) == gcd(b, a%b) == gcd(a%b , b%(a%b)) .......... 이런식으로 유클리드 호제법을 적용해주게 된다. 어떻게 예를 들어 a = 300, b = 200 일 때, 300x + 200y = gcd(300, 200) 이라 하면 ..