준카판다

https://www.acmicpc.net/problem/2156 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규 www.acmicpc.net 전형적인 dp문제이다. 내가 푼 방식과 다르게 더 효율적으로 풀 수 있는 방법이 존재해서 그 방법에 대해 소개하려 한다. 방법 1. 2차원 배열 2차원 배열을 이용하여 몇번째로 연속으로 마신 잔인지 표시하는 것이다. [i][0]은 i번째 잔이 첫번째로 마신 잔인 경우의 최대 값. [i][1]은 i번째 잔이 연속으로 두번째로 마신 잔인 경우의 최대 값이 저장되는 것이다. #include #includ..

https://www.acmicpc.net/problem/2468 2468번: 안전 영역 재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 www.acmicpc.net 기본적인 bfs문제이다. 하지만, bfs가 아닌 union, find로도 해결 가능한 문제이다. 이것을 이해하는데 오랜 시간이 걸렸다. 그 방법에 대해서 알아보자. 방법 1. bfs bfs를 100번 돌리면 된다. 근데 딱봐도 비효율적으로 보이지 않는가? 이것을 보완해주는 것이 union, find이다. #include #include int main(void) { int N, M[100][100], R..

https://www.acmicpc.net/problem/7562 7562번: 나이트의 이동 체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 www.acmicpc.net 기본적인 bfs문제이다. 주어진 값을 bfs하여 최단 거리를 출력하면 되는 문제이다. 이 문제의 특성을 이용하면 보다 효율적인 방법으로 해결할 수 있는 것이 존재하여 그 방법을 소개하려 한다. 솔직히 방법 1과 방법2의 방식이 별 다르지 않다. 방법 1은 T만큼 계속해서 bfs를 돌리는 것이고, 방법 2는 bfs를 한번 진행해, 그 값을 이용해 출력하는 것이다. 방법 1. bfs 진짜 T만큼 bfs..

https://www.acmicpc.net/problem/11286 11286번: 절댓값 힙 첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 0이 아니라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net 그냥 전형적인 우선순위 큐 문제이다. 방법이 2가지가 존재해서 그 방법을 소개하려고 글을 작성한다. 방법 1. 우선순위 큐 2개 사용. 방법 2. 우선순위 큐 정렬 기준 변경. 우선순위 큐에 대해 자세히 알고 싶다면 다음 글을 참고하자. https://jhcard.tistory.com/69 [C++] queue 라이브러리 queue는 list자료구조와 매우 유사하다. list..

https://www.acmicpc.net/problem/6064 6064번: 카잉 달력 입력 데이터는 표준 입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터는 한 줄로 구성된다. www.acmicpc.net ㅋㅋㅋㅋ 이 문제 쉽게 생각하면 쉽다. 하지만, 이 문제를 어렵게 풀려면 어렵게 풀 수 있다. 2가지 방법으로 해결할 수 있다. 방법 1. 일반적인 유클리드 호제법을 이용한 최대공약수, 최소공배수를 이용한 문제 해결 방법 2. 유클리드 확장을 이용한 중국인의 나머지 정리 사용이다. 방법 2의 경우 중국인의 나머지 정리를 처음 접하여 혼란스럽기도 하였고, 유클리드 확장이라는 새로운 알고리즘을 접하게 되..

https://www.acmicpc.net/problem/1309 1309번: 동물원 첫째 줄에 우리의 크기 N(1≤N≤100,000)이 주어진다. www.acmicpc.net 전형적인 DP문제이다. 하지만, DP를 조금만 변형하면 더 효율적인 방법으로 구현할 수 있어 그 방법을 소개할려고 한다. dp방식이다. 빨간색이 dp[2][0] 파란색이 dp[2][1] 초록색이 dp[2][2] 이 된다. N = 1일때의 dp의 상태에서 힌트를 주었는데 뒤쪽의 3개의 배열의 의미는 가장 아래에 있는 동물원에 사자가 아예 없는 경우가 [N][0], 왼쪽에 있는 경우가 [N][1], 오른쪽에 있는 경우가 [N][2]가 된다. 이것을 가지고 계산을 해보면, 가장 아래가 아무것도 없는 경우가 N-1의 0, 1, 2를 더한..

https://www.acmicpc.net/problem/5014 5014번: 스타트링크 첫째 줄에 F, S, G, U, D가 주어진다. (1 ≤ S, G ≤ F ≤ 1000000, 0 ≤ U, D ≤ 1000000) 건물은 1층부터 시작하고, 가장 높은 층은 F층이다. www.acmicpc.net 문제를 보면 기본적으로 bfs로 해결 가능한 문제이다. 하지만, bfs를 사용하지 않고도 문제를 해결할 방법이 존재한다. 그 방법을 소개하려 한다. 방법 1. bfs 기본적으로 할 줄 안다고 판단하기 때문에 코드만 보여주겠다. #include #include int main(void) { int F, S, G, U, D, R = 0; scanf("%d %d %d %d %d", &F, &S, &G, &U, &D..

https://www.acmicpc.net/problem/1325 > N >> M; while (M--) { std::cin >> A >> B; P[B].push_back(A); } for (int i = 1; i