본문 바로가기

분류 전체보기

 (49)
[STL] Map STL map map은 key, value 페어로 이루어진 자료 구조입니다. Key에 대한 중복이 없습니다. 레드블랙 트리(Red-Black Tree 이하 RB Tree) 기반으로 되어있기 때문에 모든 데이터는 정렬되어 저장됩니다. 빠른 검색 속도를 가집니다. ( $ O(\log(N)) $ ) 인덱스가 따로 존재하지 않기 때문에 iterator를 사용합니다. 선언 map : key와 value를 pair 형태로 선언합니다. Method begin(): beginning iterator를 반환 end(): end iterator를 반환 insert(make_pair(key,value): 맵에 원소를 pair 형태로 추가 erase(key): 맵에서 key(키값)에 해당하는 원소 삭제 clear(): 맵의 ..
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..
[DP] Knapsack problem Knapsack Problem 도둑이 박물관에 침입했습니다. 멋진 그림, 조각품, 보석이 사방에 있습니다. 도둑은 이러한 물건의 가치를 잘 알고 있으며, 각각 이 진귀한 물건들이 시장에서 수백 또는 수천 달러에 거래 되는 것도 잘 알고 있습니다. 그러나 도둑은 현장에 배낭 하나만 가져 왔고, 가방의 수용량 만큼만 가지고 나갈 수 있습니다. 도둑은 가치를 극대화하기 위해 어떤 품목을 가져 가야합니까? 문제에는 두가지 버전이 있습니다. 1. Fraction knapsack problem 2. 0-1 knapsack problem 차이점은 보물을 가루로 만들어 일부만 취할 수 있는지 없는지 여부입니다. 1번의 경우에는 그리디 알고리즘으로 간단하게 해결이 가능합니다. 각 항목에 대해 파운드당 가치를 계산합니다...
최대공약수, 최소공배수, 소인수분해 1. 소인수분해 소수를 모두 구해서 나눠보는 것 보단 2부터 차례대로 나눠 나머지를 확인하는 것이 더 효율적이다. 왜냐하면 결국 2, 3, 5 등의 소수로 나눠떨어지지 않는다면 그들의 배수인 4, 6, 10.. 등으로도 나눠떨어지지 않을 것이기 때문에 항상 나누는 수가 소수일 때 먼저 나눠떨어지는 효과를 갖기 때문이다. 예를 들어, 24라는 수를 소인수분해하려면 우선 2로 나눠본다. 24 % 2 = 0 나눠떨어지므로 나눗셈의 결과값(몫)인 12를 다시 2로 나눈다. 12 % 2 = 0 나눠떨어지므로 나눗셈의 결과값(몫)인 6을 다시 2로 나눈다. 6 % 2 = 0 나눠떨어지므로 나눗셈의 결과값(몫)인 3을 다시 2로 나눈다. 3 % 2 = 1 나눠떨어지지 않으므로 3으로 다시 나눈다. 3 % 3 = 0 ..
7576. 토마토 문제 철수의 토마토 농장에서는 토마토를 보관하는 큰 창고를 가지고 있다. 토마토는 아래의 그림과 같이 격자 모양 상자의 칸에 하나씩 넣어서 창고에 보관한다. 창고에 보관되는 토마토들 중에는 잘 익은 것도 있지만, 아직 익지 않은 토마토들도 있을 수 있다. 보관 후 하루가 지나면, 익은 토마토들의 인접한 곳에 있는 익지 않은 토마토들은 익은 토마토의 영향을 받아 익게 된다. 하나의 토마토의 인접한 곳은 왼쪽, 오른쪽, 앞, 뒤 네 방향에 있는 토마토를 의미한다. 대각선 방향에 있는 토마토들에게는 영향을 주지 못하며, 토마토가 혼자 저절로 익는 경우는 없다고 가정한다. 철수는 창고에 보관된 토마토들이 며칠이 지나면 다 익게 되는지, 그 최소 일수를 알고 싶어 한다. 토마토를 창고에 보관하는 격자모양의 상자들..
[DP] Multiply Chain Matrix Algorithm Multiply Chain Matrix Algorithm MCM algorithm이란? 두 개 이상의 행렬을 곱할 때, 곱하기 연산을 최소로 할 수 있게 적절히 계산 순서를 바꿔주는 문제이다. 행렬의 곱셈은 다음과 같이 결합법칙이 성립된다. A x B x C = (A x B) x C = A x (B x C) 하지만 행렬을 곱하는 순서에 따라 곱하는 횟수가 달라지게 된다. 예를 들어, A = 20 x 1, B = 1 x 30, C = 30 x 10, D = 10 x 10 의 크기를 가진 행렬들이 있다고 가정하자 A x B x C x D의 값을 구하려면 적절히 괄호를 쳐서 아래와 같은 경우의 수를 만들 수 있다. ((A x B) x C ) x D) = (20 x 1 x 30) + (20 x 30 x 10) ..
PS 일반론 PS 일반론 문제해결 프로세스 I. 문제를 읽고 요구하는 바를 명확히 이해해야합니다. 즉, 어떤 인풋을 받아 어떤 아웃풋을 내야하는지 정확히 이해해야합니다. Ex) 백준 10872번: 팩토리얼 N이라는 인풋을 받았을 때, N!의 값을 출력하면 되는구나 라고 명확하게 이해해야합니다. 위의 문제는 비교적 짧고 간단하기 때문에 실수하지 않겠지만 문제가 복잡해질수록 실수하기 쉬우므로 항상 문제에 대한 정확한 이해가 가장 중요합니다. II. 요구하는 바를 어떻게 해결할지 자신만의 알고리즘을 설계 합니다. 아웃풋을 내기 위해 어떻게 해야할지 고민하는 과정입니다. 이 과정에서 알고리즘은 우리가 배워야만 아는 BFS, DFS 같은 알고리즘일 수 있고, 단순히 구현일 수도 있습니다. 위 팩토리얼 문제의 경우 재귀(rec..
11729. 하노이 탑 이동 순서 11729. 하노이 탑 이동 순서 PS 일반론에서 제시했던 방법으로 문제를 한번 풀어보고자 한다. 나는 이 문제를 재귀에 대해 어렴풋이 알고 있지만 정확히 어떻게 동작하는지 모르는 사람들을 위해 가장 최적화된 문제라고 생각한다. 내가 그랬고, 재귀에 대해 정확히 이해하고 있지 못하면 문제에 대한 접근조차 쉽지 않기 때문이다. 1. 문제를 읽고 요구하는 바를 명확히 이해한다. 제약: 이때 원반을 옮기는 몇 가지 조건이 따른다. 한 번에 움직일 수 있는 원반은 기둥 위에 놓인 원반 하나뿐이다. 어떤 원반 위에 그보다 더 큰 원반을 쌓을 수 없다. 입력: 원판의 갯수 N 출력: 최소이동횟수와 이동 순서의 출력 문제의 입력과 출력, 제약을 알았으니 이런 정보들을 보다 함수에 가깝게 정의해보는 것이 좋다. 원반의..

티스토리툴바