본문 바로가기

알고리즘 (2020 : 08 : 10 ~ )/구현, 시뮬

(65)
[백준 / BOJ] 1091 카드 섞기 문제 출처 : https://www.acmicpc.net/problem/1091 1091번: 카드 섞기 지민이는 카지노의 딜러이고, 지금 3명의 플레이어(0, 1, 2)가 있다. 이 게임은 N개의 카드를 이용한다. (0 ~ N-1번) 일단 지민이는 카드를 몇 번 섞은 다음에, 그것을 플레이어들에게 나누어 준다. 0 www.acmicpc.net N장의 카드를 3명의 플레이어에게 나눠줄려고 한다. 카드를 주어진 조건 S를 이용해 섞어서 P에 맞게 나눠줄 수 있는지 구하는 문제이다. 풀이 지문이 난해한 문제다. 지문만 이해한다면, 시뮬레이션으로 풀면 되는데, 이때 최댓값을 계산 해줘야 한다. 이렇게 하면 안되지만... 나는 최댓값 계산에 실패해서 백준 채점 시스템을 이용해서 가지를 쳐가며 풀었다. 따라서, 증..
[백준 / BOJ] 17615 볼 모으기 문제 출처 : https://www.acmicpc.net/problem/17615 17615번: 볼 모으기 첫 번째 줄에는 볼의 총 개수 N이 주어진다. (1 ≤ N ≤ 500,000) 다음 줄에는 볼의 색깔을 나타내는 문자 R(빨간색 볼) 또는 B(파란색 볼)가 공백 없이 주어진다. 문자열에는 R 또는 B 중 한 종류만 주 www.acmicpc.net 빨간색과 파란색으로 이루어진 N개의 연속된 공이 주어진다. 자신의 옆에 다른색의 공이 있다면, 바로 옆에있는 다른색의 공과 같은 색으로 이루어진 공의 집단을 한번에 뛰어넘을수있을때, 최소한의 이동횟수로 같은색 공끼리 모으는 문제다. 단, 공은 처음으로 움직인 공과 같은색의 공만 조작할 수 있다. 풀이 그리디 문제였다. N이 500,000이라서 어려워 보이..
[백준 / BOJ] 16564 히오스 프로게이머 (누적합 풀이) 문제 출처 : https://www.acmicpc.net/problem/16564 16564번: 히오스 프로게이머 첫째 줄에는 캐릭터의 개수 N, 올릴 수 있는 레벨 총합 K가 주어진다. (1 ≤ N ≤1,000,000, 1 ≤ K ≤ 1,000,000,000) 다음 N개의 줄에는 현재 각 캐릭터의 레벨이 X1, X2, X3, ... , Xn 으로 주어진다. (1 ≤ X www.acmicpc.net N개의 캐릭터로 이루어진 팀이 있다. 이 팀의 팀 레벨은 팀의 가장 작은 레벨을 갖고있는 플레이어의 레벨과 동일하다. 팀의 플레이어의 레벨을 K만큼 올릴 수 있을때, 최대 팀 레벨을 구하는 문제다. 풀이 약간의 아이디어만 있으면 풀리는 문제였다. N과 K의 값이 커서 완전탐색으로 풀경우 시간초과가 나온다. 시..
[백준 / BOJ] 5875 오타 문제 출처 : https://www.acmicpc.net/problem/5875 5875번: 오타 올바른 괄호쌍을 좋아하는 키파는 최근에 노트북을 샀다. 그런데 키보드의 크기가 너무 작았기 때문에, 키파는 혹시 여는 괄호와 닫는 괄호를 서로 잘못 입력하지 않았는지 걱정되었다. 키 www.acmicpc.net 오타가 '최대 한번' 있는 괄호배열이 주어진다. 이 괄호배열의 괄호를 하나 조작하여 올바른 괄호 배열을 만드는 경우의 수 를 구하는 문제다. 풀이 어려웠던 문제다 누적합으로 풀었는데, 여는 괄호를 +1, 닫는괄호를 -1 이라고 하고 누적합 배열을 만들자. 예를들어, 괄호배열 ( ) 의 누적합배열은 {1, 0}, ( ( ) ) 의 누적합 배열은 {1, 2 ,1, 0}이 된다. 올바른 괄호배열이 여는괄호..
[백준 / BOJ] 11509 풍선 맞추기 문제 출처 : https://www.acmicpc.net/problem/11509 11509번: 풍선 맞추기 첫 번째 예제 에서 [5,4,3] 을 터트리고 [2,1]을 터트리면 모든 풍선을 터트릴 수 있으므로 최소한 2개의 화살을 필요로 한다. www.acmicpc.net 높이가 같거나 다른 N개의 풍선이 직선에 있다. 화살을 날려 풍선을 터트릴 수 있는데, 한 풍선을 터트릴때마다 화살의 높이가 1만큼 낮아진다. 이때, 모든 풍선을 터트리기위해 필요한 화살의 최소횟수를 구하는 문제다. 풀이 아이디어?로 풀리는 문제였다. 풍선이 최대 1,000,000개 주어지기 때문에, 완전탐색으로는 풀 수 없다. 문제를 풀기위해, 이전에 던져진 화살들의 위치를 기억하는 방식으로 풀었는데, 이러면 O(N)시간복잡도로 문제..
[백준 / BOJ] 22866 탑 보기 문제 출처 : https://www.acmicpc.net/problem/22866 22866번: 탑 보기 3번째 건물에서 볼 수 있는 건물은 2, 4, 8번째 건물로 총 3개를 볼 수 있다. 그 중 3번째 건물과 가장 가까운 건물은 2, 4번째 있는 건물로 이 중 번호가 작은 번호인 2가 답이 된다. www.acmicpc.net 일직선으로 다양한 높이의 건물이 존재한다. 한 건물 i의 옥상에서 다른 건물들을 볼때 높이가 건물 i보다 큰 건물만 볼 수 있으며, 높이가 L인 건물 뒤에 L이하인 건물은 볼 수 없다고 할때, 각 건물에서 볼 수 있는 건물의 최대 수와 가장 가까운 건물의 idx를 구하는 문제다. 풀이 N이 최대 100,000으로 완전탐색으로 구현할 경우 O(N*N)번 반복해서 TLE를 맞게된다...
[programmers / kakao] 무지의 먹방 라이브 (Java) 문제 출처 : https://programmers.co.kr/learn/courses/30/lessons/42891?language=java# 코딩테스트 연습 - 무지의 먹방 라이브 programmers.co.kr 각 음식을 먹는데 필요한 시간이 있는 foodTimes[] 배열이 주어진다. 항상 하나의 음식을 1초 먹은후, 다음 음식을 먹어야 하며, 음식은 1초동안 1만큼 먹을 수 있다. (단, 음식의 양foodTimes[] 배열의 원소가 0일 경우에는 음식을 다 먹은것 이라고 판단하고 다음 음식을 먹는다.) 이때, K번째 먹을 음식을 찾는 문제다. (정확히는 K초 후 네트워크 장애가 일어나고, 네트워크 장애가 해결된 후, 먹을 음식의 idx를 출력하는것 인데, 결국 K번째 먹을 음식을 물어보는거랑 똑같..
[백준 / BOJ] 1195 킥다운 문제 출처 : https://www.acmicpc.net/problem/1195 1195번: 킥다운 첫 줄에는 첫 번째 기어 파트를 나타내는 1과 2로 구성된 문자열이 주어진다. 두 번째 줄에는 마찬가지로 두 번째 기어 파트를 나타내는 1, 2로 구성된 문자열이 주어진다. 여기서 1은 홈을, 2는 www.acmicpc.net 두개의 기어파트가 주어진다. 각 기어파트는 1과 2로 이루어져있는데, 1은 '홈(들어가있는 부분)' 2는 '이(나와있는 부분)'를 나타낸다 이 때, 두개의 기어파트를 적절히 조합하여 조합된 기어파트의 길이의 최솟값을 구하는 문제다. 풀이 기어의 길이가 최대 100이므로 완전탐색으로 풀리는 문제다. 문제에서 주어진 그대로 구현하면 되는데, 몇가지 주의할 점 이 있다. - 기어가 맞물린..