문제풀이 (백준) (6) 썸네일형 리스트형 큰 수의 연산들 큰수의 연산 long long 범위를 넘어가는 수에 대해서 가끔 연산을 수행해야하는 경우가 있다. 이 경우 string을 통해 연산해야한다. 프로그래밍 대회나 문제풀이에서 가끔 보이니 익혀두는게 좋을 것 같아서 따로 정리해보려고 한다. 이 포스트에서는 반복적으로 수가 더해지거나 곱해져서 input이 커진 경우가 아닌 (이 경우는 다른 포스트에서 다룰 예정), 처음부터 long long 범위를 벗어나는 input에 대한 처리를 다룬다. 1. 덧셈 string addition (string a, string b) { string result; int flag_a = 0, flag_b = 0; if (a[0] == '-') flag_a = 1; if (b[0] == '-') flag_b = 1; if (fla.. 2579. 계단 오르기 문제 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점수를 얻게 된다. 예를 들어 와 같이 시작점에서부터 첫 번째, 두 번째, 네 번째, 여섯 번째 계단을 밟아 도착점에 도달하면 총 점수는 10 + 20 + 25 + 20 = 75점이 된다. 계단 오르는 데는 다음과 같은 규칙이 있다. 계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 즉, 한 계단을 밟으면서 이어서 다음 계단이나, 다음 다음 계단으로 오를 수 있다. 연속된 세 개의 계단을 모두 밟아서는 안 된다. 단, 시작점은 계단에 포함되지 않는다. 마지막 도착 계단은 반드시 밟아야 한다. 따라서 첫 번째 계단을 .. 1697. 숨바꼭질 문제 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다. 수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오. 입력 첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다. 출력 수빈이가 동생을 찾는 가장 빠른 시간을 출력한다. 예제 입력 5 17 예제 출력 4 힌트 수빈이가 5-10-9-18-1.. 7576. 토마토 문제 철수의 토마토 농장에서는 토마토를 보관하는 큰 창고를 가지고 있다. 토마토는 아래의 그림과 같이 격자 모양 상자의 칸에 하나씩 넣어서 창고에 보관한다. 창고에 보관되는 토마토들 중에는 잘 익은 것도 있지만, 아직 익지 않은 토마토들도 있을 수 있다. 보관 후 하루가 지나면, 익은 토마토들의 인접한 곳에 있는 익지 않은 토마토들은 익은 토마토의 영향을 받아 익게 된다. 하나의 토마토의 인접한 곳은 왼쪽, 오른쪽, 앞, 뒤 네 방향에 있는 토마토를 의미한다. 대각선 방향에 있는 토마토들에게는 영향을 주지 못하며, 토마토가 혼자 저절로 익는 경우는 없다고 가정한다. 철수는 창고에 보관된 토마토들이 며칠이 지나면 다 익게 되는지, 그 최소 일수를 알고 싶어 한다. 토마토를 창고에 보관하는 격자모양의 상자들.. PS 일반론 PS 일반론 문제해결 프로세스 I. 문제를 읽고 요구하는 바를 명확히 이해해야합니다. 즉, 어떤 인풋을 받아 어떤 아웃풋을 내야하는지 정확히 이해해야합니다. Ex) 백준 10872번: 팩토리얼 N이라는 인풋을 받았을 때, N!의 값을 출력하면 되는구나 라고 명확하게 이해해야합니다. 위의 문제는 비교적 짧고 간단하기 때문에 실수하지 않겠지만 문제가 복잡해질수록 실수하기 쉬우므로 항상 문제에 대한 정확한 이해가 가장 중요합니다. II. 요구하는 바를 어떻게 해결할지 자신만의 알고리즘을 설계 합니다. 아웃풋을 내기 위해 어떻게 해야할지 고민하는 과정입니다. 이 과정에서 알고리즘은 우리가 배워야만 아는 BFS, DFS 같은 알고리즘일 수 있고, 단순히 구현일 수도 있습니다. 위 팩토리얼 문제의 경우 재귀(rec.. 11729. 하노이 탑 이동 순서 11729. 하노이 탑 이동 순서 PS 일반론에서 제시했던 방법으로 문제를 한번 풀어보고자 한다. 나는 이 문제를 재귀에 대해 어렴풋이 알고 있지만 정확히 어떻게 동작하는지 모르는 사람들을 위해 가장 최적화된 문제라고 생각한다. 내가 그랬고, 재귀에 대해 정확히 이해하고 있지 못하면 문제에 대한 접근조차 쉽지 않기 때문이다. 1. 문제를 읽고 요구하는 바를 명확히 이해한다. 제약: 이때 원반을 옮기는 몇 가지 조건이 따른다. 한 번에 움직일 수 있는 원반은 기둥 위에 놓인 원반 하나뿐이다. 어떤 원반 위에 그보다 더 큰 원반을 쌓을 수 없다. 입력: 원판의 갯수 N 출력: 최소이동횟수와 이동 순서의 출력 문제의 입력과 출력, 제약을 알았으니 이런 정보들을 보다 함수에 가깝게 정의해보는 것이 좋다. 원반의.. 이전 1 다음