본문 바로가기
반응형

Programming401

[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.
[C/C++] 백준 #1929 소수 구하기(에라토스테네스의 체) 주어진 범위안의 숫자에 대해서 소수를 출력하라는 문제입니다. 사실 소수 구하기는 여러가지 방법이 있지만, 에라토스테네스의 체를 사용하는 것이 가장 빠른 편입니다. 에라토스테네스의 체를 사용하는 데 있어서 단점은 처음부터 해야한다는 것입니다. 특히 2의 배수의 개수는 많으므로, 보다 효율적인 형태를 만들려면, m이 2보다 작거나 같고, n이 2보다 크거나 같으면, 2는 무조건 출력하고, 홀수에 대해서만 처리하는 방법입니다. 그렇게 하면 전체적으로 \(\frac{1}{4}\)로 줄일 수 있습니다. 또한 메모리 문제입니다. 메모리 제한이 작으면, 에라토스테네스의 체를 비트필드 형태로 하든지 아니면, \(n \sqrt{n}\) 알고리즘으로 만들어야 합니다. 이 문제 자체가 Silver III 등급정도의 문제로 .. 2022. 11. 11.
[C/C++] 백준 #1922 네트워크 연결(크루스칼) 컴퓨터 네트워크를 공용망에 연결하지 않고, 체인 형태로 연결할 때, 최소 비용으로 모든 컴퓨터를 다 연결하고자 합니다. 컴퓨터간 연결하는 비용이 제시되었을 때, 이를 이용해서 가장 최소 비용으로 컴퓨터간 연결을 모두 합니다. 대표적인 최소 간선 비용 트리(MST : Minimum Spanning Tree) 문제입니다. 최소 간선 비용 트리를 만드는 방법은 여러가지가 있지만, 보편적으로 많이 사용되는 것이 크루스칼 알고리즘과 프림 알고리즘입니다. 그 외에도 몇가지 더 있죠. 집합 개념을 사용해서 집합갠 최소 비용 간선을 선택할 수도 있고요. 크루스칼 알고리즘과 같이 간선 가중치를 모두 정렬한 후에 최소 비용 간선을 선택하면서 집합을 늘려가는 방법도 있습니다. 제 경우에는 크루스칼 알고리즘을 이용했습니다. .. 2022. 11. 9.
[C/C++] 백준 #1920 수 찾기(이진 탐색) 주어진 수열에서 M개의 데이터 중에 해당 수가 존재하는지 여부를 가리는 문제입니다. 집합 자료를 이용하면 손쉽게 구현할 수 있고, 또는 정렬 후 이진 탐색을 통해서도 이루어질 수 있습니다. 해시 집합 자료를 이용하면, 이론적으로 \(O(N+M)\)의 효율로 구현될 수 있습니다. 이진트리 집합 자료인 경우에는 \(O((N+M) \log N)\)이 걸립니다. \( \log N \) 자체가 큰 로드가 아니므로 사실상 집합 자료를 사용해도 되고, 정렬 후 이진 탐색을 사용해도 됩니다. 저는 정렬 후 이진 탐색을 이용해서 구현했습니다. 알고리즘 효율은 \(O( (N+M) \log N )\)입니다. 제가 작성한 소스입니다. //------------------------------------------------ .. 2022. 11. 8.
728x90

티스토리툴바