본문 바로가기

알고리즘

 (46)
[BOJ 1298] 노트북의 주인을 찾아서(c++) https://www.acmicpc.net/problem/1298  문제 개요n명의 학생과 n개의 노트북이 있고, 노트북은 뒤섞여있다. 한 학생이 특정 노트북이 자신의 것 같다고 말하는 것이 m번 있다. 노트북을 최대한 많이 매치한 결과를 출력하라(1 (1  문제 풀이한 사람이 하나의 노트북과 매칭될 수 있으므로 이분 매칭 알고리즘을 적용하면 쉽게 풀이할 수 있다. 학생과 학생이 지목한 노트북을 인접리스트로 연결한 뒤 학생마다 인접리스트를 순회하며, 노트북이 학생과 매칭이 되지 않았다면, 해당 노트북과 학생을 매칭한다. 만약 학생 A의 인접리스트 속 노트북 1이 학생 B와 이미 매칭되어 있다면, 노트북 1과 매칭된 학생 B가 다른 노트북 2와 매칭될 수 있는지를 확인하고 매칭할 수 있다면 노트북 2와 학..
[BOJ 2263] 트리의 순회 (c++) https://www.acmicpc.net/problem/2263 문제 개요n개의 정점을 갖는 이진 트리의 정점에 1 ~ n까지의 번호가 중복없이 매겨져 있고, 중위 순회와 후위 순회의 결과가 주어졌을 때, 전위 순회의 결과를 구해야 한다.(1 문제 풀이중위 순회와 후위 순회의 결과를 알고 있으면, 전위 순회의 결과를 알 수 있고 트리의 구조를 유추할 수 있다. 이를 위해 전위, 중위, 후위 순회에 대해서 알아야 한다.아래와 같은 트리를 예로 들면,중위 순회와 후위 순회의 결과는 다음과 같다.   후위 순회의 결과를 보면 루트인 1번 정점을 마지막에 순회하는 것을 볼 수 있다. 또한 중위 순회의 결과를 보면 루트인 1번 정점을 기준으로 왼쪽은 왼쪽 하위 노드인 2번 노드를 루트로 하는 하위 정점들이 있고..
[BOJ 7578] 공장(c++) https://www.acmicpc.net/problem/7578 문제개요어떤 공장에 2n개의 기계가 2열에 걸쳐 n개씩 배치되어 있고, 이를 각각 A열과 B열이라 한다.A열과 B열의 기기들은 아래와 같이 1:1로 연결되어 있다. 두 기계를 연결하는 직선을 그릴때 직선끼리 교차하는 점이 몇개인지 구해야 한다.(1 (1  문제풀이A열의 순서대로 직선을 연결하며, 연결된 지점부터 n - 1까지의 연결된 갯수를 구하며 더해주면 손쉽게 교차점의 갯수를 구할 수 있다. A열의 기기는 순서대로 저장하고, B열의 기기들은 식별번호를 인덱스로 저장해주고, 갯수를 세는 세그먼트 트리를 만들어 저장해주었다. 코드#include using namespace std;int n;int arr[500001];int idx[100..
[BOJ 20919] XOR 자료구조 (c++) https://www.acmicpc.net/problem/20919 문제 개요T개의 테스트케이스가 있다. n개의 수를 포함한 집합 S에서 q개의 연산을 해야한다. 연산은 다음과 같다.find_min(v): 현재 자료 구조에 저장된 정수 집합이 S라면, (v XOR s) 값이 최소가 되는 S의 원소 s를 찾아 (v XOR s) 값을 출력한다. S는 변경되지 않는다.find_max(v): 현재 자료 구조에 저장된 정수 집합이 S라면, (v XOR s) 값이 최대가 되는 S의 원소 s를 찾아 (v XOR s) 값을 출력한다. S는 변경되지 않는다.add(v): 현재 자료 구조에 저장된 정수 집합 S에 v를 추가한다. 추가한 후, S에 저장된 고유한 정수의 개수를 출력한다.remove_min(): 현재 자료 구..
[BOJ 30865] xor 쿼리(c++) https://www.acmicpc.net/problem/30865  문제 개요길이가 N인 정수 수열 a = [a1, a2, ..., aN]이 주어질 때, Q개의 다음 쿼리를 처리하는 프로그램을 작성해야한다.  - 1 i x: ai의 값을 x로 변경  - 2 i x: 수열  [a1⊕x,a2⊕x,…,aN⊕x]에서 중복을 포함하여 i번째로 큰 값을 출력 (1  (0 문제 풀이트라이를 사용해 풀이하였다. 일반적으로 트라이는 문자열을 관리할때 사용하지만, 숫자를 저장할때도 사용할 수 있다.특히, xor 연산은 두 수의 각 비트를 비교하고 비트가 서로 다를수록 커지기 때문에 트라이에 수를 이진수로 바꾸어 저장하면 효과적으로 비교할 수 있다.수를 입력할때 트라이에 루트부터 가장 왼쪽 비트부터 집어 넣어야, 각 xo..
[BOJ 3665] 최종 순위(c++) https://www.acmicpc.net/problem/3665 문제 개요T개의 테스트케이스가 있다. 각 테스트 케이스에선 다음과 같은 정보가 주어진다.n개의 팀이 있고, 1등부터 n등까지의 순서대로 입력이 주어진다. 그리고 m개의 상대 순위가 바뀐 팀의 정보들이 주어진다.바뀐 정보가 6 13으로 주어진다면, 13팀이 6팀보다 순위가 높을경우 6팀이 13팀보다 높아진다.바뀐 정보들로 다시 순위를 만들건데, 입력된 순위 정보에 일관성이 없는 경우 "IMPOSSIBLE" 순위를 찾을 수 없는 경우 "?" 순위를 찾을 수 있다면, 1등팀부터 n등팀까지 순서대로 출력해야한다.(1 (2 (0   문제 풀이위상정렬 알고리즘을 활용해 풀이하였다. 입력을 바탕으로 간선을 직접 추가하였다.순위가 바뀐 경우엔 방문 처리..
[BOJ 14925]목장 건설하기(c++) https://www.acmicpc.net/problem/14925 문제 개요m x n 땅에서 정사각형 땅에 목장을 건설하려 한다. 땅에는 들판, 나무, 돌이 있고 들판에만 목장을 지을 수 있다. 목장을 가장 크게 지을 수 있는 경우의 한 변의 길이 L을 출력하자. (1  행렬의 원소 0은 들판 1은 나무 2는 돌 문제 풀이행렬에서 0인 부분으로 만들 수 있는 가장 큰 정사각형을 구해야 하는 문제이다. 완전 탐색으로 이 문제를 접근할 경우 한점을 왼쪽 대각선 위로 보고 만들 수 있는 정사각형의 최대 크기를 확인해야 한다. 이는 매우 오래 걸리고, 시간 초과가 나게 된다.해당 문제는 다이나믹 프로그래밍을 통해 간단히 해결할 수 있다. 만약 (x, y)가 0이라면 (x-1, y)와 (x, y-1), (x-1..
[BOJ 14728] 벼락치기(c++) https://www.acmicpc.net/problem/14728 문제 개요시험까지 남은 시간에서 공부를 해서 시험 점수를 최대한 잘 받아야 한다. 각 단원별 공부하는데 필요한 공부시간과 배점이 주어진다. 시험 문제의 조건은 다음과 같다. 1. 여러 단원을 융합한 문제는 출제하지 않는다. 2. 한 단원에 한 문제를 출제한다. 단, 그 단원에 모든 내용을 알고 있어야 풀 수 있는 문제를 낼 것이다. N개의 단원 (1 공부할 수 있는 총 시간 T (1 각 단원 별 공부시간 K, 문제 배점 S(1  문제 풀이공부 시간을 기준으로 DP 배열을 만든다면, 냅색 문제와 동일한 문제이다.DP의 점화식은 다음과 같다.DP[i] = max(DP[i - K] + S, DP[i])K, S를 입력받으면 T부터 K까지 DP배..

티스토리툴바