본문 바로가기

전체 글

 (78)
최근 MBTI 약식검사 결과 망했다 사회생활 하기는 이미 글러먹었다 몇 주 사이에 더 극단적이 됐다 살려줘
INTP's Life 대한민국에서 희귀유형 천연기념물 intp로 살아오면서 느낀 점(내 성격이 특이하다고 느낀 것들?)들을 생각날 때마다 간단하게 적어보기로 했다. 그와 별개로 내가 느끼고 쓰고 싶은 잡설들도 포함시키려고 한다. 일기장처럼. 수시로 업데이트 예정. - 잘 때 너무 오래 걸린다. 졸린데 오만 생각이 머리를 꽉 채워서 자기도 싫고 자지도 못한다. - 말하다 혀가 많이 꼬인다. 내 입이 내가 말하고 싶은 속도를 못 따라간다. 뇌는 두 번째 문장을 시작했는데 입은 첫번째 문장을 말하고 있으니 문장이 섞인다. 반대로 어떤 단어 쓸지 고민하면서 말할땐 가끔 두 단어가 섞여서 나온다. - Random facts의 화신. 일생을 위키질로 보낼 것 같다. -INFP나 ENTP같은 사람들이 이런 잡소리같은거 굉장히 잘 받아준다..
PS: 뉴비를 위한 Simulated Annealing 입문 (2) INTRO 국내에서 가장 널리 사용되는 온라인 저지인 BOJ에는 Simulated Annealing으로 풀 수 있는 유명한 문제가 하나 있습니다. 바로 동전 뒤집기 2 (https://www.acmicpc.net/problem/2582) 입니다. 많은 사람들이 KOI에도 시뮬레이티드 어닐링 같은 특수한 알고리즘을 시용해서 푸는 문제가 나오냐고 의아해 하는데, 저 당시에는 서브태스크가 아닌 테스트 케이스 당 부분점수가 있었고, 따라서 정해가 적절한 가지치기를 동반한 백트래킹이었다고 추측해 볼 수 있을 것 같습니다. 하지만, 고생고생해서 백트래킹에 휴리스틱 함수를 적용시키는 것 보다는 시뮬레이티드 어닐링을 배워서 써먹는 쪽이 아무래도 훨씬 빠르겠죠. 시뮬레이티드 어닐링은 이러한 종류에 문제에 더 일반적으로 ..
PS: 뉴비를 위한 Simulated Annealing 입문 (1) INTRO PS에서 우리가 푸는 평범한 알고리즘 문제들은 결정론적 문제입니다. 이 말은, 이미 출제자에 의해서 밝혀진 고정된 시간 안에 동작하는 해법이 있고, 우리는 그 해법을 찾아서 구현하기만 하면 된다는 뜻입니다. 그렇지만 NYPC 예선에서 나오는 출력 파일 문제라던가, IOI의 "그 문제"인 nowruz로 대표되는 Output Only 문제, Topcoder에서 진행되는 Marathon Match 등에서는 완벽한 최적해를 찾아내는 것이 불가능하기도 합니다. 이럴 때에는 많은 사람들이 휴리스틱 알고리즘을 사용합니다. 사실 휴리스틱 알고리즘이라고 하면 어떤 특정한 알고리즘을 지칭하는 것이 아닌데, 보통 저는 휴리스틱을 완전 탐색을 할 때 속도 향상을 위해 사용하는 일반적인 휴리스틱과 전역에서 최적점과 ..
[BOJ] 13309 트리 문제 링크: https://www.acmicpc.net/problem/13309 13309번: 트리 표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 트리의 정점의 개수와 질의의 개수를 나타내는 두 정수 N과 Q (1 ≤ N, Q ≤ 200,000)가 주어진다. 다음 N-1개의 줄의 i번째 줄에는 정점 i+1의 부모 정점을 나타내는 정수 a가 주어진다 (1 ≤ a ≤ N). 다음 Q개의 줄 각각에는 세 정수 b, c, d가 주어진다. d = 0이면, b와 c를 연결하는 경로가 존재하는 지 묻는 질의만 수행함을 의미한다. d = 1이면, b와 c를 연 www.acmicpc.net 문제 요약: 정점이 20만개인 트리가 주어진다. 이때 어떤 정점 a, b를 잇는 경로가 있는 지에 대한 쿼리 20만개에 응답..
BOJ 길라잡이 (Beta) 내년 동아리 활동을 대비해서 만들어 놓는 [BOJ를 여행하는 히치하이커를 위한 안내서]입니다. 아직 미완성이라 부족한 부분이 있습니다. 보완해야 할 것 같은 부분은 댓글로 달아주시면 감사하겠습니다. ryute.tistory.com/68 한 세트는 총 4개의 소단원으로 구분되어 있습니다. 각 소단원에는 4~5개정도의 문제가 실려 있으며, 난이도 순은 아닙니다. *가 달린 문제는 심화 문제이거나 매우 유사한 문제입니다. 알고리즘 초보 딱지를 떼기 위한 목적으로 다양한 유형의 기초 문제들을 계단식으로 학습할 수 있도록 주제들을 배치하였습니다. C를 문제 해결에 무리 없이 활용할 수 있는 수준에 도달했을 때 시작하는 것을 전제 조건으로 하였습니다. 1-1. 탐색과 정렬 (1) 1-2. 기초 자료구조 (1) 1-..
국제정보올림피아드(IOI) 겨울학교 1~5일차 후기 토론 전까지 풀지 못한 문제는 *로 표시, 후에도 풀지 못한 문제는 하나 더 붙임 1일차/ 순열과 조합 개인적으로 조합론에 매우 약해서 굉장히 힘들었던 날. 첫날이라 실습 시간이 얼마 안되어서 좀 편하긴 했다 1. comb nCm의 마지막 0의 개수를 구하는 문제. 그냥 2와 5의 개수만 세주면 된다. 5의 개수만 세면 5C1 같은 경우에서 문제가 생김. 2. divide정n각형을 삼각형/사각형으로 나누는 각각의 경우의 수를 구하는 문제. 삼각형은 카탈란이고, 사각형 같은 경우도 비슷한 논리로 $O(N^3)$ 짜리 DP를 짜주면 된다. 3. perm **길이가 n인 수열이 주어졌을 때 a_i
[CF] 100551A Connect and Disconnect 문제 링크: https://codeforces.com/gym/100551/problem/A 문제 설명: 정점 $n$개로만 이루어진 그래프에 $k$개의 쿼리가 주어지는데, 쿼리는 +, -, ? 이렇게 세 종류가 있다. +는 존재하지 않는 간선 하나를 추가하고, -는 이미 존재하는 간선 하나를 삭제한다. ?는 현재 그래프의 컴포넌트 개수를 출력한다. $n$과 $k$는 둘 다 30만 이하이다. 문제 풀이: - 쿼리가 오직 + 와 ?만 들어온다면...?Union-Find Tree를 이용해서 정점들을 쉽게 합쳐줄 수 있고, 시간복잡도는 $O(k alpha(k) )$가 되겠다. - 제거 쿼리가 추가되었을 때 만약에 정직하게 모든 쿼리들을 다 처리해 준다면...?Union-Find Tree를 그대로 첫번째 풀이에 적..

티스토리툴바