돌이 코딩하는 방

문제 링크 : www.acmicpc.net/problem/19857 문제 풀이 이 문제를 딱 보고나서, 당연히 이 문제는 greedy or DP 느낌의 문제라고 생각이 들었다. 하지만 조금 더 고민을 해보니 DP라고 할 만한 요소가 하나도 존재하지 않다는 것을 깨달았다. 그리고 나서는 '만들 수 있는 최댓값'이라는 단어에 집중을 했고, 어떤 값이 만들 수 있는지 판별하는 것이 훨씬 쉬울 것 같아 파라메트릭 서치를 쓰는 방향으로 설정하였다. 마지막에 광물 i를 남길 수 있을까? 직접 i를 역추적 해보면서 생각하였다. 어떤 광물 j를 만들기 위해서는 0~j-1가 하나씩 존재하면 된다. j 보다 큰 광물은 하나도 쓸모가 없다. j이상의 광물을 가장 잘 쓰는 방법은 그 광물 하나로 0짜리 광물 하나는 만드는 것..

문제 링크 : www.acmicpc.net/problem/19938 문제 소개 두 가지 행동을 해야하는 투스텝 문제이다. 1. 트리에 적당히 라벨링한다. 2. 시작 라벨, 끝 라벨만 보고, 가야하는 바로 다음 라벨을 구한다. 이때 1->2 로 전달되는 정보는 시작,끝,주위 라벨 뿐이다. 문제 풀이(+의식의 흐름) part 1. 문제를 읽으면서 생각한 것들 - 1차 생각, 해야할 일들 정리 X 문제 자체를 이해하는데 꽤나 오랜 시간이 걸렸다. 결과적인 부분은 위의 내용밖에 없는데, 전체적인 프로그램의 작동방식의 흐름을 이해하지 못해서 힘들었다. 1과 2 사이의 정보를 프로그램을 꺼서 데이터를 날리고 다시 켜서 실행시키는 방식인 것을 제대로 알지 못했다. part 2. 출발지와 목적지. 결국 중요한 것은 1..

문제 링크 : www.acmicpc.net/problem/19935 문제 소개 k 판의 게임을 진행한다. 각각의 게임은 m개의 숫자카드중 일부가 있는 n개의 카드 세트에서 1개씩을 뽑는다. 주최측이 원하는대로 수를 선정하고, 그 수와 뽑은 n개의 수의 차이의 절댓값 만큼 점수를 얻는다. 이때 주최측은 얻는 점수가 최소화 되도록 수를 선정한다. 이때 k 판을 진행하면서 얻는 점수가 최대가 되도록 각 판에서 뽑을 숫자카드를 설정하고, 이때 얻을 점수를 구하여라. 문제 풀이(+의식의 흐름) part 1. 문제를 읽으면서 생각한 것들 - 1차 생각, 해야할 일들 정리 이 문제를 시작한 이유. 1분 보고 나서 DP 느낌이 확 왔다. 뭔가 난이도의 대부분은 관찰이고, 구현은 그렇게 어렵지 않을 것 같다는 생각이 크..

문제 링크 : www.acmicpc.net/problem/19934 문제 소개 인접행렬이 주어진다. 이때 모든 값은 3이하이다. 이때 주어진 인접행렬을 만족하는 트리가 있는지 판단하고, 있다면 그 트리를 보여라. 문제 풀이(+의식의 흐름) part 1. 문제를 읽으면서 생각한 것들 - 1차 생각, 해야할 일들 정리 경로의 가짓수로 가능한 것은 0,1,2,3 인데, 각각의 경우에 대해서 두 노드가 어떤 식으로 배치 되어 있을지에 대해서 생각을 해보았다. 0가지일때: 둘은 같은 컴포넌트에 존재하지 않는다. 또한 0 이 아닌 두 노드는 항상 같은 컴포넌트에 존재해야 한다. 따라서 우리는 경우의 수가 0이 아닌 모든 쌍에 대해서 union &find 를 이용하여 같은 컴포넌트로 묶을 수 있다. 이때 같은 컴포넌..

문제 링크 : www.acmicpc.net/problem/1167 문제 태그 더보기 DFS 문제 풀이 트리의 한 정점에서 가장 먼 정점을 잡는다. 그러면 그 정점을 트리의 지름의 한쪽 끝이 된다. 따라서 찾은 정점에서 시작하여 가장 먼 정점까지의 거리를 구하면 그 거리가 트리의 지름이 된다. - 임의의 한 점에서 가장 먼 점을 잡으면 그 점은 항상 트리의 지름의 한 쪽 끝이 되는가? 아니라고 해보자. 아래의 그림에서 초록이 주황, 노랑보다 길어야 하는데, 그럼 주황-노랑으로 이어진 길이 지름인 것에 모순이다. 따라서 위의 가설은 참이다. 따라서 풀이는 정당하고, 어떤 한 점에서 나머지 모든 점까지의 거리를 구하면 되는데, 이는 다익으로도 할 수 있지만, 트리에서는 dfs로 간단하게 해결할 수 있다. 코드..

후기 글을 쓰던 도중에 결과가 떠서 급하게 바로 이어서 쓰는 글이다. 결과는 이렇다. 총 시험인원은 654명 정도였고, 내가 7등을 기록하였다. 6등은 441점이고, 5등은 443점이다. 결국 마지막에 못긁은 17번 테케 4점이 너무 아쉽게 작용하게 된 것이다. 왜냐하면 금컷이 1%. 즉 6등이기 때문이다. 만약 그냥 은상이라고 알려주었으면 진짜 너무 억울했을텐데, 내가 전국 7등이라는 것을 입증할만한 수치가 같이 딸려와서 다행이다... 흠.... 휴.... 사실 이렇게 말은 하지만 지금 미친듯이 기쁘다. 지난 2년동안 메이저 대회에서의 나를 생각하면 정말 끔찍했다. 사실 코딩에서의 디테일이 많이 부족했다고 할 수 있다. 어쩌면 최근에 실력이 많이 상승했다고 할 수 도 있는 것 같다. 아무튼 정말정말 행..

정말 중요한 시험... 입시로 굉장히 바쁜 때였지만, 포기할 수 없었다. 2년간 1차 탈락을 한 슬픔을 만회할 수 있는 마지막 기회였다. 그래서 최근 1주일동안 열심히 준비를 했다. 시간이 없기 때문에 1교시 문제는 다루지 않고 2교시 실기 문제만 다루려고 한다. 1교시를 1~2개 빼고 다 맞은 것 같아서 기분이 좋은 상태로 시작하였다. 특히 비버챌린지 4번을 1초 남기고 137의 경로를 찍고 제출을 해서 굉장히 행복한 상태였다. 문제는 여기서 볼 수 있다. 1번 박 터트리기 풀이 서로 다른 수 M개의 합으로 어떠한 수를 표현할때는 연속된 M개의 수로 표현이 가능하거나 중간에 1개를 띄고 M개로 표현이 가능하다. 즉 4개의 합으로 14를 표현할때는 2 3 4 5, 15를 표현하려면 2 3 4 6, 16을..

앞으로 이 글은 블로그 메인페이지 맨 아래 공지사항에서 지속적으로 확인이 가능합니다. 알고리즘 & 자료구조 복기 글 시작 글 stonejjun.tistory.com/7 BFS 와 DFS stonejjun.tistory.com/8 다익스트라 stonejjun.tistory.com/15 최소 스패닝 트리 stonejjun.tistory.com/19 union & find stonejjun.tistory.com/21 이분 매칭 stonejjun.tistory.com/46 파라매트릭 서치 stonejjun.tistory.com/61 LCA stonejjun.tistory.com/63 Mo's algorithm stonejjun.tistory.com/79 SCC stonejjun.tistory.com/84 코사라..

Codeforces 다시 떡락한뒤에... div1에서는 올리지 못했다. #668 div1이 굉장히 아쉬웠다. /2 만 안했어도 D를 푸는 것이었기 때문에 진짜 쭉 떡상할 수 있었다. 하지만 실패했다. 2000 초반이었지만 한동안 div1을 볼 수가 없었다. only div2만 한가득. 최대한 존버를 하다가 비장의 한 번을 터트려서 쭉 올라가기로 마음먹었다. #669에서 그 컨트롤을 실패해서 그냥 망해버릴뻔 했다. 2110 박제가 될 뻔 했으나 환상적인 D 시스페일로 인해서 2050 쯤에 세워놓을 수 있었다. 그 후 #670에서 38등 떡상에 성공! 후기글은 여기서 볼 수 있다. 현재 레이팅은 2181. 한국 60등, 세계 1700등대, 교내 5등을 기록했다. BOJ 1000문제 달성!!!! 요즘 정말 꾸..

문제 링크 : www.acmicpc.net/problem/5916 문제 태그 더보기 HLD ,segment tree lazy propagation 문제 풀이 문제를 보자... 1번 트리다. 2번 쿼리가 주어진다. 3번 그 쿼리가 경로 쿼리이다.... 아무리 봐도 이 문제는 HLD를 사용하는 문제라고 밖에는 생각이 들지 않는다. 경로에 모두 하나씩 심기 때문에 segment tree part에서 lazy propagation을 같이 섞어주면 문제를 해결할 수 있을 것 처럼 보인다. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 4..