티스토리

Ryute's Note

검색하기

블로그 홈

Ryute's Note

ryute.tistory.com/m

알고리즘과 Problem Solving, 기타 일상등을 다룹니다.

구독자: 41

방명록 방문하기

주요 글 목록

[BOJ] 24973 Up Down Subsequence 문제 요약 길이가 $N$인 수열이 주어진다. 어떤 부분수열을 앞에서부터 읽었을 때 인접한 두 수가 커지면 U, 작아지면 D를 적은 문자열이 있다고 하자. 문자열 $S$가 주어질 때 부분수열을 잘 골라서 만든 문자열과 $S$의 common prefix 길이를 최대화하여라. 문제 풀이 결론부터 말하면, 다음을 반복하면 된다. 1. 문자열을 (연속한 문자 종류, 개수)로 압축한다. 2. 맨 앞이 U면 LIS, D면 LDS를 길이가 그 문자의 개수가 될 때까지 찾는다. 3-1. 만약 찾지 못한다면 LIS나 LDS의 길이(정확히는 길이-1)만큼 추가로 문자를 처리할 수 있고 그 뒤는 불가능하다. 3-2. 만약 찾는다면 연속한 문자를 모두 처리할 수 있다. LIS/LDS의 마지막 위치가 pos라고 하자. 그러면 계.. 공감수 0 댓글수 0 2023. 2. 8.
[BOJ] 23172 Equivalent Pipeline 문제 링크: [BOJ 23172](https://www.acmicpc.net/problem/23172) 문제 요약 정점이 $n$개인 가중치 있는 트리가 $d$개 있다. $vT(i,j)$를 $T$에서 $i$와 $j$를 잇는 최단경로 중 가중치의 최솟값이라고 하자. 만약 모든 $i$, $j$ 쌍에 대해 이 값이 같다면 두 트리는 동치이다. 동치 관계를 구하여라. 풀이 트리에서 가장 가중치가 작은 간선들을 생각해보자. 이 간선들을 제거하면, 트리가 여러 컴포넌트로 쪼개질 것이다. 이때 같은 컴포넌트에 있는 정점들끼리의 $vT(i,j)$ 값은 반드시 최소 가중치보다 크고, 다른 컴포넌트에 있는 정점들끼리의 값은 정확히 최소 가중치일 것이다. 따라서 두 트리가 동치이려면 최소 가중치 간선들을 기준으로 쪼갰을 때 .. 공감수 0 댓글수 0 2022. 11. 25.
[BOJ] 16711 Erasing Matrix 문제 링크: [BOJ 16711](https://www.acmicpc.net/problem/16711) 문제 요약 격자가 있다. 격자에서 인접한 두 수를 골라 임의의 수를 더할 수 있다. 격자 안의 수가 항상 음수가 되지 않게 하면서 최종적으로 모든 수가 0이 되게 하는 방법을 찾아라. 풀이 일단 가장 먼저 생각해봐야 할 점은 -1을 찍을 조건이다. 이런 식으로 격자에서 인접한 두 수를 고려하는 문제는 특성상 체스판처럼 색칠하면 이분 그래프 구조가 나오는데, 이를 활용해 볼 수 있다. 인접한 두 수에 어떤 수를 더하더라도 (흰 칸의 수 합) - (검은 칸의 수 합)은 변하지 않으므로, 이 두 값은 반드시 같아야 한다. 만약 이 값이 같다면 항상 0으로 만들 수 있을까? 가능하다. 핵심은 같은 색깔이라면 .. 공감수 1 댓글수 0 2022. 11. 25.
[BOJ] 17434 도로 청소 문제 링크: [BOJ 17434](https://www.acmicpc.net/problem/17434) 문제 요약 무방향 그래프가 있다. 교집합이 없고 방문하는 간선의 합집합이 그래프 간선 전체인 오일러 투어 2개를 구하여라. 풀이 풀이 방향을 잘못 잡으면 구데기같은 구현에 고통받게 된다. 일단 가장 먼저 생각해야 하는 건, 그래프의 홀수 차수 점 개수는 반드시 0, 2, 4중 하나여야한다는 것이다. 오일러 투어를 하나 구하고 그 간선들을 모두 제거한다고 생각해보자. 그러면 오일러 순환인 경우 홀수 차수 점 개수는 그대로고 아니라면 2개 줄어든다. 모두 지웠을 때 개수가 0이어야 하므로 이 셋 중 하나이다. 홀수점 0개 아무 오일러 순환을 하나 찾자. 그 뒤 아무데서나 적당히 끊어서 오일러 투어 2개로 .. 공감수 0 댓글수 0 2022. 11. 25.
[BOJ] 20093 Coins 문제 설명 $8 \times 8$ 크기의 체스보드가 있습니다. $A$와 $B$가 이 위에서 게임을 합니다. 각 체스보드에는 동전이 하나씩 올려져 있고, 처음 상태는 무작위입니다. $A$는 동전을 최대 한 개 뒤집어서, $0$ 이상 $63$ 이하의 정수 하나를 체스보드만 보고 $B$가 알 수 있게끔 해야 합니다. $A$와 $B$의 전략을 직접 구현해 제출하는 투 스텝 문제입니다. 문제 관찰 서브태스크 1 동전을 하나 뒤집을 수 있다는 건, 원하는 위치의 동전을 위 또는 아래로 정확히 맞출 수 있다는 것과 동치입니다. 따라서 0번 위치의 동전을 잘 뒤집어 주면 됩니다. 서브태스크 4 서브태스크 1과 비슷한 느낌으로 접근합시다. $A$가 $B$에게 전달해야 하는 정보는 정확히 6비트어치입니다. 따라서 6개의 .. 공감수 0 댓글수 0 2021. 5. 26.
[BOJ] 19677 Holy cow, Vim! (Hard) 문제 설명 생략한다. 문제 접근 이 문제를 풀기 위해서는 굉장히 많은 시행착오를 거쳐야 한다. 아래는 그 시행착오를 줄이기 위한 접근들을 단계별로 서술해놓았다. 그러나 이를 보지 않고 많은 시행착오를 겪는 것이 거의 모든 측면에서 도움이 될 것으로 보인다. 일단 lexicographical하게 정렬했을 때 명령어의 순서는 '*', '+', '-', '/', 'dup', 'input', 'jump', 'pop', 'print', 'push' 순서이다. 문제는 이 중 사칙연산과 dup은 우선순위도 빠르면서 스택에 필수적으로 하나 이상의 원소를 요구하기에, 두 명령어 .. 공감수 0 댓글수 0 2021. 4. 8.
정보올림피아드 / 알고리즘 과외 안 구합니다. 알고리즘 과외 안 합니다 현재 고려대학교 컴퓨터학과 재학 중인 김준겸입니다. 알고리즘 사이트에서는 ryute라는 닉네임을 사용 중입니다. 약 8년 정도의 알고리즘 문제 해결 경력이 있습니다. 알고리즘, 그 중에서도 특히 정보올림피아드 분야 과외를 하고자 합니다. Zoom과 Visual Studio Live를 통한 화상 과외를 주로 받습니다. 모든 세부사항은 상담을 통해 조정이 가능하니, 부담 갖지 마시고 연락 주시길 바랍니다. 코딩 테스트 수준의 과외는 별도의 특이사항이 없는 한 당분간 받지 않으려고 합니다. 연락을 많이 주시는데 받지 못해 죄송합니다. 새로 이메일 주시면 과외 다시 진행하게 될 때 먼저 연락드리겠습니다. 당분간 과외를 받지 않습니다. 어떤 일이 있어도 과외를 해야겠다 싶은 경우에만 연락.. 공감수 7 댓글수 1 2021. 2. 4.
USACO 2020 Open contest Gold 풀이 Intro PS를 거의 한달간 접었었는데, 올해 ICPC를 나갈 수 있다는 희망이 보여서 급하게 PS 재활 중입니다. 최대한 빨리 플래티넘을 안정적으로 해결할 수 있는 실력까지 올렸으면 좋겠네요. 가능할지는 아직 미지수입니다. 이 셋 푸는데도 두시간은 넘게 걸렸으니 미래가 어둡네요 :( 18874 Haircut 문제 링크 : https://www.acmicpc.net/problem/18874 문제를 요약하면 각 $j$에 대해 $j$보다 큰 수열의 원소들이 정확히 $j$로 바뀔 때, 수열의 inversion을 구하는 문제입니다. 이런 문제에서 흔히 나오듯이 $j$를 큰 수부터 작은 수까지 움직이면서 차례대로 구해봅시다. 수열의 inversion은 수열의 각 원소 $a_i$에 대해 인덱스가 $i$보다 작으면.. 공감수 0 댓글수 0 2021. 1. 4.
(임시) 2020 ICPC Seoul Regional 후기 * 페이스북에 올린 것을 급하게 그대로 올립니다. 14일날 있었던 Seoul Regional과, 그리고 리저널을 치기 위해서 노력했던 시간들에 대해 짧은 후기글을 올립니다. (긴 후기는 나중에 블로그에 올라올 것 같습니다.) 두서가 좀 없어도 이해해 주세요. 저희 팀은 결성된 지 상당히 오래 된 팀입니다. 올해 1월에 만들어졌고, 그때부터 팀연습을 몇 번 했던 것 보면 태생이 빡겜을 하기 위해 만들어진 팀이었던 것 같습니다. 저 또한 재수하려고 마음을 먹었다가 이 팀 구성이면 Semi-World Final에는 무조건 진출하겠다고 생각이 들어서 재수를 포기하고 PS를 계속 했습니다. 결과적으로 좋은 성적을 냈으니 옳은 선택이었다고 생각합니다. 사실 저희 팀이 객관적으로 잘하는 팀이다 말하기는 아직도 힘들다.. 공감수 0 댓글수 2 2020. 11. 17.
Random Problem Solving 1 Intro 정말 PS를 하고 싶었기 때문에, 몇 문제를 풀었다. 잘 푼 문제도 있고 그렇지 못한 문제도 있지만, 어쨌던 간에 풀었던 문제들의 기록을 간단하게나마 남길까 한다. 20045 Trading System 먼저 다음과 같은 값을 찾는다. 구간합이 $x$ 이상인 구간의 개수가 $k$ 이상인 가장 큰 $x$ 이 값을 찾아야 하는 이유는, 이 값을 찾는다면 실제 수열은 $x+1$ 이상인 구간합을 모두 set을 이용해서 찾아 준 다음 나머지를 $x$로 채우는 방식으로 역추적해낼 수 있기 때문이다. 따라서 이 값을 찾는 것이 답을 구하는 것과 동치이고, 이 정도 문제를 해결할 수준이라면 이 과정은 매우 쉬우므로 설명은 생략할 것이다. 이 값은 $x$에 대한 Parametric Search로 찾아줄 수 있다.. 공감수 1 댓글수 2 2020. 10. 16.
[BOJ] 17524 Dryer 문제 링크 : www.acmicpc.net/problem/17524 문제 풀이 가장 먼저 해야 하는 관찰은 다음과 같다. $t_i$가 같은 옷이 2개 있다면 어차피 $w_i$가 큰 쪽이 더 오래 걸릴 것이기 때문에, 같이 넣고 말려도 무방하다. 따라서 의미 있는 옷은 각 $t_i$에 대해서 유일하므로, $1\le N\le61$과 사실상 같다. 그 다음으로 해야 하는 관찰들은 다음과 같다. 어떤 옷들의 집합을 같은 건조기에 넣고 돌린다면, 그 건조기의 온도는 반드시 옷 중 $t_i$의 최솟값과 같아야 한다. 이는 매우 자명하다. 어떤 건조기가 이미 $x$초 동안 돌아간다면, $x$초 이하를 소모하는 다른 옷을 끼워 넣어도 상관없다. $k=3$일때만 해결하면 그 아래는 쉽게 해결할 수 있으므로 이 경우에 대.. 공감수 1 댓글수 0 2020. 10. 11.
[SCPC] 2020 1차 예선 풀이 Intro대충 4시간 정도 때려 박아서 1~4번에서 만점을 받았고, 5번은 문제만 읽었습니다. 예전 SCPC 기출에 비해서는 확실히 난이도가 균일해진 것 같습니다(https://newdeal123.tistory.com/61 참조 요망). 제가 예상하는 Solved.ac 티어 난이도는 다음과 같습니다.다이어트 (Silver 3)카드 게임 (Platinum 3)사다리 게임 (Platinum 3)범위 안의 숫자 (Platinum 2)우범 지역 (Diamond 2~3?)1. 다이어트다음과 같이 생각해봅시다. 일단 자명히 두 식단에서 칼로리가 낮은 순으로 K개만 먹어야 한다는 것을 알 수 있습니다. 이때 식단 A의 가장 큰 칼로리를 가지는 식사는 B의 어떤 식사랑 매칭시켜야 할까요? 당연히 B의 가장 작은 칼로리.. 공감수 0 댓글수 0 2020. 8. 22.
[ICPC] Latin America Regional 2017 일부 문제 풀이 A. Arranging Tiles BOJ 15052번: https://www.acmicpc.net/problem/15052 이 문제의 핵심은, 어떤 2개의 다각형을 얼마나 가까이 붙일 수 있는 지 빠르게 계산하는 것입니다. 다각형을 배열하는 순서를 정하고, 그 다각형들에 대해 한 다각형의 x좌표 최댓값이 바로 다음 다각형의 x좌표 최솟값과 같게 배치했다고 합시다. 그렇다면 이 때의 해는 모든 다각형의 x축 길이 합에서, 모든 인접한 다각형 쌍에 대해서 다각형을 얼마나 가까이 이동시킬 수 있는지의 합을 뺀 것이 됩니다. 따라서 우리는 다각형 쌍이 주어졌을 때 이를 서로 붙일 수 있는 최대 길이를 미리 계산해 둔 뒤 가능한 모든 배열에 대해 해 중 최소를 찾아주면 됩니다. 붙일 수 있는 최대 길이를 모두 전.. 공감수 3 댓글수 0 2020. 8. 13.
[BOJ] 15404 Divide and Conquer 문제 요약 $N$개의 정점이 있고, 이 정점을 잇는 스패닝 트리가 2개 있다. 이 두 스패닝 트리의 합집합으로 구성되는 그래프에 대해(간선은 구별된다), $K$개의 간선을 제거하면 그래프를 연결 그래프가 아니도록 할 수 있다. 이 때 $K$의 최솟값을 구하고, 그 경우의 수를 $10^9 + 7$로 나눈 나머지를 출력하면 된다. 문제 풀이 가장 먼저 해야 하는 관찰은 다음과 같다. $K=2$이거나, $K=3$. 증명은 다음과 같다. 임의의 정점에 연결된 모든 간선을 제거하면 그 정점은 다른 정점과 연결되어 있지 않기에, 그래프는 연결 그래프가 아니다. 따라서 $K$는 모든 정점의 degree 중 최솟값보다 클 수 없다. 간선 하나는 정확히 두 개의 정점의 degree를 1만큼 증가시키므로, 모든 정점의 d.. 공감수 0 댓글수 0 2020. 8. 10.
2020 숭고한 Marathon 참가 후기 Intro 원래는 Advanced Division에 참가하려고 했었는데, 팀노트를 만들기 귀찮았고 무엇보다 자신이 작성해둔 코드라도 인터넷 검색에 걸리면 표절이라는 룰이 있었기 때문에 굳이 참가할 이유를 못 찾았습니다. ALPS는 Contest나 Marathon에서 한 문제 이상 해결하면 회비를 면제해주기도 했고, thak00는 이기고 싶었기 때문에 정확히 thak00보다 한문제 더 풀려고 노력했습니다. 여담으로 이번에 domjudge를 처음 써 봤는데 CMS에 비해 매우 별로였습니다. CMS가 최고다! 마지막 두 문제 빼고는 전부 해결했습니다. M은 디버깅 코드를 안 빼고 제출한 관계로 대회 중에는 WA로 기록되어 있습니다. 각 문제를 해결하면서 느낀 점과 셋 구성, 디스크립션에 대해 잡설을 풀어보려고.. 공감수 0 댓글수 2 2020. 7. 20.
[BOJ] 16910 mex와 쿼리 [문제 링크](https://www.acmicpc.net/problem/16910) 문제 요약 다음과 같은 세 쿼리를 처리해야 합니다. [l,r]에 속하는 모든 자연수를 배열 A에 추가한다. 이미 있는 수는 무시된다. [l,r]에 속하는 모든 자연수를 배열 A에서 제거한다. 없는 수는 무시된다. [l,r]에 속하는 모든 자연수에 대해 있으면 제거, 없으면 추가한다. 각 쿼리를 수행 한 뒤에 이 배열에 없는 수 중 가장 작은 자연수를 찾으면 됩니다. 문제 풀이 일단 문제에서 요구하는 좌표가 크니 좌표 압축을 시도하고 생각합시다. 그 이후 Lazy Propagation 달려 있는 세그로 연산을 처리해주며 특정 구간에 존재하는 수의 개수를 세 주면 됩니다. Lazy 연산 중에 1번 쿼리와 2번 쿼리는 서로 상.. 공감수 0 댓글수 1 2020. 3. 22.
[BOJ] 14591 KUBC League, 17165 Gosu 14591 KUBC League 문제 요약 토너먼트 그래프가 있다. 1번 정점에서 시작해서 모든 정점을 순회하는 단순 경로를 찾으면 된다. 문제 풀이 DFS 스패닝 트리에 의거하여, 그냥 DFS를 1번 정점에서부터 수행 후 마지막부터 출력해주면 된다! 코드 #include #include #include #define all(x) (x).begin(), (x).end() #define endl "\n" #define ends " " #define pb(x) push_back(x) #define fio() ios_base::sync_with_stdio(0); cin.tie(0) using namespace std; typedef long long ll; typedef pair pii; typedef pai.. 공감수 0 댓글수 0 2020. 3. 22.
Small to Large Trick Intro Small to Large Trick은 집합을 서로 합치는 연산을 최적화 할 때 사용하는 트릭입니다. (한국에서는 작은거 큰거 라고도 불리는 모양입니다.) 예를 들어 $n$개의 disjoint한, 크기가 1인 집합을 서로 합쳐야 한다고 합시다. 당연하게도 크기가 $a$인 집합에 크기가 $b$인 집합을 추가하는 데는 $O(b)$의 시간이 걸립니다. 이걸 Naive하게 구현한다면 얼마의 시간이 걸릴까요? 만약 두 집합을 합칠 때 아무 집합을 다른 집합에 합치는 것을 계속 반복한다면, 최악의 경우에는 크기가 가장 큰 집합을 크기가 가장 작은 집합에 계속해서 넣으면서 총 $O(N^2)$의 시간이 걸릴 것입니다. 하지만 어지간히 멍청한 알고리즘이 아니고서야, 크기가 큰 집합을 작은 집합에 합칠리가 없습.. 공감수 9 댓글수 1 2020. 2. 24.
Google Hash Code 2020 후기 부추전 고양이 boots jeon cats는 이런 사람들이 모여 만든 팀입니다. ryute, 고려대 아기호랑이, 랜덤과 휴리스틱을 사랑함 Lawali, 고려대 석유호랑이, 랜덤과 휴리스틱을 혐오함 cloneofsimo, 고려대 어른호랑이, 아무튼 알고리즘 시작한지 한달 반 지남 junie, 서울대, 왜 설대인데 고대 사이에 끼어 계십니까? :blobaww: 개인적으로 junie님하고 꽤 많이 친하기에, 구글 해시코드에 나가자는 뜻이 맞아 2인 팀이 결성되었습니다. 그 후 연습을 빙자한 맥주 마시기 행사를 가진 다음 사람이 많을수록 무조건 이득이라는 것을 확인하고, 대충 버스를 태워줄 수 있을 것으로 보이면서 할 것도 딱히 없어 보이는 라왈리를 섭외했습니다. 마지막으로 인원수를 대충 때워야 할 것 같다는 .. 공감수 6 댓글수 1 2020. 2. 21.
[BOJ] 13329 Meteor Shower 문제 요약 y>0인 반평면에 다각형들이 있다. 원점에서부터 빛을 쏴서 다각형들을 관측할 때, 어떻게 빛을 쏴도 관측할 수 없는 다각형의 개수를 세서 출력한다. 문제 풀이 이런 류의 문제에서 항상 쓰는 테크닉인 스위핑을 갖고 옵시다. 다만 평소에 쓰는 라인 스위핑이 아닌, 각도 기준으로 스위핑을 진행해야 합니다. 다각형끼리 서로 교차하지 않으므로, 각 다각형을 각도가 가장 작은 점과 각도가 가장 큰 점을 이어주는 선분으로 바꿔줘도 답에는 영향이 없습니다. 그렇다면 문제는 n개의 선분이 주어졌을 때 완전히 가려지는 선분을 구하는 문제로 환원됩니다. 모든 선분의 끝 점을 각도 순으로 정렬합니다. (https://koosaga.com/97) 선분의 시작 지점이 들어올 때 집합에 선분을 추가하고, 종료 지점이 들.. 공감수 0 댓글수 0 2020. 2. 4.
[ICPC] ICL 2016 (GP of Tatarstan) 후기 & 잡설들 Intro 고려대학교 2020 ICPC 팀이 한 팀 결성되었습니다! ryute, 20학번, 퍼플 seyun, 19학번, 오렌지 cheetose, 군인, 오렌지 cheetose님이 저에게 팀 하자는 제안을 주셨고, seyun님도 cheetose님한테 팀 하자는 제안을 드린 것 같아서 영문도 모른 채 3인 팀이 구성되게 되었습니다. 저는 오렌지 둘의 버스를 탈 수 있으니 대만족이고, 현재 음료수와 간식을 배달하고 분배하는 업무에 숙달되기 위해 오늘도 열심히 노력하고 있습니다. 입학하기도 전에 버스팀이 생기는 사람이 있다? 서로 얼굴을 본 적이 없다는 이유로 만나서 밥을 먹기로 했습니다. cheetose님이 밥 먹기 전에 셋을 하나 돌자고 하셔서 솔직히 불안했습니다. 오렌지 2명 사이에 끼어서 노솔브 하면 어.. 공감수 0 댓글수 0 2020. 1. 31.
[BOJ] 10264 Particle Swapping 문제 링크: https://www.acmicpc.net/problem/10264 문제 요약 평면 그래프에서 다음과 같은 쿼리를 처리해야 한다. 어떤 두 정점이 주어질 때, 각 정점에서 반대 정점으로 이동하는 개체 2개가 있다. 이동 중 개체 사이 거리의 최솟값이 가장 최대가 되도록 배치했을 때 거리의 최솟값을 구한다. 단, 경로에서는 간선은 따지지 않고 오직 정점만을 따진다. 문제 풀이 그래프를 적절히 바꿔서 모델링해보자. 정점 A에서부터 출발하는 개체와 정점 B에서 출발하는 개체의 위치를 순서쌍으로 표현해볼 수 있다. 만약 그렇다면 이동 중 개체 사이 거리의 최솟값은, 순서쌍을 정점으로 두고 순서쌍 사이의 상태 전이가 가능한 경우를 적당히 간선으로 이어줬을 때 (A,B)에서 (B,A)로 이동하면서 찾아.. 공감수 0 댓글수 0 2020. 1. 24.
[BOJ] 1396 크루스칼의 공 문제 링크: https://www.acmicpc.net/problem/1396 문제 요약 간선에 가중치가 존재하는 그래프가 존재하는데, 다음과 같은 쿼리를 빠르게 처리해야 한다. 정점 x에서 시작해서 y까지 이동하려고 할 때, 이용해야 하는 간선의 최소 가중치는 얼마인가? 그리고 x에서부터 그 가중치로 방문할 수 있는 정점의 개수는 몇 개인가? 문제 풀이 두 가지 풀이가 존재한다. (1) 병렬 이분 탐색 한 쿼리에 대해서 다음과 같은 문제를 해결한다고 생각해보자. 정점 x에서 시작해서 k 이하의 가중치를 갖는 간선만을 사용할 수 있을 때, 정점 y에 방문할 수 있는가? 또한 이 때 정점 x로부터 방문할 수 있는 정점의 개수는 얼마인가? 이 문제를 해결하는 방법은 쉽다. 말 그대로 k 이하의 가중치를 가지.. 공감수 0 댓글수 0 2020. 1. 24.
USACO 2020 January (Gold) 풀이 Intro 원래 USACO 참여할 생각이 없었는데 브론즈만 밀어야지 실버만 밀어야지 하다가 결국 골드를 키게 되었다. 중간에 뇌절파티를 많이 해서 예상보다 시간이 매우매우 많이 걸렸다. 개인적인 난이도는 2->1->3이라고 생각하나, 증명 없이 뇌를 비우고 푼다면 1번이 2번보다 더 쉬울수도 있다는 생각을 해본다. 세 문제 모두 플5에서 플3 정도의 수준이라고 생각한다. 1. Time is Mooney (time) 문제 요약 정점 1000개, 간선 2000개인 그래프가 있다. 각 정점은 1000 이하의 가중치를 가지고 있는데, 정점을 방문할 때 마다 그만큼의 점수를 얻는다(여러 번 방문해서 점수를 얻을 수 있다). 단, 사용한 간선 개수를 $t$라고 하면 주어지는 1000 이하의 정수 $c$에 대해 $c.. 공감수 1 댓글수 2 2020. 1. 22.
Goodbye, BOJ 2019! 후기 Intro 굿바이, BOJ 2019! 라는 대회는 어떻게 보면 제 주도로 만들어진 대회입니다. leejseo님과 rdd6584님과 작년 백준에서 진행했던 디디포스를 끝내고, 다음 대회를 진행해 보자는 말이 나왔었습니다. 10월 초 경에 생각이 나서 대회를 열고 싶었는데 만약 12월 말에 대회를 개최하게 된다면 디디포스와 거의 1년 간격이 된다는 것을 알았습니다. 구데기컵과 키파컵을 보고 백준에도 매년 정기적으로 개최되는 대회가 있었으면 좋겠다고 생각했는데 마침 대회를 여는 시기가 연말이었기 때문에, 낼름 연말 대회 자리를 먹기로 시도했습니다. 백준 대회란이 백준 고유 콘테스트가 아닌 다른 교내대회 오픈컨으로만 가득 채워진 것이 조금 안타까워서도 있었습니다. 그런 고로 자주 활동하는 알고리즘 채팅방에서 사.. 공감수 1 댓글수 5 2020. 1. 5.
BOJ: 코딩 테스트를 위한 길라잡이 (미완성) 들어가기에 앞서 미완성인 길라잡이입니다!!!!! 링크 지금 거의 다 깨져서 조만간 수정 예정입니다 최근 많은 기업들이 코딩테스트를 진행한다고 들었습니다. 왜 코딩 테스트를 진행할까요? 아직 기업 코딩 테스트에 목숨을 걸 나이는 아니지만, 아무래도 기업에서는 대학에서 커리큘럼을 모두 소화했다면 이 정도는 코딩해서 풀 수 있지 않을까라고 생각하기 때문 아닐까 합니다. 실제로 회사에서 해결하기를 원하는 과제가 엄청 대단한 수준을 요구하는 것 또한 아니고요. 하지만 많은 분들이 이를 굉장히 힘들어 합니다. 또 왜 이런 생고생을 해야 하냐고 물으시는 분들도 있습니다. 하지만 이런 간단한 과제조차 효율적으로 해결하지 못하고 또 버그를 내서 제대로 잡지 못한다면, 실무에서 코드가 훨씬 길어졌을 때도 마찬가지로 수렁에.. 공감수 6 댓글수 2 2019. 11. 25.
PS: 뉴비를 위한 Simulated Annealing 입문 (2) INTRO 국내에서 가장 널리 사용되는 온라인 저지인 BOJ에는 Simulated Annealing으로 풀 수 있는 유명한 문제가 하나 있습니다. 바로 동전 뒤집기 2 (https://www.acmicpc.net/problem/2582) 입니다. 많은 사람들이 KOI에도 시뮬레이티드 어닐링 같은 특수한 알고리즘을 시용해서 푸는 문제가 나오냐고 의아해 하는데, 저 당시에는 서브태스크가 아닌 테스트 케이스 당 부분점수가 있었고, 따라서 정해가 적절한 가지치기를 동반한 백트래킹이었다고 추측해 볼 수 있을 것 같습니다. 하지만, 고생고생해서 백트래킹에 휴리스틱 함수를 적용시키는 것 보다는 시뮬레이티드 어닐링을 배워서 써먹는 쪽이 아무래도 훨씬 빠르겠죠. 시뮬레이티드 어닐링은 이러한 종류에 문제에 더 일반적으로 .. 공감수 10 댓글수 3 2019. 10. 6.
PS: 뉴비를 위한 Simulated Annealing 입문 (1) INTRO PS에서 우리가 푸는 평범한 알고리즘 문제들은 결정론적 문제입니다. 이 말은, 이미 출제자에 의해서 밝혀진 고정된 시간 안에 동작하는 해법이 있고, 우리는 그 해법을 찾아서 구현하기만 하면 된다는 뜻입니다. 그렇지만 NYPC 예선에서 나오는 출력 파일 문제라던가, IOI의 "그 문제"인 nowruz로 대표되는 Output Only 문제, Topcoder에서 진행되는 Marathon Match 등에서는 완벽한 최적해를 찾아내는 것이 불가능하기도 합니다. 이럴 때에는 많은 사람들이 휴리스틱 알고리즘을 사용합니다. 사실 휴리스틱 알고리즘이라고 하면 어떤 특정한 알고리즘을 지칭하는 것이 아닌데, 보통 저는 휴리스틱을 완전 탐색을 할 때 속도 향상을 위해 사용하는 일반적인 휴리스틱과 전역에서 최적점과 .. 공감수 12 댓글수 0 2019. 8. 14.
[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만개에 응답.. 공감수 0 댓글수 1 2019. 5. 27.
BOJ 길라잡이 (Beta) 내년 동아리 활동을 대비해서 만들어 놓는 [BOJ를 여행하는 히치하이커를 위한 안내서]입니다. 아직 미완성이라 부족한 부분이 있습니다. 보완해야 할 것 같은 부분은 댓글로 달아주시면 감사하겠습니다. ryute.tistory.com/68 한 세트는 총 4개의 소단원으로 구분되어 있습니다. 각 소단원에는 4~5개정도의 문제가 실려 있으며, 난이도 순은 아닙니다. *가 달린 문제는 심화 문제이거나 매우 유사한 문제입니다. 알고리즘 초보 딱지를 떼기 위한 목적으로 다양한 유형의 기초 문제들을 계단식으로 학습할 수 있도록 주제들을 배치하였습니다. C를 문제 해결에 무리 없이 활용할 수 있는 수준에 도달했을 때 시작하는 것을 전제 조건으로 하였습니다. 1-1. 탐색과 정렬 (1) 1-2. 기초 자료구조 (1) 1-.. 공감수 39 댓글수 22 2019. 2. 12.

문의안내

티스토리
로그인
고객센터

티스토리는 카카오에서 사랑을 담아 만듭니다.