Programming/BOJ277 [C/C++] 백준 #1940 주몽(두개의 포인터) 두개의 조합에 의해서 M인 값을 얼마나 많이 찾을 수 있는 가에 대한 문제입니다. 예를 들어서, 2 7 4 1 5 3 이라는 재료가 주어지고, 조합해서 만들어야 하는 갑옷이 9의 값을 가져야 한다면, 먼저 정렬을 수행합니다. 1 2 3 4 5 7 그러면 두개의 합을 왼쪽편과 오른쪽편을 이용해서 구해보도록 합니다. 1) 1 과 7을 더하면 8이므로 숫자가 부족하므로 왼쪽을 1 증가시킵니다. 2) 2 와 7을 더하면 9이므로 답을 1 증가시키고, 왼쪽을 1 증가, 오른쪽을 1 감소합니다. 3) 3과 5를 더하면 8이므로, 왼쪽을 1 증가합니다. 4) 4와 5를 더하면 9이므로, 왼쪽은 1 증가, 오른쪽을 1 감소합니다. 5) 왼쪽의 포인터와 오른쪽 포인터가 교차했으므로 종료합니다. 그러면 총 2개의 갑옷을 .. 2022. 11. 29. [C/C++] 백준 #1939 중량제한(그래프) 이번 문제는 프림이나 다익스트라와 비슷하게 동작하지만, 경로에 걸쳐있는 간선중, 최소값의 간선값이 해당 경로값이 됩니다. 이 경로값이 가장 큰 것을 찾는 문제입니다. 그래서 프림 알고리즘이나 다익스트라 알고리즘을 곧이 곧대로 사용할 수가 없습니다. 제가 사용한 탐욕 방법은 이것입니다. 0) 모든 노드의 값을 0으로 초기화합니다. 1) 출발지점에서 가장 큰 노드값을 가지고 있는 노드를 선택합니다. 2) 이동할 수 있는 모든 간선들을 적용하여 도착할 곳의 노드값을 결정합니다. 도착할 노드값은 현재보다 큰 경우 노드값을 저장하고, 우선순위큐에 해당 값을 넣습니다. 3) 도착지점이 가장 큰 노드값인 경우 종료합니다. 이 상태에서 선택할 수 있는 다른 노드값은 도착지점보다 적은 값이므로 의미가 없습니다. 제가 작.. 2022. 11. 19. [C/C++] 백준 #1937 욕심쟁이 판다(동적 계획법) 격자로 나누어진 공간에서 판다가 대나무를 먹는데, 옮긴곳이 이전보다 대나무가 더 많은 곳이어야 옮겨갈 수 있습니다. 판다는 이동을 할 때, 상하좌우중 하나를 선택해서 한칸만 옮겨갈 수 있습니다. 이 판다가 최대한 많은 대나무숲에서 식사를 할 수 있도록 하고자 할 때, 최대 이동횟수를 구하는 문제입니다. 조금 어려워보이지만, 전 일단 탐욕 방법을 사용했습니다. 판다가 처음 위치한 곳의 대나무숲이 적은 곳이어야 한다는 것이죠. 그래서 최대로 많은 곳까지 가는 대나무숲을 고르는 것이죠. \(V(s)\)의 값이 현재까지 이동한 횟수를 저장한다고 한다면, \[ V(s) = max_{s \rightarrow s'}(V(s'))+1 형태로 작성할 수 있습니다. 이것을 동적 계획법으로 풀기 위해서는 가장 적은 값부터 .. 2022. 11. 17. [C/C++] 백준 #1935 후위 표기식2(스택) 후위 표기식 계산을 스택을 이용하는 것은 이미 잘 알려져 있습니다. 이 문제는 \(+\alpha\)로 변수의 개념까지 둔 문제입니다. 제 경우에는 식과 변수값을 미리 다 읽고, 식을 읽으면서 스택에서 계산을 바로 하도록 작성했습니다. 후위 표기식 알고리즘은 간단한 스택 알고리즘을 작성하시면 되는 것이라 크게 어려운 점은 없습니다. 제가 작성한 소스입니다. //---------------------------------------------------------- // baekjoon #1935 - Postfix Equation // - by Aubrey Choi // - created at 2020-01-10 //---------------------------------------------------.. 2022. 11. 16. [C/C++] 백준 #1932 정수 삼각형(동적 계획법) 이번 문제는 삼각형 형태로 이루어진 숫자 피라미드에서 위의 꼭지점에서 바닥까지 이동을 할 때, 숫자들의 합이 최대가 되는 것을 고르는 것입니다. 아랫단에서는 선택할 수 있는 위의 숫자들이 최대 두가지가 됩니다. 이 중 최대값과 더하면 어느 곳이든 꼭지점에서부터 해당 지점까지 오는 경로의 합 중 최대값이 됩니다. 이를 이용해서 프로그램을 작성하면 됩니다. 단, 해당 층에서 맨 왼쪽 원소와 맨 오른쪽 원소는 선택할 수 있는 윗단의 숫자가 하이므로 미리 처리를 하든지, 예외 처리를 하시면 됩니다. 제 경우에는 경계처리를 간단하게 하기 위해서 일단 모든 값을 0으로 초기화해서 경계처리를 했습니다. 이렇게 경계처리를 하면 조건 검사를 덜하거나 예외처리를 하지 않아도 된다는 장점이 있습니다. 위에서부터 내려오는 방.. 2022. 11. 14. [C/C++] #1931 회의실 배정(탐욕) 최대한 많은 회의를 겹치는 시간 없이 하고자 합니다. 이 경우에는 빨리 끝나는 회의를 우선 배정하면 다음에 배정할 수 있는 회의가 많아질 수 있습니다. 선택의 폭을 넓히기 위해서는 회의가 끝나는 시간순으로 정렬합니다. 그런 후에 현재 끝난 회의의 시간을 기록하고, 시작시간이 그 시간보다 앞이라면 해당 회의는 할 수 없습니다. 제가 작성한 소스입니다. 소스는 참고용으로 봐주세요. //------------------------------------------ // baekjoon #1931 // - by Aubrey Choi // - created at 2019-09-07 //------------------------------------------ #include #include struct Lesso.. 2022. 11. 13. 이전 1 ··· 18 19 20 21 22 23 24 ··· 47 다음 728x90
