알고리즘/atcoder90제 썸네일형 리스트형 앳코더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 - 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 - 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 .. 앳코더90 - 026 - Independent Set on a Tree（★4） https://atcoder.jp/contests/typical90/tasks/typical90_z 026 - Independent Set on a Tree（★4）AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.atcoder.jp 7레벨은 이제 건너뛰도록 하자 하나의 트리 그래프가 주어질때 인접하지 않은 정점의 집합을 N/2개 출력하시오.예제이다. 정점 하나를 잡고 시작해서 깊이를 기준으로 깊이가 짝수일때만 vector에 넣어서 정렬 후 출력했더니 테스트케이스 일부가 틀렸었다. 다시 생각해보니 내가 시작 정점을 1로 한거였는데 1이 끝이 아니.. 앳코더90 - 024 - Select +／- One（★2） https://atcoder.jp/contests/typical90/tasks/typical90_x 024 - Select +／- One（★2）AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.atcoder.jp 길이가 N인 두개의 배열 A, B가 있다. 배열 A에서 특정 index의 원소를 선택하여 +1, 또는 -1 하여 배열 B를 K번 이내에 만들 수 있는가?를 판별하는 문제이다. +1 또는 -1 한다는 것은 어떻게든 값을 만들 수 있는 것이고 K번 이내에 가능한지 만 판별하면 되는 것이다. 0번째 원소가 3, 5라고 할때 3을 5로 만들기.. 이전 1 2 3 4 다음
