오랜만의 코딩으로 풀어보기 시리즈이다. 오늘은 아주 간단하고 쉬운 문제이다. 문제 1부터 9까지의 숫자를 한번씩만 사용해서, 수식을 성립시키는 문제이다. 이런 유형의 문제는 "복면산 문제"라고 불리는 수학 퍼즐의 한 종류이다. 여담이지만, 개인적으로 좋아하는 문제이다. 이와 관련한 알고리즘 문제를 출제한 적도 있다. 완전 탐색류 알고리즘을 연습하기 좋은 문제라고 생각한다. 아래 링크에서 풀어볼 수 있다. BOJ 15811 - 복면산?! (https://www.acmicpc.net/problem/15811) 위 문제는 9개의 숫자와 9개의 알파벳이니 더 쉽다. 1부터 9까지 A부터 I까지 모두 대응시켜보며 만들어지는 세 값이 일치하는 지 확인하면 된다. 즉, 모든 순열을 확인하면 된다. 경우의 수는 \(9..

링크: https://www.acmicpc.net/problem/3640문제가중치가 있는 방향 그래프가 주어지고, 1번 정점에서 V번 정점까지 서로 겹치지 않는 2개의 경로 중 비용이 최소인 경우를 출력하는 문제이다. 겹치지 않는 경로를 찾는 것은 최대 유량으로 해결 가능하고, 그 비용이 최소가 되는 것을 구해야하므로, 네트워크 플로우 유형 중에서 MCMF(Min Cost Max Flow; 최소 비용 최대 유량)인 문제이다. 그래프 문제는 항상 문제 조건을 꼼꼼히 살펴야겠다. 이번에도 "출발과 목적지를 제외하고 같은 중간 지점이나 같은 뱃길을 지나면 안 된다." 에서 정점이 겹쳐서는 안되는 조건을 깜빡해서 계속 틀렸다. 이 조건을 무시하면 틀리는 예외 케이스는 아래와 같다. 최대 유량은 1개이고, 답은 ..

링크: https://www.acmicpc.net/problem/15480문제문제 설명은 간단하다.루트를 r로 하는 트리에서 u와 v의 최소공통조상(LCA)를 출력하는 문제이다. LCA(r, u), LCA(r, v), LCA(u, v) 세 개 중에서 깊이가 더 깊은 노드를 출력하면 된다.증명은 사실 안 했는데, 케이스 몇 개를 두고 해보니까 계속 답이었다..혹시나 싶어서 제출해봤더니 정답코드

제목 그대로, 트리의 노드 순서를 다시 정리하여 구간으로 표현하는 것이다. 그림으로 보면, 트리의 구조와 왼쪽과 같았다면, 각 트리의 번호를 오른쪽처럼 변경하는 것이다. 순서는 전위순회(pre-order)로 탐색하면서 번호를 붙이면 된다. 이게 왜 필요할까? 제목에서 이미 말한거지만, 구간으로 표현하는 것이 더 용이할 때 사용한다. 특히 트리를 세그먼트 트리나 펜윅 트리 등의 구간합/부분합으로 변형하여 문제 해결이 필요한 경우이다. 노드의 번호를 위처럼 정리하면, 각 노드가 포괄하는 노드는 항상 확실하다. "자신의 번호 + 그 노드의 서브 트리(들)의 크기"가 포함할 수 있는 자식의 마지막 번호와 같다. 그럼 트리를 일렬로 펴서 다룰 수 있다. 코드 관련 문제 (+스포일러)BOJ 2820 - 자동차 공장..

링크: https://www.acmicpc.net/problem/9034오랜만의 포스팅. 아마 한동안 문제를 풀 시간은 없을 듯.. ㅠ문제매번 \(i\)번 선수에게 더해지는 점수가 주어지고, \(x\)번째 선수가 몇 등인지 실시간으로 출력하는 문제이다. 먼저 어떤 선수의 등수는 "그 선수보다 점수가 더 높은 사람의 수 + 1"이다.매번 탐색을 하거나, 정렬을 한다면 \(100,000\)명의 선수에 대한 \(200,000\)번의 질의에 대답하기엔 시간상으로 버겁다. 내 등수는 구간 [내 점수 + 1, ∞)에 있는 사람의 수 + 1과 같다. 점수의 합은 최대 \(10^{9}\)이므로, 모든 점수를 압축할 필요가 있다. 이건 좌표압축 문제(BOJ 18870 - 좌표 압축)를 먼저 풀어보기를 권장한다.점수가 더..

링크: https://www.acmicpc.net/problem/1539문제주어진 순서대로 이진 검색 트리를 구축하였을 때, 모든 노드들의 높이 합을 출력하는 문제이다. 9 다음에 1이 주어지면, 위와 같은 그림일 것이다.다음으로 4가 들어오면 \(x\) 위치로 갈 텐데, 이전에 등장한 수 중에서, 자신보다 바로 작거나 바로 큰 수의 높이 중 더 큰쪽 + 1이 자신의 높이이다. 만약 \(y\) 자리에 무엇이 있다고 해도, \(x < 9 < y\) 임은 항상 보장되므로, 자신보다 바로 작거나 큰 수만 비교하면 된다.코드

2020/03/19 - [개발/C++] - [C++ STL] binary_search, upper_bound, lower_bound 구현하기 [C++ STL] binary_search, upper_bound, lower_bound 구현하기 종종 사용하는 std::binary_search와 그 친구들(lower_bound, upper_bound)의 구현입니다. 이 친구들은 헤더에 있습니다. 평소 쓰던 스타일을 그대로 작성하여 올립니다. binary_search가 왜 그 lower.. joonas.tistory.com binary_search는 찾는 key와 lower_bound 위의 값이 같은지만 확인하면 된다. 따라서 아래처럼 구현할 수 있다. bool binary_search(int arr[], int..

Palindromic tree 영문 글 - http://adilet.org/blog/palindromic-tree/ 두 문자열 S, P의 공통 부분 문자열이면서, 팰린드롬인 문자열의 개수를 구하는 자료구조이다. 관련 문제로는:2014-2015 ACM-ICPC, Asia Xian Regional - Problem G. The Problem to Slow Down You가 있다. Mikhail Rubinchik라는 유저가 고안한 자료구조라고 한다.삼성 소멤에서 shjgkwo님이 정리해준 한국어 문서도 있다. (https://www.secmem.org/blog/2019/05/17/Palindromic-Tree/)