반응형 알고리즘/백준 문제풀이 썸네일형 리스트형 [BOJ 2336] 굉장한 학생 [문제] : https://www.acmicpc.net/problem/2336 2336번: 굉장한 학생 문제 N명의 학생이 참여하여 세 번의 시험을 치렀다. N명의 학생들은 세 번의 시험에 모두 응시하였다. 조교는 각각의 시험에서 같은 등수의 학생이 한 명도 없도록 성적을 매겼다. A라는 학생이 www.acmicpc.net [난이도] - Platinum 2 (2020.08.05 solved.ac 기준) [개념] - 세그먼트 트리 (Segment Tree) [풀이] 우선 https://jason9319.tistory.com/57 블로그의 설명을 참고하여 풀이를 하였다. 문제를 요약하자면, 각 학생이 세 번의 시험에 참여하였고, 학생 A보다 세 과목이 모두 더 높은 등수인 사람이 없다면 A를 '굉장하다'라고.. [BOJ 2437] 저울 [문제] : https://www.acmicpc.net/problem/2437 2437번: 저울 하나의 양팔 저울을 이용하여 물건의 무게를 측정하려고 한다. 이 저울의 양 팔의 끝에는 물건이나 추를 올려놓는 접시가 달려 있고, 양팔의 길이는 같다. 또한, 저울의 한쪽에는 저울추들만 놓� www.acmicpc.net [개념] - 그리디 (Greedy) 알고리즘 [풀이] 아이디어만 떠올린다면 생각보다 쉬운 문제이다. N개의 추가 주어졌을 때, 추들을 이용하여 측정할 수 없는 무게 중 가장 작은 무게를 구하는 것이다. 첫 번째로, 측정할 수 있는 무게들을 모두 구하는 것은 당연히 풀이의 의도가 아니라는 것을 알 수 있어야 한다. 완전 탐색으로 구한다고 한다면 추의 개수가 최대 1000개이므로 경우의 수가 최대.. [BOJ 8980] 택배 [문제] : https://www.acmicpc.net/problem/8980 8980번: 택배 입력의 첫 줄은 마을 수 N과 트럭의 용량 C가 빈칸을 사이에 두고 주어진다. N은 2이상 2,000이하 정수이고, C는 1이상 10,000이하 정수이다. 다음 줄에, 보내는 박스 정보의 개수 M이 주어진다. M은 1이 www.acmicpc.net [필요 개념] - 그리디 (Greedy) 알고리즘 [풀이] 문제 난이도 치고 (풀이일 기준 Gold 4) 생각보다 풀이 방법이 쉽게 떠오르지 않은 문제였다. 처음에는 보내는 마을을 오름차순으로 정렬한 후, 현재 트럭에 있는 박스 개수를 계속 비교하면서 더 채울 수 있으면 채우고, 내릴 수 있으면 내리는 방식으로 하였으나 당연히 WA를 받았다. 다음과 같은 반례가 있.. [BOJ 12920] 평범한 배낭 2 [문제] : https://www.acmicpc.net/problem/12920 12920번: 평범한 배낭 2 첫 번째 줄에 N, M (1 ≤ N ≤ 100, 1 ≤ M ≤ 10,000) 이 빈칸을 구분으로 주어진다. N은 민호의 집에 있는 물건의 종류의 수이고 M은 민호가 들 수 있는 가방의 최대 무게다. 두 번째 줄부터 N개의 줄에 � www.acmicpc.net [필요 개념] - DP , 배낭 문제 (Knap-sack) - 비트마스크 [풀이] 전형적인 배낭문제 (Knapsack)처럼 보이나, 이 문제에서는 특별하게 고려해줘야 하는 부분이 있다. 바로 같은 종류의 물건의 개수가 2개 이상일 수 있다는 것이다. 원래 배낭문제에서는 각 물건이 하나씩 있어, 해당 물건을 넣거나 빼는 두가지 경우만 있었는데.. [BOJ 2517] 달리기 출처 : https://www.acmicpc.net/problem/2517 2517번: 달리기 첫째 줄에는 선수의 수를 의미하는 정수 N이 주어진다. N은 3 이상 500,000 이하이다. 이후 N개의 줄에는 정수가 한 줄에 하나씩 주어진다. 이 값들은 각 선수들의 평소 실력을 앞에서 달리고 있는 선수부터 제시한 것이다. 각 정수는 1 이상 1,000,000,000 이하이다. 단, 참가한 선수들의 평소 실력은 모두 다르다. www.acmicpc.net 세그먼트 트리(Segment Tree)를 이용한 문제이다. 각 선수마다 자기보다 앞에 달리고 있는 선수들 중에서 자신보다 실력이 높은 사람의 수 + 1이 자신의 최선의 등수가 된다. 각 선수들의 실력을 정수로 나타내었고, 실력의 범위가 1~10억이다. 여기.. [BOJ 2568] 전깃줄 - 2 문제 출처 : https://www.acmicpc.net/problem/2568 2568번: 전깃줄 - 2 첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100,000 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결되는 위치의 번호가 차례로 주어진다. 위치의 번호는 500,000 이하의 자연수이고, 같은 위치에 두 개 이상의 전깃줄이 연결될 수 없다. www.acmicpc.net LIS (Longest Increasing Subsequence, 최장 증가 부분 수열) 유형의 문제이다. 전깃줄이 순서없이 입력되기 때문에 A 또는 B를 기준으로 정렬을 해주어야 한다. A를 기준으로 정렬한다면, 정렬된 후의 B 수열을 가지고.. [BOJ 11066] 파일 합치기 (https://www.acmicpc.net/problem/11066) 이 문제는 Dynamic Programming을 이용하는 문제이며, Knuth's Optimization을 이용하여 최적화를 한다. Knuth's Optimization 게시글 (https://wogud6792.tistory.com/20) 위 문제는 파일을 합치는 모든 경우 중에서, 합이 최소가 되는 경우를 찾는 문제이다. 만약 C1~C4를 합친다면, C1 + C2~C4 또는, C1~C2 + C3~C4 또는, C1~C3 + C4와 같이 부분문제가 만들어질 수 있다. 이 때, C2 ~ C4, C1 ~ C3의 경우도 또 다시 부분문제로 나뉘어 질 수 있다. ex) C2 + C3~C4 또는 C2~C3 + C4 / C1 + C2~C3 또는 .. [BOJ 1725] 히스토그램 1725번 (히스토그램) 위의 문제는 분할 정복 알고리즘을 이용해서 해결할 수 있다. 분할 정복은 주어진 문제를 부분 문제들로 나누어 푸는 것이기 때문에 이 문제 또한 히스토그램을 나누어 푸는 것이 핵심이다. 따라서 주어진 n개의 막대그래프를 절반으로 나누게 되면 결국 찾고자 하는 가장 큰 직사각형은 다음 세가지중 하나에 속하게 된다. 1. 왼쪽 부분 문제에서 가장 큰 직사각형이 존재하는 경우 2. 오른쪽 부분 문제에서 가장 큰 직사각형이 존재하는 경우 3. 가장 큰 직사각형이 왼쪽 부분 문제와 오른쪽 부분 문제에 걸쳐 있는 경우 1번과 2번의 경우에는 재귀 호출을 이용하면 되고, 3번의 경우만 특별히 고려한다면 답을 구할 수 있을 것이다. 문제에서 출력이 20억을 넘지 않는다고 하였으니, 변수 자료형을.. 이전 1 2 3 4 다음
