코딩/BOJ (6) 썸네일형 리스트형 BOJ 4013 : ATM 문제 링크 : https://www.acmicpc.net/problem/4013 4013번: ATM 첫째 줄에 교차로의 수와 도로의 수를 나타내는 2개의 정수 N과 M(N, M ≤ 500,000)이 차례로 주어진다. 교차로는 1부터 N까지 번호로 표시된다. 그 다음 M개의 줄에는 각 줄마다 각 도로의 시작 교차 www.acmicpc.net SCC 응용 문제입니다. 간단해 보이지만 처리해줄게 많고 구현량이 많아 생각보다 어려웠습니다. 문제를 간략하게 정리하면, 그래프가 주어지며 각 정점은 현금을 가지고 있습니다. 이때, 시작 정점과 도착가능한 정점이 주어질 때 인출할 수 있는 현금의 최댓값을 출력해야 합니다. 현금의 액수는 0이상의 정수이기 때문에 하나의 SCC에서는 모든 정점의 현금을 인출하는 것이 이득.. Problem Solving Review #2 [06.04~06.06] 기회가 생겨 3일동안 많은 문제를 풀게 되었습니다. 문제가 많았고 다른 대회들이나 기말고사와 겹치다 보니 많이 늦어졌지만 좋은 문제들이 많았기에 정리해서 올리게 되었습니다. BOJ 20960. Po 아이디어는 간단하지만 이를 파악하기가 어려웠습니다. 결론적으로는 스택을 이용하여 간단하게 해결할 수 있습니다. 입력받은 배열 \(a\)를 순차탐색하면서 스택에서 \(a[i]\)보다 큰 원소들을 제거하고 알맞은 위치에 삽입해주면 됩니다. 다만, 스택에 이미 \(a[i]\)와 같은 값을 가진 원소가 존재한다면 \(a[i]\)값을 만들기 위해 추가적인 increasing의 작업을 거칠 필요가 없기 때문에 스택에 \(a[i]\)를 추가해주지 않아도 됩니다. 결과적으로 스택에 \(a[i]\)를 삽입한 횟수를 세어 출력.. Problem Solving Review #1[2022.3월 1주 - 3월 3주] 3월의 시작부터 3주차까지 풀었던 문제들과 개념들을 정리해보고자 합니다. 앞으로 문제를 풀어나가는데 있어서도 정리해둔 것이 도움이 될 것 같고, 알고리즘을 자꾸 까먹는 저에게 가장 필요한 습관이 아닐까 생각이 들어 지속적으로 작성하려고 합니다. BOJ 2631. 줄세우기 KOI 2001 > 중등부 2번 간단한 관찰을 통해 한 가지 사실을 발견한다면 해결할 수 있지만, 처음 볼 때는 의외로 관찰이 떠오르지 않았습니다. LIS(Longest Increasing Sequence) 에 포함되는 아이들을 고정해놓고 나머지 아이들을 움직여야지만 최소의 아이들을 옮길 수 있기 때문에 간단히 DP로 LIS를 구현하여 해결할 수 있습니다. #include using namespace std; int n, a[202], .. BOJ 15972 : 물탱크 문제 링크 : https://www.acmicpc.net/problem/15972 15972번: 물탱크 세로 길이가 N, 가로 길이가 M, 높이가 H인 물탱크가 있다. N, M, H는 모두 양의 정수이다. 은 세로 길이가 2, 가로 길이가 3, 높이가 5인 물탱크 모양을 보여준다. 에서 보듯이 물탱크 www.acmicpc.net 우선순위큐와 BFS를 이용한 문제입니다. 결론적으로 물이 마지막에 빠져나가는 구멍은 바깥과 연결된 구멍일 것입니다. 따라서, 역으로 바깥과 연결된 구멍이 있는 칸부터 우선순위큐에 저장합니다. 우선순위큐에서는 {물의 높이, 칸의 x 좌표, 칸의 y 좌표}를 저장하며 물의 높이에 따라 오름차순으로 정렬됩니다. 이후 우선순위큐에서 BFS를 돌리는 과정에서 관찰이 필요합니다. 현재 칸과.. KOI 2021 2차 고등부 2번 풀이(그래프 균형 맞추기) https://www.acmicpc.net/problem/22344 22344번: 그래프 균형 맞추기 N개의 정점과 M개의 간선으로 구성된 무방향 단순 연결 그래프가 있다. 그래프의 정점들에는 1 이상 N 이하의 서로 다른 자연수 번호가 붙어 있고, 간선들에는 1 이상 M 이하의 서로 다른 자연수 www.acmicpc.net 개인적으로 1번 DP 생각해내는게 2번 풀이보다 어려웠다 2번 문제 해석과정에서 연립방정식을 생각해낼 수 있고, 이를 확장시키는 방식이다 먼저, 문제에서 주어진 예제를 해석해보았다. 왼쪽과 같은 그래프가 주어졌을 때 (1)번 정점의 값 C1을 기준으로 잡았을 때, 간선의 값을 반영하여 각 정점의 값을 표현해보면 C3 = 5 - C1 C5 = 3 - C3 = C1 - 2 C2 = -4.. KOI 2021 2차 고등부 1번 풀이(헬기 착륙장) https://www.acmicpc.net/problem/22348 22348번: 헬기 착륙장 각 테스트 케이스에 대해, 한 줄에 하나씩, 빨강 페인트 a통과 파랑 페인트 b통만을 이용해 만들 수 있는 서로 다른 헬기 착륙장의 수를 109 + 7로 나눈 나머지를 출력한다. www.acmicpc.net 내 2차 대회 시간을 날려먹은 주범.. 수학 문제가 나오면 규칙을 찾을려고 하는 편인데 규칙이 잘 찾아지지 않다보니 시간을 많이 소비했었고 멘탈에도 안좋았던 문제이다 결론적으로는 DP 테이블을 만들어야지 풀이가 보이는 문제였다 먼저, 착륙장의 크기가 \(n\)일 때 필요한 페인트의 양은 \(i(i+1)/2\)이다 빨강 페인트를 \(x\)통 사용하였다면 파랑 페인트는 \(i(i+1)/2-x\)통이 필요할 것이.. 이전 1 다음
