Computer_Study

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 만큼 시간이 ..

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에 둘다 적용..

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. 우선 비가 고이는 장소의 특징은 상하좌우가 자신보다 높은 곳이다. 한 곳이라도 자신보다 낮은 곳이 있을 경우 그 부분으로 흘러가기 때문이다. 이를 전체 탐색을 하자..

https://www.acmicpc.net/problem/5000  일행중 누군가가 swap에서 parity라는 의문을 제기하자. 나는 데이터 통신에서 패리티체크는 들어봤지만 다른 식으로 쓰이는 걸 처음봐서 이 문제를 추천(?) 받게 되었다. 해당 문제의 경우에는 인접한 수열 3개를 선택해서 A B C 일때 C A B 로 만들 때 수열 A로 수열 B로 만들 수 있느냐 없느냐를 뭇는 문제이다. 하나씩 swap 하는 문제들은 여럿 있지만 이러한 형태는 처음 보는 것이었다.  여기서 "순열의 홀짝성" 이라는 개념이 나온다. 특정한 순열을 1:1로 교환해서 증가하는 순으로 만드는데 N번의 시행횟수가 있을 수 있지만 해당 N의 홀, 짝 여부는 항상 동일하다 라는 것이다. 21345라는 순열을 봤을 때 12345로..

어제 Atcoder 연습겸 시간 안재고 풀어봤습니다.https://atcoder.jp/contests/abc379 Toyota Programming Contest 2024#11（AtCoder Beginner Contest 379） - AtCoderAtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.atcoder.jp  Ahttps://github.com/sjmjys954646/Algorithm/blob/master/AtCoder/ABC379_A.cpp입력받은 길이 3 짜리 문자열을 재배치하는 문제string 쓰는 방법이 기억이 안나서 어찌저찌 걸..

https://www.acmicpc.net/problem/1270 1270번: 전쟁 - 땅따먹기 첫째 줄에는 땅의 개수 n(n> tmp; v.push_back(tmp); if (count == 0) major = tmp; if (major == tmp) count++; else count--; } ll cnt = 0; rep(i, n) { if (major == v[i]) cnt++; } if (cnt

알고리즘 문제 푸는것을 포기한 것이 아니다. 잘 순항중이다. 하지만, 난이도 높은 문제에 시간을 투자하는 것도 중요하고 좋아하지만 하나 풀때마다 정리하기에 시간이 많이들고 쉬운 문제는 정리하기에 오버헤드가 크다고 생각한다. 또한, 지금은 개발 분야 공부를 하고 있기에 온라인 대회에 나왔던 쉬운 문제들을 하루에 하나씩 풀면서 살아가고 있다. 그 와중에 숙제 처럼 남겨 뒀던 문제가 있다. https://www.acmicpc.net/problem/8481 8481번: Generator Your program should print the content of the file geni.out to the standard output. Your output may contain additional white spa..

앳코더 찍먹중입니다. 퍼포가 별로좋질 않네요 A(05:00)[+1] https://github.com/sjmjys954646/Algorithm/blob/master/AtCoder/ABC308_A.cpp 3가지 조건 충족하는 지 확인하면 되는문제 ||를 &&로 잘못생각해서 한번 틀렸습니다. B(16:27) https://github.com/sjmjys954646/Algorithm/blob/master/AtCoder/ABC308_B.cpp 구현 문제 입니다. map을 사용해서 개수 세어주고 뒤에서 가격별로 처리해 줬습니다. D(45:17) https://github.com/sjmjys954646/Algorithm/blob/master/AtCoder/ABC308_D.cpp C번에서 맞왜틀 하다가 D번 넘어갔습..

근래에 solved.ac 시즌 마감 소식을 들어서 아껴놨던 스프라그그런디 문제들이랑 이분매칭 문제들을 짧은시간안에 여러개 해결해보았다. 그리고 이후로는 부족한 구현실력, dp, 기하학 쪽 육각형을 채워나갈 생각이다. 이분매칭 문제들의 핵심은 알고리즘 그 자체 보다는 그래프 디자인인것같다. 이분탐색 처럼 문제가 이분매칭이다 라는 것을 눈치채는게 중요한것 같다. https://www.acmicpc.net/problem/1671 상어의 저녁식사 P3 더보기 분류 : 이분매칭 이 문제는 읽어보면 이분매칭의 느낌을 준다. 상어가 두마리를 잡아 먹을 수 있다는 점이 열혈강호3와 비슷한 테크닉으로 해결할수 있어보인다. 하지만 문제는 예제에서 나오는 능력치가 동일한 상어이다. 이와 같은경우를 index별로 잘 정렬해서..

음 원래는 꾸준히 쓸려고 만들었는데 임팩트 있는 문제들만 정리 하려고만해도 글 쓰는걸 깜빡하게 되네요. 최근에 프로그래밍 대회 나가서 죽쓰고 와서 열심히 작성하려고합니다. 거의 한달전에 푼 문제들 리뷰 https://www.acmicpc.net/problem/1014 컨닝 P4 더보기 분류 : dp, 비트마스킹 dp[i][j]를 n번째 줄에 어떤 형태로 앉아있느냐로 정의 이때 j 는 비트마스킹으로 표현한다. 앉는것 같은경우에 해당위치의 좌 좌상단 우상단을 확인하면 앉을수 있는지 없는지 체크가 가능하다. 이를 백트래킹 처럼 끝까지 진행해주면서 경우의수를 count한다. 이 문제의 hard는 이분매칭으로만 풀린다고 하니 이분매칭 공부 이후 다시 풀어볼 예정 https://github.com/sjmjys954..