개요 PS에서 정수론은 수학에서 기하와 함께 양대산맥을 이루는 주제중 하나이다. 본 포스트에서는 정수론 알고리즘을 배우기 이전에, 증명 및 이해를 하기 위하여 필수적으로 알아야 할 합동식에 관한 이론과, 정수론에서 가장 기초적인 연산인 모듈러 연산, 기초적인 정수론 알고리즘을 다룬다. 합동식 합동식은 PS에서 사용되는 알고리즘 뿐만 아닌 정수론에...

탐욕법 개요 최적해를 구할 때 사용되는 알고리즘으로, 문제를 쪼개어 단계별로 나눈 후, 각 단계에서의 최적해를 구해나가며 전체 문제의 최적해를 구하는 알고리즘이다. 조건 총 두 조건이 만족할 시 탐욕법 사용이 가능하다. 탐욕적 선택 속성(greedy choice property): 각 단계에서 최적의 선택을 하는 것으로 전체 문제의...

동적계획법 개요 문제를 부분 문제로 나눈 후, 해당 부분 문제의 최적해를 결합하여 문제의 최적해를 구할 수 있을 때 중복되는 부분 문제의 답을 저장해 두었다가 재활용하는 알고리즘 설계 방식 조건 총 두 조건이 만족한다면 동적계획법을 활용할 수 있다. 중복되는 부분 문제(Overlapping Subproblems): 부분 문제들의 ...

이분 탐색(Binary Search) 개요 탐색 기법중 하나로, 배열이 정렬되어 있을 때 사용할 수 있다. 간단히 설명하자면, 배열의 중간 값이 자신이 찾는 값인지 확인하고 찾는 값이 아니면 배열을 왼쪽 절반, 또는 오른쪽 절반으로 범위를 줄여나가며 자신이 원하는 값을 찾을 때 까지 반복해 나가는 알고리즘이다. 시간복잡도는 $O(logN)$이다....

개요 Meet int the middle (중간에서 만나기), 줄여서 MITM 알고리즘이란 부르트포스 알고리즘을 사용하여 문제를 해결할 때 시간복잡도를 줄이기 위해서 사용되는 테크닉으로, 쉽게 설명하면 문제를 반으로 나누어 각각 해결한 후 중간에서 만나 최종적인 문제를 해결하는 알고리즘이다. BOJ 2295 (세 수의 합) https://www.a...

헷깔려서 적은 문자 및 문자열 관련 입력 정리 (유니코드는 제외했다.) 포스트에서 활용할 변수들 string 객체 #include <iostream> std::string str; 비고: STL에서 제공하는 클래스 문자열 끝에 '\0' 문자가 들어가지 않음 <iostream> 헤더는 <string> 헤더를...

이 글은 2023년 12월 31일에 작성된 회고록을 바탕으로 블로그 첫 포스팅 겸 일부 수정되어 작성되었습니다. 23-1학기 프로그래밍기초 1 이 분야에 입문하게 되었을때 전공수업이 정말 도움이 되었다. 분반당 5명씩 추가신청을 받는다고 하길래 아침 9시에 PC방으로 달려가서 미친듯이 광클해서 잡은 수업인데 23-1학기때 들었던 수업중에 가장...