알고리즘 썸네일형 리스트형 앳코더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비슷한 문제.. 이전 1 2 3 4 ··· 14 다음
