조준화의 오류정정

C++의 sort, stable_sort, set, map는 비교 함수를 설정할 수 있다. 정렬 기준을 설정하는 것이다.참고로 stable_sort는 동일한 값을 가진 원소들의 상대적 순서(삽입 순서)가 정렬 후에도 보존되는 정렬 알고리즘이다. C++에서 비교 함수가 true를 반환하면 첫 번째 인자가 더 앞에 오게 한다. 즉, comp(a, b)가 true를 반환하면 a가 앞에 오는 것이다. 따라서 a>b를 비교 함수로 설정하면 a가 더 클 때 true이고 더 큰게 앞으로 오므로 내림차순 정렬이 된다. 이 비교 함수는 람다 표현식으로 익명 함수를 생성해 편리하게 설정할 수 있다. 람다 표현식의 기본 문법은 다음과 같다.[캡처](매개변수) -> 반환타입 { 함수 본문 } 캡처 클로저 [ ]: 외부 변수..

[실전 알고리즘] 0x14강 - 투 포인터안녕하세요, 이게 강의 목차를 16진수로 붙이니까 혼동을 주는데 이번 강의가 0x14강이니까 오리엔테이션은 빼고 20번째입니다. 아직 갈길이 좀 멀긴 하지만 꽤 많이 온 것 같습니다. 여러분들도blog.encrypted.gg바킹독님의 블로그를 참고하여 공부한 내용을 기록한 글입니다.투포인터 알고리즘은 배열에서 원래 이중 for문으로 O(N^2)으로 처리되는 작업을 2개의 포인터의 움직임으로 O(N)에 해결하는 알고리즘이다. 어떻게 N이나 줄일 수 있냐면, 일반적인 이중 for문에서 i = 0일 때 j가 0부터 n-1까지 돌고, i = 1일 때 j가 0부터 n-1까지 도는 방식, 즉 각 i에 대해서 j가 0부터 n-1까지 도는 상황을 생각해보면, i = 0일 때 계..

https://www.acmicpc.net/problem/2473전에 풀었던 두 용액을 섞어서 0과 가장 가까이 만드는 문제와 세 수를 합해서 딱 0을 만드는 문제를 합친 버전이다. 우선 0과 가장 가까이 만들어야하고, 세 수를 합한다는 점에서 (i, j)의 합을 먼저 구하고 그 합과 어떤 숫자 idx를 합해서 0과 가장 가까이 만드는 idx를 찾는 방식으로 접근했다. 문제는 두 용액이 아닌 세 용액이라는 점이다. 기존 두 용액에서는 lower_bound(~~, ~~, -i) = idx 라 했을 때 idx - 1, idx를 보면 된다. 다만 idx가 i와 겹치는 경우를 고려해서 idx + 1까지 봤던 것이었다.이번에는 용액이 세 가지이므로 idx는 idx + 1을 똑같이 보고, [i, j] 와 같은 경우..

https://www.acmicpc.net/problem/2467https://www.acmicpc.net/problem/3151용액을 먼저 풀어보고 합이 0을 풀어보는 것을 추천한다. 백준 2467: 용액용액은 간단하게 합이 0과 가장 가까운 index를 찾으면 된다.arr [i]를 기준으로 찾으면 될 것 같은데 결론부터 말하자면 arr [i]와 합이 0과 가장 가까워지는 index를 찾으려면 -arr [i]를 lower_bound() 함수에 적용하면 된다. lower_bound(~~, ~~, -arr [i])의 결과는 -arr [i] 이상인 값이 될 테고 그 값을 arr [k]라 하자.arr [k]는 -arr [i]가 될 수도 있고 그 값보다 클 수도 있다. 또, arr [k-1]은 -arr [i] ..

https://www.acmicpc.net/problem/18869먼저 문제를 꼭 읽어보고 좌표 압축은 떠올리지 말고 풀이를 생각해보자. 최대 100개의 우주이고 각 우주당 10000개의 행성이 존재한다. 그냥 완전 탐색을 생각해보면 총 100*100 번의 루프를 돌 것이고, 한 번의 루프에 10,000개의 행성에 대해 모든 index 쌍별로 어떤 값이 더 큰지를 계산해봐야 한다. 얼추 계산해봐도 10,000 C 2 * 10,000 ... 불가능하다. 문제가 되는 부분은 두 개의 우주에 대해 그 우주가 균등한지를 계산하는 과정이다. 이 부분만 해결하면 될 것 같다. 아래의 예시로 좀 더 생각해보자. 균등한 행성들이다.2 33 17 512 50 31 값 3 17 5를 정렬하면 3 5 17이다. 그냥 정렬해..

[실전 알고리즘] 0x13강 - 이분탐색안녕하세요, 이번 시간에는 이분탐색을 배워보도록 하겠습니다. 사실 이분탐색의 개념 자체는 그렇게 어렵지는 않습니다. 초등학생 정도만 되어도 업다운게임같은걸 아주 재밌게 즐길 수 있고,blog.encrypted.gg바킹독님의 블로그를 바탕으로 정리한 글입니다.이분탐색은 업다운 게임을 생각하면 이해가 편하다. 1에서 50 사이의 숫자를 찾으려면 25를 부르는게 가장 합리적인 것이다. 가장 기본적인 형태의 이분탐색은 이 업다운 게임의 기조를 띄고 있다. 특정 범위를 줄여가면서 특정 조건을 만족하는 데이터를 찾는 것이다. 구현적으로는 이미 STL에 잘 구현되어있기에 어려운 부분이 전혀 없다. 하지만 이분탐색은 응용이 들어가게 되면 굉장히 어렵고 특히 코딩테스트에서 가장 어..

[실전 알고리즘] 0x11강 - 그리디안녕하세요, 그리디를 공부해봅시다. 그리디 알고리즘을 한국어로 번역하면 욕심쟁이 알고리즘입니다. 그리디라고 부를 때랑 다르게 욕심쟁이 알고리즘이라고 하면 떼쓰는 어린 아이가 생각나blog.encrypted.gg바킹독님의 블로그를 바탕으로 정리한 글입니다.그리디 알고리즘은 탐욕적으로 지금 상태에서 가장 최적인 답을 선택하는 알고리즘이다.이를 다르게 말하면 관찰을 통해 탐색 범위를 줄이는 알고리즘이다.조금 더 쉽게 풀어보자면 현재 상태를 관찰해서 원래라면 O(N^2) 만큼 탐색해야 하는걸 O(N) 정도로 줄이는 것이다.예를 들어 merge sort를 생각해보자. 병합 과정의 한 step을 생각해보면, 정렬된 결과 배열에 들어갈 하나의 원소를 선택해야 한다.이 과정에서 현..

정보검색의 꽃. 굉장히 중요한 부분이다!이번 챕터의 Term frequency, Tf-idf ranking, Vector space model은 반드시 시험에 나오니 잘 익혀두자.1. Ranked retrieval기존에는 단어가 포함된 문서를 찾는 boolean retrieval을 다루었다. 그런데 어떤 단어는 많은 관련이 있고 어떤 단어는 등장하기만 할 수 있다. 중요도가 없는 것이다. expert users, application에게는 boolean retrieval이 좋을 수 있다. 전문가는 &, |를 잘 설정해서 관련된 문서의 개수를 잘 조절할 수 있지만 일반 사용자들에게는 불가능하다.예를 들어 변호사는 오래 걸리더라도 관련된 모든 정보를 다 봐야 하지만일반 사용자들은 1000개가 넘는 문서를 다..

RDBMS가 수학에 기반한 모델이기에 견고하게 구성되어 있고 모델 뿐 아니라 모델을 잘 활용할 수 있는 인터페이스가 중요했다. 그 인터페이스 중 SQL로 수렴이 됐고 잘 만들어진 언어이다. SQL은 술어논리로 이루어져 있는데 그래서 닫힘 성질을 가지고 있다. operation을 수행했을 때 input과 output이 같은 집합에 속해있다는 것이다. 예를 들어 어떤 집합에 SQL 연산을 수행하면 결과 또한 집합이다.이러한 닫힘 성질 덕분에 operation set 하나만 디자인하면 된다. 만약 결과가 집합이 아니라면 그 결과에 따른 다른 operation set을 만들어야 한다.1. SQL Data Definition and Data TypesSQL 에서는 Table, Row, Column 용어를 사용하고..

이제 위에서 만든 ER 다이어그램을 테이블로 만들기 전에 Relational Data Model과 RDB가 가지고 있는 제약사항을 알아야 한다.1. Relational Model ConceptsRelation에 대한 개념부터 짚고 넘어가자. Relation을 원래 table로 생각을 했지만 이해를 쉽게 하기 위해 table로 생각한 것이지 원래 Relation은 집합을 근본으로 한다. 집합을 근본으로 하는 만큼 정교한 수학을 기반으로 하기에 Relation 개념은 견고하다.Relational Model Concepts은 Dr.E.F.Codd에 의해 집합을 근거로 고안된 수학적인 컨셉이다. 이 컨셉은 구현에 관해서는 전혀 신경쓰지 않고, 이 컨셉을 구현할 때 table을 이용해서 구현하게 된 것이다.Inf..