본문 바로가기
  • Let's study

알고리즘15

[알고리즘] 백트레킹 백트래킹이란? 해를 얻을 때까지 모든 경우의 수를 시도하는 알고리즘이다. 규칙을 적용하여 얻은 결과가 틀리면 그 규칙을 적용한 다음부터 현재까지의 결과를 무시하고 이전으로 돌아가서 다른 규칙을 선택하여 다시 시도한다. 보통 DFS를 사용해서 탐색하면서 조건을 통해 필요 없는 부분을 쳐낸다. 백트래킹 예시 N-Queen 문제가 가장 대표적인데, 예시로 너무 많이 나와서 다른 문제를 준비해봤다. N과 M (1) 자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. - 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열 해결방법 해당 숫자를 골랐는지의 유무를 저장하는 visited 배열을 사용하여 1부터 고르지 않은 숫자를 찾아 arr 배열에 저장한.. 2023. 10. 5.
[알고리즘] 다익스트라 다익스트라 알고리즘이란? 다익스트라는 그래프에서 한 정점에서 다른 정점까지의 최단 경로를 구하는 알고리즘이다. 최단 경로 구하는 과정 출발점으로부터의 최단거리를 저장할 배열 d[v]를 만들고, 출발 노드에는 0을, 출발점을 제외한 다른 노드들에는 매우 큰 값 INF를 채워 넣는다. A로부터 갈 수 있는 임의의 노드 B에 대해, d[A] + P[A][B](가중치)와 d[B]의 값을 비교한다. d[A] + P[A][B] < d[B] 라면, d[B] = d[A] + P[A][B]로 갱신시킨다. A의 모든 이웃 노드 B에 대해 이 작업을 수행한다. A의 방문 상태를 TRUE로 바꾼다. 방문하지 않은 모든 노드들 중, 출발점으로부터의 거리가 제일 짧은 노드를 다시 A로 지정한다. 도착 노드의 방문 상태가 TRUE.. 2023. 10. 2.
[C++] 백준 2109번: 순회강연 문제 한 저명한 학자에게 n(0 ≤ n ≤ 10,000)개의 대학에서 강연 요청을 해 왔다. 각 대학에서는 d(1 ≤ d ≤ 10,000)일 안에 와서 강연을 해 주면 p(1 ≤ p ≤ 10,000)만큼의 강연료를 지불하겠다고 알려왔다. 각 대학에서 제시하는 d와 p값은 서로 다를 수도 있다. 이 학자는 이를 바탕으로, 가장 많은 돈을 벌 수 있도록 순회강연을 하려 한다. 강연의 특성상, 이 학자는 하루에 최대 한 곳에서만 강연을 할 수 있다. 예를 들어 네 대학에서 제시한 p값이 각각 50, 10, 20, 30이고, d값이 차례로 2, 1, 2, 1 이라고 하자. 이럴 때에는 첫째 날에 4번 대학에서 강연을 하고, 둘째 날에 1번 대학에서 강연을 하면 80만큼의 돈을 벌 수 있다. 입력 첫째 줄에 정수.. 2021. 11. 1.
[C++] 백준 1946: 신입사원 문제 언제나 최고만을 지향하는 굴지의 대기업 진영 주식회사가 신규 사원 채용을 실시한다. 인재 선발 시험은 1차 서류심사와 2차 면접시험으로 이루어진다. 최고만을 지향한다는 기업의 이념에 따라 그들은 최고의 인재들만을 사원으로 선발하고 싶어 한다. 그래서 진영 주식회사는, 다른 모든 지원자와 비교했을 때 서류심사 성적과 면접시험 성적 중 적어도 하나가 다른 지원자보다 떨어지지 않는 자만 선발한다는 원칙을 세웠다. 즉, 어떤 지원자 A의 성적이 다른 어떤 지원자 B의 성적에 비해 서류 심사 결과와 면접 성적이 모두 떨어진다면 A는 결코 선발되지 않는다. 이러한 조건을 만족시키면서, 진영 주식회사가 이번 신규 사원 채용에서 선발할 수 있는 신입사원의 최대 인원수를 구하는 프로그램을 작성하시오. 입력 첫째 줄.. 2021. 11. 1.
[C++] 백준 1931번: 회의실 배정 문제 한 개의 회의실이 있는데 이를 사용하고자 하는 N개의 회의에 대하여 회의실 사용표를 만들려고 한다. 각 회의 I에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 회의의 최대 개수를 찾아보자. 단, 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다. 회의의 시작시간과 끝나는 시간이 같을 수도 있다. 이 경우에는 시작하자마자 끝나는 것으로 생각하면 된다. 입력 첫째 줄에 회의의 수 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N+1 줄까지 각 회의의 정보가 주어지는데 이것은 공백을 사이에 두고 회의의 시작시간과 끝나는 시간이 주어진다. 시작 시간과 끝나는 시간은 231-1보다 작거.. 2021. 11. 1.
[알고리즘] 탐욕(그리디) 알고리즘 그리디 알고리즘이란? 탐욕적 알고리즘이라고도 하며, 여러 경우 중 하나를 결정해야 할 때마다 그 순간에 최적이라고 생각되는 것을 선택해 나가는 방식으로 진행하여 최종적인 해답에 도달한다. A에서 C까지 가는 최단 경로는? A에서 B로 갈 때 가장 적은 비용인 20을 고른다. B에서 C로 갈 때 가장 적은 비용인 8을 고른다. A에서 C로 가는 최단 경로는 20+8=28인 것을 알 수 있다! 이 문제는 선택의 순간마다 가장 적은 비용이 드는 길을 찾아가는 방법으로 풀 수 있었다. 아래의 문제도 위와 같이 그때그때 가장 최적의 값을 고르는 방법으로 풀어야 할까? 총 합이 최대의 값을 얻는 방법은? 위의 방법처럼 그때그때 최적의 값을 골라보자. start에서 시작하여 최대의 값을 얻어야 하니 15로 가보자. .. 2021. 11. 1.

티스토리툴바