알고리즘 109

2025 상반기 전남대학교 PIMM 알고리즘 파티 후기

서론올해에도 이전과 같은 멤버들끼리 백준에 대회 개최를 준비하게 되었다. 이제는 대회 출제 준비를 한지 2년차 노하우가 쌓였다고 하면 쌓였다고 할 수 있지만, 문제를 출제하는 것도 지문을 준비하는 것도 서로의 문제를 검수하는 것도 이전보다 늦어졌다고 생각했다. 하지만, 정말 늦었다라고 할 수는 없었고 여러 문제들을 생각해내고 부족한 문제들을 쳐내고 보완하고 등의 과정을 통해서 각자 출제할 문제를 선정하게 되었다. 대회 문제문제 후기내가 세팅한 두개의 문제는 A, B, H번이다. 항상 들었던 생각인데, 내가 A, B번을 내지 않으면 우리 대회에 브론즈, 실버는 없다고 생각했다. 이번에도 골드컵이 될번 한 걸 잘 막았다고 생각했다. A번 치매예방수칙 3.3.3우선 이 문제는 문제 출제를 앞두고 정말 산책을 ..

알고리즘/후기 2025.04.05

앳코더90 - 036 - Max Manhattan Distance(★5)

https://atcoder.jp/contests/typical90/tasks/typical90_aj 036 - Max Manhattan Distance(★5)AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.atcoder.jp N개의 x,y로 점의 좌표가 주어지고 Q개의 쿼리가 주어진다. 쿼리에 해당하는 좌표와 가장 맨해튼거리가 먼 점의 거리를 구하라. 문제를 읽고 몇 분동안 생각해보다가 내가 아는 알고리즘에서는 풀 수 있는 방법이 없는것 같아 해설을 봤는데, 해설코드로도 이해가 안되서 gpt와 함께 분석까지 했다. 우선 내가 접근한 방식은 ..

앳코더90 - 034 - There are few types of elements(★4 )

https://atcoder.jp/contests/typical90/tasks/typical90_ah 034 - There are few types of elements(★4)AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.atcoder.jp N개의 원소가 주어질때 포함된 요소가 K개 이하인 연속된 부분수열의 길이를 구하라.7 21 1 2 2 3 3 4 로 주어지면 2개이하인 연속된 부분수열로 1,1,2,2 / 2,2,3,3 으로 최대길이는 4다. N의 최대가 10만개이므로 모든 경우의수를 계산하는 N^2의 방법으로는 불가능하다. 이를 O(N..

앳코더90 - 033 - Not Too Bright(★2)

https://atcoder.jp/contests/typical90/tasks/typical90_ag H, W가 주어졌을 때, LED 켜진 개수를 최대화 하는 문제이다. 조건으로는 2*2 구간에 켜져있는 LED가 1개만 있게 키는것이다. 조금 생각해봤을 때, 그리디한 접근으로 2*2에 불이 켜져있게 하려면 왼쪽 위부터 차근차근 불을 키면된다. 수식으로 정리하면 (H+1)/2 * (W+1)/2 이다.  이렇게 제출하니 틀렸다고 나오자 corner케이스가 있나 하고 검토를 해봤지만 찾을 수 없어서 몇개의 테캐나 통과를 못했는지 보러갔는데, corner1~10.txt 정도의 케이스를 통과를 못했다. 그래서, 설마 1칸짜리면 LED가 빼곡히 들어가도 되나? 싶었다. 조건이 2*2구간 안에 켜져야 하기 때문에 1..

앳코더90 - 032 - AtCoder Ekiden(★3)

https://atcoder.jp/contests/typical90/tasks/typical90_af 032 - AtCoder Ekiden(★3)AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.atcoder.jp 31번은 스프라그 그런디 문제 같은데 문제 이해가 잘 안되서 일단 킵이다. N명의 선수가 주어지고 바통달라기를 한다. N^2의 행렬로 세로는 N번째 선수가 가로는 N번째 구간을 가는데 걸리는 시간을 의미한다.1 10 10010 1 100100 10 1 이라면 1번선수는 1번구간 2번구간 3번구간을 가는데 1 10 100 만큼 시간이 ..

앳코더90 - 030 - K Factors(★5)

https://atcoder.jp/contests/typical90/tasks/typical90_ad 030 - K Factors(★5)AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.atcoder.jp 2이상의 N이하의 정수 중에서 소인수가 K개이상인 정수의 개수를 구하라. 난이도가 왜 별 5개 짜리문제인지는 모르겠다. 난이도만 보고 수학적인 뭔가를 써야 되나 싶었다. 우선 각 N마다 소인수분해를 해서 저장하는 방식이 문제의 의도는 아닐것이다. 예전에 이런 비슷한 문제를 백준에서 본적이 있어서 쉽게 접근할 수 있었던 것 같다. 에라토스테네스..

앳코더90 - 029 - Long Bricks(★5)

https://atcoder.jp/contests/typical90/tasks/typical90_ac 029 - Long Bricks(★5)AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.atcoder.jp 크기가 W인 가로로 이루어진 공간에 N개의 벽돌을 쌓는다.범위 l, r이 주어질때 l~r까지 벽돌을 하나씩 놓는다. 놓는 위치에 이미 벽돌이 있다면 그 위에 쌓는데 범위 내에서 가장 높은 벽돌의 높이에서 하나 쌓은만큼 나머지 범위도 그만큼 쌓는다.ex) 1 3 1 상태에서 범위가 1 2 면 4 4 1이 된다. 3+1 을 1,2에 둘다 적용..

14474번 : 尾根 (Ridge)

https://www.acmicpc.net/problem/14474 H, W 크기의 그래프가 있다. 이는 해당 부분의 높이를 의미하며 물은 높이가 높은곳에서 낮은곳으로 흐른다. 어떤 구역에 비가 내렸을 때, 최종적으로 비가 고이는 곳이 2개이상인 지역의 개수를 구하라. 3 55 3 8 2 149 10 4 1 1312 7 11 6 15예제 2번의 오른쪽아래 15, 13 부분을 보면 각 부분에서 비가 내렸을 때 1로 비가 고이지만 비가 고이는곳이 한 곳이기 때문에 해당하지 않는다. 12의 경우에는 7, 3에서 비가 고인다. 순서대로 접근해보자1. 우선 비가 고이는 장소의 특징은 상하좌우가 자신보다 높은 곳이다. 한 곳이라도 자신보다 낮은 곳이 있을 경우 그 부분으로 흘러가기 때문이다. 이를 전체 탐색을 하자..

앳코더90 - 028 - Cluttered Paper(★4)

https://atcoder.jp/contests/typical90/tasks/typical90_ab 028 - Cluttered Paper(★4)AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.atcoder.jp N개의 색종이가 주어진다. 색종이의 왼쪽 위 그리고 오른쪽 아래의 좌표가 a, b, c, d로 주어진다. 색종이를 N개 두었을 때, k=1~N까지 종이가 정확히 k 겹쳐진 부분의 면적을 출력하라. 문제를 보면 2차원 누적합 관련 문제임을 유추할 수 있다. https://www.acmicpc.net/problem/11660비슷한 문제..

앳코더90 - 027 - Sign Up Requests (★2)

https://atcoder.jp/contests/typical90/tasks/typical90_aa 027 - Sign Up Requests (★2)AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.atcoder.jp Lowcoder라는 사이트를 다카하시군이 만들었다. N개의 문자열이 주어질때, i일에 문자열 S의 입력이 등록된다. 이미 등록됐을 경우에는 무시하고 새로 등록할시 등록한 날짜를 출력한다. set자료구조를 이용하면 쉽게풀린다. #define _CRT_SECURE_NO_WARNINGS#include #include #include ..