코후닝

알고리즘 분류: 수학, 다이나믹 프로그래밍, 그리디 알고리즘 문제 링크: https://www.acmicpc.net/problem/2839 2839번: 설탕 배달 상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그 www.acmicpc.net 【 문제 】 상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그램 봉지와 5킬로그램 봉지가 있다. 상근이는 귀찮기 때문에, 최대한 적은 봉지를 들고 가려고 한다. 예를 들어, 18킬로그램 설탕을 배달해야 ..

알고리즘 분류: 구현, 자료 구조, 시뮬레이션, 큐 문제 링크: https://www.acmicpc.net/problem/1966 1966번: 프린터 큐 여러분도 알다시피 여러분의 프린터 기기는 여러분이 인쇄하고자 하는 문서를 인쇄 명령을 받은 ‘순서대로’, 즉 먼저 요청된 것을 먼저 인쇄한다. 여러 개의 문서가 쌓인다면 Queue 자료구조에 www.acmicpc.net 【 풀이 】 주어진 테스트 케이스에서 특정 문서의 중요도가 몇 번째로 큰지 구하는 문제이다. 이 문제는 큐와 우선순위 큐, 그리고 pair를 사용하여 쉽게 해결할 수 있다. 다음은 이 문제의 단계적 접근방법이다. pair에 각각 { 인덱스, 중요도 } 순으로 큐에 저장 우선순위 큐를 구현하여 큐의 첫값과 우선순위 큐의 첫값을 비교 큐 원..

알고리즘 분류: 구현, 문자열, 해싱 문제 링크: https://www.acmicpc.net/problem/15829 15829번: Hashing APC에 온 것을 환영한다. 만약 여러분이 학교에서 자료구조를 수강했다면 해시 함수에 대해 배웠을 것이다. 해시 함수란 임의의 길이의 입력을 받아서 고정된 길이의 출력을 내보내는 함수로 정 www.acmicpc.net 【 풀이 】 문자열을 입력받아 해시값을 계산하는 문제이다. 이 문제는 한마디로, 문자열 각 인덱스의 문자값에 고유 계수를 거듭제곱한 값을 곱하여 그 수들을 더한 해시값을 구하라는 것이다. 그러기 위해서 먼저 m을 1234567891로, 각 계수에 곱할 r을 1로 선언한다. 그러고 아스키 코드 값을 이용해 문자열 각 인덱스의 값을 구하여 계산하면 ..

알고리즘 분류: 구현, 자료 구조, 스택 문제 링크: https://www.acmicpc.net/problem/10773 10773번: 제로 첫 번째 줄에 정수 K가 주어진다. (1 ≤ K ≤ 100,000) 이후 K개의 줄에 정수가 1개씩 주어진다. 정수는 0에서 1,000,000 사이의 값을 가지며, 정수가 "0" 일 경우에는 가장 최근에 쓴 수를 지우고, 아닐 경 www.acmicpc.net 【 문제 】 나코더 기장 재민이는 동아리 회식을 준비하기 위해서 장부를 관리하는 중이다. 재현이는 재민이를 도와서 돈을 관리하는 중인데, 애석하게도 항상 정신없는 재현이는 돈을 실수로 잘못 부르는 사고를 치기 일쑤였다. 재현이는 잘못된 수를 부를 때마다 0을 외쳐서, 가장 최근에 재민이가 쓴 수를 지우게 시킨다..

알고리즘 분류: 수학, 구현, 정렬 문제 링크: https://www.acmicpc.net/problem/2108 2108번: 통계학 첫째 줄에 수의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 단, N은 홀수이다. 그 다음 N개의 줄에는 정수들이 주어진다. 입력되는 정수의 절댓값은 4,000을 넘지 않는다. www.acmicpc.net 【 문제 】 수를 처리하는 것은 통계학에서 상당히 중요한 일이다. 통계학에서 N개의 수를 대표하는 기본 통계값에는 다음과 같은 것들이 있다. 단, N은 홀수라고 가정하자. 산술평균: N개의 수들의 합을 N으로 나눈 값 중앙값: N개의 수들을 증가하는 순서로 나열했을 경우 그 중앙에 위치하는 값 최빈값: N개의 수들 중 가장 많이 나타나는 값 범위: N개의 수들 중..

알고리즘 분류: 자료구조, 문자열, 스택 문제 링크: https://www.acmicpc.net/problem/4949 4949번: 균형잡힌 세상 각 문자열은 마지막 글자를 제외하고 영문 알파벳, 공백, 소괄호("( )"), 대괄호("[ ]")로 이루어져 있으며, 온점(".")으로 끝나고, 길이는 100글자보다 작거나 같다. 입력의 종료조건으로 맨 마지막에 www.acmicpc.net 【 문제 】 세계는 균형이 잘 잡혀있어야 한다. 양과 음, 빛과 어둠 그리고 왼쪽 괄호와 오른쪽 괄호처럼 말이다. 정민이의 임무는 어떤 문자열이 주어졌을 때, 괄호들의 균형이 잘 맞춰져 있는지 판단하는 프로그램을 짜는 것이다. 문자열에 포함되어 있는 괄호는 소괄호("()")와 대괄호("[]")로 2종류이고, 문자열이 균형을..