PS/boj (53) 썸네일형 리스트형 백준 23044 트리 조각하기 (C++) https://www.acmicpc.net/problem/23044 23044번: 트리 조각하기 타고난 트리 조각가 온조는 오늘도 완벽한 작품을 만들기 위해서 트리 $T$를 준비하였다. 온조는 뛰어난 예술적 직관을 통해 조각할 작품을 머릿속으로 구상하였고, 먼저 조각상의 전체적인 틀 www.acmicpc.net bfs와 파라메트릭 서치(이분탐색)을 이용하는 문제였습니다. 폭탄을 터뜨릴 정점을 선택하는 것과 최대 거리를 둘 다 구하는것은 매우 어렵습니다. N이 20만으로 매우크기때문이죠. 따라서 우리는 둘 중 하나를 고정해서 풀어야 합니다. 이럴때 우리가 사용할 수 있는게 파라메트릭 서치입니다. 우리는 최대거리를 구하고 싶습니다. 답이 되는 최대거리+1 이후로는 당연하게도 전부 최대거리 후보가 되지 못합니.. 백준 1786 찾기 (C++) 문자열 탐색 알고리즘을 사용하라는 문제입니다. kmp나 라빈 카프 둘 중 아무거나 사용하면 됩니다. 보이어무어 알고리즘 같은경우 최악의 경우 (N*M)이므로 시간복잡도를 넘게됩니다. 저는 라빈카프를 사용해서 풀었습니다. 영어소문자와 띄어쓰기로 이루어져있으므로 사용되는 문자가 61개정도되는데 충분히 큰 radix와 mod를 사용하셔야 합니다. #include #include #include #include #include #include #include #include #include #include using namespace std; void fast_io() { cin.tie(0)->sync_with_stdio(0); } long long MOD=1000000007; long long mod(long.. 백준 4817 괄호 (C++) https://www.acmicpc.net/problem/4817 4817번: 괄호 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 문제 설명의 문법을 만족하는 식이며, 한 줄로 이루어져 있다. 식의 길이는 최대 1000이다. www.acmicpc.net 재귀함수나 스택을 사용하는 문제였습니다. 저같은 경우 스택을 잘 못써서 재귀를 사용해 풀었습니다. 손으로 예제를 들어서 풀어보시면 괄호를 못없애는 경우는 괄호 안에 덧셈이 들어가있으며 괄호 앞 뒤로 곱하기가 들어가있는경우 뿐인걸 아실 수 있습니다. 따라서 재귀적으로 가장 바깥에 있는 괄호부터 풀어가시면서 그 괄호안에 덧셈이 들어가있는 경우만 체크해서 앞뒤로 곱하기가 있는지만 확인하고 괄호를 없애면 됩니다. 또한 유의해야되는 경우는 .. 백준 23022 숙제 (C++) https://www.acmicpc.net/problem/23022 23022번: 숙제 Albert는 앞으로 n개의 숙제를 해야한다 (편의상 1번부터 n번까지 번호가 붙어있다). 현재 시각은 S 이고, i번째 숙제의 내용은 정해진 시각 t[i]에 공개 된다 (어떤 숙제는 이미 공개 되었지만 Albert www.acmicpc.net 우선순위 큐를 사용하는 문제였습니다. 시간순으로 숙제를 정렬 한후 앞에서부터 스위핑하면서 현재시간(초기에는 S) 기준으로 작으면 큐에 넣고 현재시간보다 뒤의 숙제가 나온다면 현재시간을 증가시켜가며 큐에서 빼면됩니다. 그러다가 증가시키면서 지금보고있는 숙제시간의 시간과 같아진다면 현재 숙제를 큐에넣고 다음 숙제로 넘어가면 됩니다. #include #include #include .. 백준 16882 카드게임 (C++) https://www.acmicpc.net/problem/16882 16882번: 카드 게임 예제 1의 경우에 구사과가 7을 고르면 모든 카드가 제거되기 때문에, 큐브러버가 이길 수 없다. 예제 2의 경우에는 어떤 카드를 제거해도 카드 한 장이 남는다. 따라서, 큐브러버가 이긴다. www.acmicpc.net 게임이론 문제입니다. 게임이론 문제들은 제 경험상 손으로 써가면서 경우의 수를 찾는게 가장 좋더라고요. 생각보다 직관적이어서 어렵지 않은 문제였습니다. 어떤 수를 가져가면 그보다 작은 수 들을 전부 없애고 마지막으로 카드를 전부 없앤 사람이 이기는 게임입니다. 직관적으로 가장 큰 수를 가져가게되면 큰 수를 제외한 모든 수를 가져갈 수 있게되고 따라서 가장 큰 수의 개수가 승리와 연관이 되있다는걸 알.. 백준 21940 가운데에서 만나기 (C++) https://www.acmicpc.net/problem/21940 21940번: 가운데에서 만나기 위 조건을 만족하는 도시 $X$의 번호를 출력한다. 만약 가능한 도시 $X$가 여러 개인 경우는 도시의 번호를 오름차순으로 출력한다. www.acmicpc.net 대놓고 다익스트라를 사용하라는 문제였습니다. (양의 간선 가중치) n=200 다익스트라를 모든 점을 시작점으로 두고 돌려 다른 점에 대한 거리를 구해 배열에 저장한뒤 마을에 대해 답을 구하는 연산을 하면 됩니다. #include #include #include #include #include #include #include #include #include #include using namespace std; void fast_io() { cin... 백준 16117 실버런 (C++) https://www.acmicpc.net/problem/16117 16117번: 실버런 첫 번째 줄에 맵에 있는 실버 주머니들이 이루는 직사각형의 행과 열 수를 나타내는 정수 N, M(1 ≤ N, M ≤ 1,000)이 공백을 사이에 두고 주어진다. 다음 N개의 줄에 걸쳐 각 줄에 M개의 정수가 주 www.acmicpc.net 예제부터 이해하기 힘든 문제 였습니다. 예제2에서 많이 당황했어요. 혹시 못본게 있나 살펴봤더니 문제에 "정수 좌표가 아니어도 된다"라는 조건이 있더라고요. 그제서야 이해했습니다. .5지점에서 실버 주머니를 먹으면서 이동할 수 있었습니다. 대신 .5지점에서 움직이게 될 경우 오른쪽으로 갈 경우 실버주머니를 먹지 못합니다. 이 경우를 주의하여 각각 정수좌표계에서 움직이는 dp .5좌.. 백준 22345 누적거리 https://www.acmicpc.net/problem/22345 22345번: 누적 거리 KOI 나라는 수직선 위에 놓인 N개의 마을로 구성되어 있다. 이 중 i (1 ≤ i ≤ N)번째 마을은 xi 위치에 놓여 있으며 ai명이 거주 중이다. 또한 서로 다른 두 마을이 같은 위치에 놓인 경우는 없다. KOI www.acmicpc.net 마을이 총 20만개 이며 거리질의 또한 20만이므로 O(N^2)시간복잡도로 풀수 없습니다. 즉, 한 마을에 대해서 모든 마을의 거리를 계산하면 시간초과가 납니다. 따라서 우리가 배열에 흔히 쓰는 prefix sum을 마을에 대한 누적 거리 합을 저장하면 됩니다. 저는 마을 사람수를 정렬한 후 참조하려고 map을 썼지만 풀고 나니 map을 안썼어도 좋았겠네요. 거리 질의.. 이전 1 ··· 3 4 5 6 7 다음