일기 (50) 썸네일형 리스트형 C++ iterator 사용 시 주의 사항 다음은 대회 중에 제출한 소스의 일부이다. if (it-- != t2c.begin()) { // do something } 여기서 t2c는 std::map 타입이고 it는 std::map::iterator 타입이다. 위의 조건문에서는 undefined behavior가 발생한다. 지금까지는 iterator가 invalidated 상태가 되어도 dereference만 하지 않으면 문제가 없다고 생각하였다. 대회 종료 후 코드 테스트 중 원인을 알 수 없는 segmentation fault가 발생하였다. 도저히 원인을 찾을 수 없어 gdb로 디버깅을 하다가 놀라운 사실을 발견하였다. 일부 컨테이너에서는 iterator의 증감 연산 시 iterator가 invalidated 상태가 되면 segmentation.. BOJ 26248번 - 겨울 숲의 수호자 26248번: 겨울 숲의 수호자 첫 번째 테스트 케이스의 경우, 첫 번째 야수를 $0$초부터 $1$번 공격하고 두 번째 야수를 $1$초부터 $10$번 공격하고 첫 번째 야수를 $11$초부터 $9$번 공격하면 된다. 두 번째 테스트 케이스의 경우, www.acmicpc.net 서론 기반이 되는 논문은 링크에서 찾아볼 수 있다. 논문의 pseudocode를 그대로 구현하면 WA를 받는다. 약간의 수정이 필요한데 이를 위해서는 논문의 내용을 어느 정도는 이해하고 있어야 한다. 수정된 pseudocode를 공개하면 난이도가 대폭 낮아지기에 몇 가지 팁만 언급하고자 한다. 참고로 나도 논문의 모든 내용을 완벽하게 이해한 것은 아니라서 잘못된 부분이 존재할 수 있다. assert 도배하기 코드의 온갖 부분에 ass.. ACM-ICPC World Finals 2015 H - Qanat Qanat – Kattis, Kattis A qanat is an irrigation system widely used to deliver water in hot, arid climates. The technology was originally developed by Persians over 2000 years ago. In Morocco, qanats are known as khettara and are still used today in the southern part of the count open.kattis.com 너무 어려워서 solved.ac 티어를 보니 다이아였다. 무자비한 구현을 요구하는 Window Manager도 World Finals 2015 문제이다. ICPC 대회 시간이 5시간인.. Waterloo Programming Contest 2009-10-03 C - Cantor Cantor – Kattis, Kattis Hide Cantor Georg Cantor (public domain) The ternary expansion of a number is that number written in base $3$. A number can have more than one ternary expansion. A ternary expansion is indicated with a subscript $3$. For example, $1 = 1_{3} = 0.222\ldots _ open.kattis.com 0 이상 1 이하의 실수가 주어질 때 해당 수가 cantor set에 속하는지 판단하는 문제이다. 이때 입력은 소수점 아래 6자리까지 주어진다. 우선 0과 1을 제외한 모든 입력에 .. CP4 Chapter 2. Data Structures and Libraries CP4 Chapter 2를 읽고 모든 Kattis 연습 문제를 풀이하였다. 이것 저것 하다 보니 대략 한 달 정도 걸렸다. Chapter 1보다 수준이 살짝 올라가서 대다수의 연습 문제는 solved.ac 기준 실버 수준이다. 내용은 읽을 만한데 코드는 개판이다. 대부분 더 나은 구현이 존재하니 인터넷을 잘 뒤져보자. Segment Tree 부분은 연습 문제가 많이 부족하다. solved.ac CLASS 6~7에서 segtree 태그로 검색하고 밀면 도움이 될 것이다. 또한 Lazy Propagation 없는 Segment Tree도 별도로 공부하자. Lazy Propagation 버전보다 코드도 짧고 시간과 메모리 모두 적게 소모한다. 연습 문제의 절반 이상은 BOJ에서도 풀이할 수 있다. 문제집으로 .. solved.ac CLASS 7 구간 트리 문제 정리 solved.ac 알고리즘 문제해결 학습의 이정표 🚩 Baekjoon Online Judge 문제들의 난이도 및 티어 정보를 제공하는 사이트입니다. solved.ac 서론 이 글에서 제시된 문제 중 Fenwick Tree로 풀이할 수 있는 문제들은 Segment Tree로 풀이할 수도 있습니다. 일부 스포일러가 존재합니다. 1. BOJ 10999번 - 구간 합 구하기 2 RURQ Fenwick Tree 2. BOJ 16975번 - 수열과 쿼리 21 RUPQ Fenwick Tree 3. BOJ 16978번 - 수열과 쿼리 22 Fenwick Tree + offline query 4. BOJ 13537번 - 수열과 쿼리 1 Fenwick Tree + offline query or Merge Sort Tree.. solved.ac CLASS 6 구간 트리 문제 정리 solved.ac 알고리즘 문제해결 학습의 이정표 🚩 Baekjoon Online Judge 문제들의 난이도 및 티어 정보를 제공하는 사이트입니다. solved.ac 서론 이 글에서 제시된 문제 중 Fenwick Tree로 풀이할 수 있는 문제들은 Segment Tree로 풀이할 수도 있습니다. 일부 스포일러가 존재합니다. 1. BOJ 2042번 - 구간 합 구하기 Fenwick Tree 기초 2. BOJ 2357번 - 최솟값과 최댓값 Segment Tree 기초 3. BOJ 11505번 - 구간 곱 구하기 Segment Tree 기초 수의 범위에 0이 포함되어서 Fenwick Tree 풀이는 어려워보인다. 4. BOJ 14428번 - 수열과 쿼리 16 Segment Tree 5. BOJ 2243번 - .. KTH Challenge 2014 G - Intercept Intercept – Kattis, Kattis Fatima commutes from KTH to home by subway every day. Today Robert decided to surprise Fatima by baking cookies and bringing them to an intermediate station. Fatima does not always take the same route home, because she loves to admire the artwork inside di open.kattis.com 문제를 다음과 같이 요약할 수 있다. 가중치가 있는 유향 그래프 G가 주어진다. 정점 s에서 정점 t로 가는 모든 최단 경로에서 반드시 지나는 정점 집합 V를 구하여라. 나의 .. 이전 1 2 3 4 5 6 7 다음
