전체 글 (58) 썸네일형 리스트형 백준 20159 동작 그만. 밑장 빼기냐? https://www.acmicpc.net/problem/20159 20159번: 동작 그만. 밑장 빼기냐? 카드의 개수 N (2 ≤ N ≤ 100,000)이 주어진다. 단, N은 짝수이다. 둘째 줄에 카드의 윗장부터 밑장까지 카드의 값 X (1 ≤ X ≤ 10,000)이 정수로 주어진다. www.acmicpc.net 누적합을 사용하는 문제였습니다. 문제에서 저도 헷갈린 조건이 있었는데 밑장이란 현재 윗장인 카드의 바로 밑에 있는 카드가 아닌 맨 밑의 카드를 뜻하는 것이었습니다.(-_-) 밑장을 분배하는 순간 이 후 예정되어있던 분배순서가 정훈이와 상대가 바뀌게 됩니다. 이를 누적합을 통해 순서대로 분배를 탐색하면서 현재 밑장으로 바꿀때 합이 어떻게 되는지 계산하면됩니다. 정훈이 차례일경우 여태까지 정훈.. 백준 20437 문자열 게임 2 https://www.acmicpc.net/problem/20437 20437번: 문자열 게임 2 첫 번째 문자열에서 3번에서 구한 문자열은 aqua, 4번에서 구한 문자열은 raquator이다. 두 번째 문자열에서는 어떤 문자가 5개 포함된 문자열을 찾을 수 없으므로 -1을 출력한다. www.acmicpc.net 슬라이딩 윈도우를 통해 푸는 문제였습니다. 문자열이 주어지고 같은문자가 K개이며 시작글자와 마지막글자가 같은 연속 문자열 길이를 구해야 합니다. 문제를 해결하려면 같은 문자가 K개 나올때마다 당시의 연속 문자열의 길이를 기록하며 최소 최대를 구해야합니다. 같은 문자가 K개 나올때마다 문자열의 길이를 구할때 시작과 끝의 index를 통해 구할 수 있습니다. 따라서 각 문자마다 문자가 나올때 in.. 백준 11952 좀비 https://www.acmicpc.net/problem/11952 11952번: 좀비 첫 번째 줄에 N, M, K, S가 공백으로 구분되어 입력된다. 각 값은 도시의 수, 길의 수, 좀비에게 점령당한 도시의 수, 위험한 도시의 범위 를 의미한다. (2 ≦ N ≦ 100000, 1 ≦ M ≦ 200000, 0 ≦ K ≦ N - 2, www.acmicpc.net 다익스트라와 그래프 탐색을 이용하여 푸는 문제였습니다. 문제에서 요구하는 1에서 N까지 드는 최단 비용은 다익스트라 알고리즘을 통해 구할 수 있습니다. 하지만 좀비가 점령한 도시라는 변수가 있습니다. 좀비가 점령한 도시로부터 S이하의 거리에 존재하는 도시들은 비용이 틀려지기 때문에 bfs 혹은 dfs와 같은 그래프 탐색으로 이러한 도시들을 구해야 .. 백준 25200 곰곰이와 자판기 https://www.acmicpc.net/problem/25200 25200번: 곰곰이와 자판기 $f(k)$ 가 음료수 종류 $k$ 가 $M$ 번의 차원 이동을 거쳐 최종적으로 변하는 음료수 종류라고 할 때, $f(1), f(2), \cdots, f(N)$ 을 첫 번째 줄에 공백을 사이에 두고 출력하라. www.acmicpc.net 애드혹 문제였습니다. 음료수는 순서대로 현재상태에서 다른상태로 전이됩니다. 처음에 1~N의 번호를 가진 음료수 N개가 있고 순서대로 주어지는 전이에 따라 변한다고 생각하시면 될 것 같습니다. 문제에서 요구하는 것은 1~N번을 가진 N개의 음료수가 최종적으로 어떻게 변할 것인가에 대한 문제입니다. N과 전이의 횟수인 M 모두 300000이므로 처음부터 시작하여 각 전이마다 N.. 백준 24229 모두싸인 출근길 https://www.acmicpc.net/problem/24229 24229번: 모두싸인 출근길 취준생 주헌이는 드디어 취업에 성공했다. 주헌이가 취직한 회사는 비대면 전자계약 서비스 모두싸인(MODUSIGN) 이라는 회사이다. 그리고 오늘은 첫 출근날이다. 주헌이의 출근길에는 다리가 있 www.acmicpc.net 스위핑을 통해 푸는 문제였습니다. 문제에서 제시한 두번째 예시와 마찬가지로 주의할점은 점프할 수 있는 판자는 한가지가 아니라는 점입니다. 따라서 완전탐색으로 점프 하는 경우의수를 모두 체크할경우 경우의수가 매우 커지게됩니다. 문제에서 요구하는 것은 갈 수 있는 최대 좌표를 구하는 것입니다. 만약 겹치는 판자를 모두 합쳐 각 판자가 점프로 갈 수 있는 최대 좌표를 고정하게된다면 한번의 탐색으.. 백준 20168 골목 대장 호석 - 기능성 https://www.acmicpc.net/problem/20168 20168번: 골목 대장 호석 - 기능성 첫 줄에 교차로 개수 N, 골목 개수 M, 시작 교차로 번호 A, 도착 교차로 번호 B, 가진 돈 C 가 공백으로 구분되어 주어진다. 이어서 M 개의 줄에 걸쳐서 각 골목이 잇는 교차로 2개의 번호와, 골목의 www.acmicpc.net 그래프 탐색을 통해 푸는 문제였습니다. N개의 노드와 M개의 에지로 이루어진 그래프라고 볼 수 있습니다. 노드의 개수가 최대 10개고 시작과 도착이 정해져있으며 한 노드에서 특정 노드로 가는 에지는 최대 1개입니다. 따라서 그래프 탐색의 시간복잡도는 O(8!)가 됩니다. 그래프 탐색과정에서 최대요금만 기록해가며 도착 노드에 도달했을때 현재까지 나온 가장작은 최대요.. 백준 6987 월드컵 https://www.acmicpc.net/problem/6987 6987번: 월드컵 월드컵 조별 최종 예선에서는 6개국으로 구성된 각 조별로 동일한 조에 소속된 국가들과 한 번씩, 각 국가별로 총 5번의 경기를 치른다. 조별리그가 끝난 후, 기자가 보내온 각 나라의 승, 무승부 www.acmicpc.net 완전 탐색을 통해 푸는 문제였습니다. 총 6개국으로 구성된 팀이 서로 한번씩은 경기를 해야합니다. 따라서 6*5/2 = 15 번의 경기를 가지게 됩니다. O(3^15)시간 복잡도는 문제에서 제시한 시간제한을 만족합니다. 따라서 완전탐색을 통해 해결할 수 있습니다. 하지만 완전탐색이지만 좀 더 시간을 단축할 수 있는 여지가 있습니다. 저는 처음에 모든 경우의 수를 탐색한 후 각 경우의 수를 문제에서 제.. 백준 16965 구간과 쿼리 https://www.acmicpc.net/problem/16965 16965번: 구간과 쿼리 N개의 쿼리가 주어졌을 때, 쿼리를 수행해보자. 쿼리는 총 2가지 종류가 있고 아래와 같다. 가장 처음에 집합에는 아무것도 없다. 1 x y (x < y): 새로운 구간 (x, y)를 집합에 추가한다. 구간의 크기 www.acmicpc.net 그래프 탐색을 사용하는 문제였습니다. 이 문제에서 주의할점은 문제에서 주어진 조건을 만족하는 두 구간 사이의 이동이 양방향이 아니라는점입니다. 즉 무방향 그래프가 아니라는점입니다. 처음에는 저도 Union-Find를 사용해서 풀기를 시도하였고 틀리고나서 문제를 다시 읽다보니위에서 말한 점을 깨닫게 되었습니다. 쿼리가 구간을 추가하는 쿼리일때 이전에 추가했던 구간들과 현재 .. 이전 1 2 3 4 ··· 8 다음