[백준] 28422: XOR 카드 게임
알고리즘: 다이내믹 프로그래밍 문제 링크: https://www.acmicpc.net/problem/28422 28422번: XOR 카드 게임 XOR 카드 게임이란 $N$장의 카드 더미가 있을 때, 맨 위에서부터 카드를 두 장 혹은 세 장씩 가져가 점수를 획득하는 게임이다. 이 게임에서 점수는 아래 단계를 거쳐 누적해서 획득할 수 있다. 한 www.acmicpc.net 【 문제 】 주어진 카드 n장 중 2장 혹은 3장을 카드가 0장이 될 때까지 뽑는다. 뽑은 카드에 적힌 숫자들을 XOR 연산한 뒤, 2진수 값으로 변환시켜 1의 개수를 구하고 점수로 더한다. 마지막에 1장의 카드가 남을 경우 최종 점수가 0점이 된다. 이때 점수의 최댓값을 구하는 문제. 【 풀이 】 1비트의 개수를 구하는 함수를 정의한다...
[백준] 1874번: 스택 수열 [C++]
알고리즘 분류: 자료 구조, 스택 문제 링크: https://www.acmicpc.net/problem/1874 1874번: 스택 수열 1부터 n까지에 수에 대해 차례로 [push, push, push, push, pop, pop, push, push, pop, push, push, pop, pop, pop, pop, pop] 연산을 수행하면 수열 [4, 3, 6, 8, 7, 5, 2, 1]을 얻을 수 있다. www.acmicpc.net 【 풀이 】 입력으로 받은 수열을 스택을 활용하여 순서대로 구현할 수 있는지를 물어보는 문제이다. 증가하는 변수 cnt를 선언해 주고, 입력한 숫자 n과 같아질 때까지 증가시키고 스택에 저장. 그 후 '+' 기호를 벡터에 저장한다. 그리고 스택의 맨 나중에 들어온 값과 ..
[백준] 2839번: 설탕 배달 [C++]
알고리즘 분류: 수학, 다이나믹 프로그래밍, 그리디 알고리즘 문제 링크: https://www.acmicpc.net/problem/2839 2839번: 설탕 배달 상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그 www.acmicpc.net 【 문제 】 상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그램 봉지와 5킬로그램 봉지가 있다. 상근이는 귀찮기 때문에, 최대한 적은 봉지를 들고 가려고 한다. 예를 들어, 18킬로그램 설탕을 배달해야 ..
[백준] 1966번: 프린터 큐 [C++]
알고리즘 분류: 구현, 자료 구조, 시뮬레이션, 큐 문제 링크: https://www.acmicpc.net/problem/1966 1966번: 프린터 큐 여러분도 알다시피 여러분의 프린터 기기는 여러분이 인쇄하고자 하는 문서를 인쇄 명령을 받은 ‘순서대로’, 즉 먼저 요청된 것을 먼저 인쇄한다. 여러 개의 문서가 쌓인다면 Queue 자료구조에 www.acmicpc.net 【 풀이 】 주어진 테스트 케이스에서 특정 문서의 중요도가 몇 번째로 큰지 구하는 문제이다. 이 문제는 큐와 우선순위 큐, 그리고 pair를 사용하여 쉽게 해결할 수 있다. 다음은 이 문제의 단계적 접근방법이다. pair에 각각 { 인덱스, 중요도 } 순으로 큐에 저장 우선순위 큐를 구현하여 큐의 첫값과 우선순위 큐의 첫값을 비교 큐 원..
[백준] 15829번: Hashing [C++]
알고리즘 분류: 구현, 문자열, 해싱 문제 링크: https://www.acmicpc.net/problem/15829 15829번: Hashing APC에 온 것을 환영한다. 만약 여러분이 학교에서 자료구조를 수강했다면 해시 함수에 대해 배웠을 것이다. 해시 함수란 임의의 길이의 입력을 받아서 고정된 길이의 출력을 내보내는 함수로 정 www.acmicpc.net 【 풀이 】 문자열을 입력받아 해시값을 계산하는 문제이다. 이 문제는 한마디로, 문자열 각 인덱스의 문자값에 고유 계수를 거듭제곱한 값을 곱하여 그 수들을 더한 해시값을 구하라는 것이다. 그러기 위해서 먼저 m을 1234567891로, 각 계수에 곱할 r을 1로 선언한다. 그러고 아스키 코드 값을 이용해 문자열 각 인덱스의 값을 구하여 계산하면 ..
[백준] 10773번: 제로 [C++]
알고리즘 분류: 구현, 자료 구조, 스택 문제 링크: https://www.acmicpc.net/problem/10773 10773번: 제로 첫 번째 줄에 정수 K가 주어진다. (1 ≤ K ≤ 100,000) 이후 K개의 줄에 정수가 1개씩 주어진다. 정수는 0에서 1,000,000 사이의 값을 가지며, 정수가 "0" 일 경우에는 가장 최근에 쓴 수를 지우고, 아닐 경 www.acmicpc.net 【 문제 】 나코더 기장 재민이는 동아리 회식을 준비하기 위해서 장부를 관리하는 중이다. 재현이는 재민이를 도와서 돈을 관리하는 중인데, 애석하게도 항상 정신없는 재현이는 돈을 실수로 잘못 부르는 사고를 치기 일쑤였다. 재현이는 잘못된 수를 부를 때마다 0을 외쳐서, 가장 최근에 재민이가 쓴 수를 지우게 시킨다..
