Algorithm/BeakJoon (24) 썸네일형 리스트형 [BeakJoon 1480] 보석 모으기 안녕하세요. 이번 포스팅에서는 백준 1480 보석 모으기 문제를 풀어보도록 하겠습니다. 해당 문제는 https://www.acmicpc.net/problem/1480 1480번: 보석 모으기 첫째 줄에 보석의 개수 N, 가방의 개수 M, 가방의 최대 한도 C가 주어진다. N은 1보다 크거나 같고, 13보다 작거나 같은 자연수이고, M은 1보다 크거나 같고, 10보다 작거나 같은 자연수이다. C는 1보 www.acmicpc.net 위 링크에서 확인하실 수 있습니다. 처음 이 문제를 보았을 때 각 가방의 한도가 같기 때문에 투 포인터 형식으로 접근을 하였는데, 해당 방식이 최적해를 구하지 못합니다. 따라서 이 문제는 Dynamic Programming으로 모든 status에 대한 검사를 해야 합니다. 가방의.. [BeakJoon 2042] 구간 합 구하기 안녕하세요. 이번 포스팅에서는 BeakJoon 2042 구간 합 구하기 문제를 풀어보도록 하겠습니다. 문제는 https://www.acmicpc.net/problem/2042 2042번: 구간 합 구하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 합을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄 www.acmicpc.net 위 링크에서 확인하실 수 있습니다. 우선 이 문제는 구간 합 구하기 문제이긴 한데, 동적으로 계속 배열 값이 변경되기 때문에 이를 일일이 변경할 수가 없습니다. https://chanho0912.tistory.com/29?categ.. [BeakJoon 17623] 괄호 안녕하세요. 이번 포스팅에서는 백준 17623 괄호 문제를 풀어보도록 하겠습니다. 문제는 https://www.acmicpc.net/problem/17623 17623번: 괄호 6개의 문자 ‘(’, ‘)’, ‘{’, ‘}’, ‘[’, ‘]’ 로 이루어진 올바른 괄호 문자열 W에 대하여 정수의 ‘괄호값’을 지정하는 함수 val(W)가 정의되어 있다. 먼저 올바른 괄호 문자열부터 정의해 www.acmicpc.net 위 링크에서 확인하실 수 있습니다. 이 문제를 dynamic programming으로 접근해서 해결하였는데, dmap값을 기준으로 dp[n] -> val(x)=n인 x 중 최솟값으로 갱신하였습니다. 조금 더 풀어서 점화식으로 설명하자면, dp[1] = "()" dp[2] = "{}" dp[3] =.. [BeakJoon 2618] 경찰차 안녕하세요. 이번 포스팅에서는 백준 2618번 경찰차 문제를 풀어보도록 하겠습니다. 해당 문제는 https://www.acmicpc.net/problem/2618 2618번: 경찰차 첫째 줄에는 동서방향 도로의 개수를 나타내는 정수 N(5 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 처리해야 하는 사건의 개수를 나타내는 정수 W(1 ≤ W ≤ 1,000)가 주어진다. 셋째 줄부터 (W+2)번째 줄 www.acmicpc.net 위 링크에서 확인하실 수 있습니다. 우선 이 문제는 굉장히 어려운 문제입니다. 그 이유는 문제의 제한입니다. 보통 이런 문제는 int go(int orderIdx, int firstCar, int secondCar) { if(orderIdx == w) return 0; int& .. [BeakJoon 16235] 나무 재테크 안녕하세요. 이번 포스팅에서는 백준 16235번 나무 재테크 문제를 풀어보겠습니다. https://www.acmicpc.net/problem/16235 16235번: 나무 재테크 부동산 투자로 억대의 돈을 번 상도는 최근 N×N 크기의 땅을 구매했다. 상도는 손쉬운 땅 관리를 위해 땅을 1×1 크기의 칸으로 나누어 놓았다. 각각의 칸은 (r, c)로 나타내며, r은 가장 위에서부터 www.acmicpc.net 해당 문제는 위 링크에서 확인하실 수 있습니다. 우선 이 문제를 풀기 위해 별도의 알고리즘을 많이 고민하실 필요는 없습니다. 해당 문제를 시뮬레이션으로 구현하시면 되는데, 문제는 이 문제의 제한이 빡빡합니다. 시간제한이 0.3초라서, 매번 sort를 하기 어렵습니다. sort를 하는 이유는 어린 나.. [BeakJoon 17070] 파이프 옮기기1 안녕하세요. 이번 포스팅에서는 백준 17070 파이프 옮기기1을 풀어보도록 하겠습니다. https://www.acmicpc.net/problem/17070 17070번: 파이프 옮기기 1 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 www.acmicpc.net 이 문제는 분류상 DP긴 한데, 저는 이 문제의 경우 역행하는 경우의 수도 없고, 고려해야할 경우의 수도 최대 16x16x7이기 때문에 BFS로 풀었습니다. #include using namespace std; int n, res, board[17][17]; const int dir[3.. [BeakJoon 1700] 멀티탭 스케줄링 안녕하세요. 이번 포스팅에서는 백준 1700번 멀티탭 스케줄링 문제를 풀어보도록 하겠습니다. 해당 문제는 https://www.acmicpc.net/problem/1700 1700번: 멀티탭 스케줄링 기숙사에서 살고 있는 준규는 한 개의 멀티탭을 이용하고 있다. 준규는 키보드, 헤어드라이기, 핸드폰 충전기, 디지털 카메라 충전기 등 여러 개의 전기용품을 사용하면서 어쩔 수 없이 각종 전 www.acmicpc.net 위 링크에서 확인하실 수 있습니다. 그리디 문제이고, 멀티탭에서 어떠한 원소를 뽑는 것이 최선일까를 생각하는 것이 어려운 문제입니다. 우선 직관적으로 생각했을 때, 당연히 이후 순번에서 등장하지 않는 멀티탭을 제거하는 것이 제일 중요합니다. 2 7 2 3 2 3 1 2 7 이러한 입력이 주어졌.. [BeakJoon 15685] 드래곤 커브 안녕하세요. 오늘은 백준 15685 드래곤 커브 문제를 풀어보도록 하겠습니다. 해당 문제는 https://www.acmicpc.net/problem/15685 15685번: 드래곤 커브 첫째 줄에 드래곤 커브의 개수 N(1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 드래곤 커브의 정보가 주어진다. 드래곤 커브의 정보는 네 정수 x, y, d, g로 이루어져 있다. x와 y는 드래곤 커 www.acmicpc.net 위 링크에서 확인하실 수 있습니다. 처음에 이 문제를 보았을 때 회전을 어떻게 배열에 주어야 할지, 시작점과 끝점을 어떻게 설정할 지에 대해 고민을 했었는데요. 사실 이 문제는 과정에서 회전을 하고 이어 그리는 부분이 필요가 없습니다. 왜냐하면 어디로 진행할 지 방향이 정해지면, .. 이전 1 2 3 다음
