본문 바로가기

전체 글

c++ stl vector 원소를 참조할 때 주의할 점 Ant& current_ant = ants[current_ant_id]; 경쟁 프로그래밍 문제나 코테 문제를 풀 때 주력 언어로 C++를 사용하고 있다. (현업에서는 거의 사용을 안해서 모던 C++는 잘 모른다.) 최근에 비교적 간단한 문제를 풀던 중 왜맞틀의 함정에 걸려 고생을 했는데 vector를 잘 못 사용하고 있었다는 것을 깨달아서 노트를 남긴다. 문제가 된 코드 vector ants; ... void create_new_ant_and_add_follow() { ... Ant& current_ant = ants[current_ant_id]; ... Ant new_ant = createNewAnt(); int new_ant_id = ants.size(); ants.push_back(new_ant);.. 더보기
BOJ 1019 책 페이지 https://www.acmicpc.net/problem/1019 1019번: 책 페이지 첫째 줄에 0이 총 몇 번 나오는지, 1이 총 몇 번 나오는지, ..., 9가 총 몇 번 나오는지를 공백으로 구분해 출력한다. www.acmicpc.net 풀이 문제를 풀기 위해 재귀 호출을 하면서, 문제의 구조를 일관되게 유지하는 게 핵심이다. 7683을 생각해보자. f(7683, 1) 은 1~7683까지 일의 자리에 각 숫자가 등장하는 횟수를 세야 한다고 하자. 1~7683까지 일의 자리에 각 숫자가 몇 번씩 등장하는지 카운팅은 금방 할 수 있다. 문제는 십의 자리에서 등장 횟수를 구하기 위해 다음 재귀 호출을 할 때, 문제의 구조를 유지하기가 어렵다. 재귀 호출 구조를 간단하게 만들어야 한다. 재귀 호출 안에서.. 더보기
BOJ 10775 공항 https://www.acmicpc.net/problem/10775 10775번: 공항 예제 1 : [2][?][?][1] 형태로 도킹시킬 수 있다. 3번째 비행기는 도킹시킬 수 없다. 예제 2 : [1][2][3][?] 형태로 도킹 시킬 수 있고, 4번째 비행기는 절대 도킹 시킬 수 없어서 이후 추가적인 도킹은 불 www.acmicpc.net 숫자가 1부터 G까지 하나씩 있는 집합 A가 있을 때 주어진 숫자 x에 대해 아래의 연산을 수행한다. 집합 A에서 x보다 작거나 같은 원소 중 가장 큰 숫자를 찾는다. 위에서 찾은 원소를 A에서 제거한다. 위에서 찾은 원소를 반환한다. 일감은 구간 트리(segment tree)를 이용하여 해결하는 것이다. 구간 트리에 대해서 i번째 원소를 i로 초기화 한다. x에.. 더보기
BOJ 12858 Range GCD https://www.acmicpc.net/problem/12858 12858번: Range GCD 첫째 줄에 수열의 원소의 개수를 나타내는 하나의 자연수 N이 주어진다. (1 ≤ N ≤ 100,000) 둘째 줄에 수열의 각 원소를 나타내는 N개의 자연수가 주어진다. i번째로 등장한 자연수는 수열의 i번째 www.acmicpc.net gcd(a, b, c, d, e) = gcd(a, |b - a|, |c - b|, |d- c|, |e - d|) 임을 이용해야 한다. (이 부분이 핵심이다) 어떤 구간에 속한 모든 원소에 x를 더한 더하는 경우, 그 구간 내에서 이웃한 원소들 사이의 차이는 변화가 없다. 그 구간의 경계에 인접한 원소와의 차이에만 변화가 발생한다. GCD를 계산하기 위한 세그먼트 트리에는 인.. 더보기
BOJ 1031 스타대결 https://www.acmicpc.net/problem/1031 1031번: 스타 대결 첫째 줄에 지민이의 팀의 팀원 수 N과 한수의 팀의 팀원 수 M이 주어진다. 둘째 줄에는 지민이의 팀의 각 팀원이 해야 하는 경기의 수가 주어지고, 셋째 줄에는 한수의 팀의 각 팀원이 해야 하 www.acmicpc.net 우선 규칙 1~3을 만족하는 대진을 만드는 것은 최대 유량(max flow)을 이용하여 푸는 해법을 생각할 수 있다. 지민이의 팀을 왼쪽에, 한수의 팀을 오른쪽에 이분매칭 하듯이 배열한다. 지민이 팀 집합을 L, 한수팀 집합을 R이라고 하자. 양 팀 간 모든 쌍에 대해, 다시 말해 모든 L의 정점에서 R의 모든 정점으로 capacity 1의 간선을 추가한다. 최대 유량 그래프의 소스 정점에서 L의 .. 더보기

티스토리툴바