복습 정리 노트

이 포스트에서는 C++으로 작성된 각종 알고리즘들의 형식적으로 코드를 정리하였습니다. 코드를 작성할 때마다 그 형태와 구성이 달라지면 불편하기 때문에 이를 해결하고자 작성하게 되었습니다. - 각 알고리즘은 분야별로 정리되어 있습니다. (분류된 분야가 정확하지 않을 수 있습니다.) - 같은 분야 내에서는 웬만하면 난이도 오름차순으로 정리하고자 하였습니다. ** 개인적으로 자주 사용하는 알고리즘 위주로 정리하였습니다! (필요한 알고리즘이 없을 수도 있음) 알고리즘은 참고용으로만 봐주세요. 문제 풀이를 할 때는, 웬만해서는 직접 다시 생각해보면서 코드를 직접 작성하는 것을 추천합니다. 코드는 포스트의 가독성을 최대화하고자 접은 글에 정리하였으니, 접은 글을 펼쳐서 코드를 복사하시면 됩니다. + 일부 알고리즘은..

이 포스트에서는 프로그래밍 문제 사이트 백준 Online Judge의 17441번 : '파리채 만들기' 문제의 풀이 코드와 해설을 다루고 있습니다. 문제의 난이도는 Solved.ac 기준 Diamond II이며, 문제를 풀이하기 위해 미적분학II의 그린 정리에 대해 알고 있으면 좋습니다. 17441번 : 파리채 만들기 문제를 요약하면, 주어진 다각형 내의 두 점 사이 거리의 제곱에 대한 평균값을 출력하는 문제입니다. 다각형은 단순다각형이며, 반시계 방향으로 꼭짓점들의 좌표가 주어지기 때문에 Convex Hull 알고리즘의 사용은 생략해도 됩니다. 이 문제는 풀이 코드를 먼저 본다고 해서 이해할 수가 없는 문제이므로, 풀이를 먼저 하고 코드를 정리하겠습니다. 저도 미적분학II를 충분히 배웠지만 손 뗀지 2..

이 포스트에서는 프로그래밍 문제 사이트 백준 Online Judge의 3356번 : '라디오 전송', 3779번 : '주기' 문제의 풀이 코드와 해설을 다루고 있습니다. 문제 난이도는 Solved.ac 기준 Platinum 티어에 해당하며, 문제를 풀이하기 위해 문자열 탐색 알고리즘인 KMP 알고리즘에 대한 이해가 필요합니다. 3356번 : 라디오 전송 반복되어 나오는 문자열이 주어졌을 때, 가능한 가장 짧은 부분 문자열의 길이를 출력하는 문제입니다. 문자열이 반복되어 나온다는 점에서 이전에 풀이한 1305번 : '광고' 문제와 똑같습니다. [C++ 백준 풀이] 16900번 : 이름 정하기 / 1305번 : 광고 / 1498번 : 주기문 (KMP 응용) 이 포스트는 프로그래밍 문제 사이트 백준 Onlin..

이 포스트는 프로그래밍 문제 사이트 백준 Online Judge의 16900번 : '이름 정하기', 1305번 : '광고', 1498번 : '주기문' 문제의 풀이 코드와 해설을 다루고 있습니다. 문제 난이도는 Solved.ac 기준 Platinum 티어에 해당하며, 문제를 풀이하기 위해 문자열 탐색 알고리즘인 KMP 알고리즘에 대한 이해가 필요합니다. [C++ 알고리즘] KMP 알고리즘 (O(N+M) 문자열 탐색 알고리즘) 이 포스트에서는 O(N+M) 시간 문자열 탐색 알고리즘인 KMP 알고리즘에 대해 다루고 있습니다. 또한 KMP 알고리즘에 대해 설명하기 위해, 프로그래밍 문제 사이트 백준 Online Judge의 16916번 : '부분 문 restudycafe.tistory.com KMP 알고리즘 코..

이 포스트에서는 프로그래밍 문제 사이트 백준 Online Judge의 11585번 : '속타는 저녁 메뉴', 12104번 : '순환 순열', 16570번 : '앞뒤가 맞는 수열'의 풀이 코드와 해설을 다루고 있습니다. 문제의 난이도는 Solved.ac 기준 Platinum 티어에 해당하며, 문제를 풀이하기 위해 KMP 알고리즘에 대한 이해가 필요합니다. 11585번 : 속타는 저녁 메뉴 룰렛을 돌려서 원래 모양과 같아지는 배열이 몇 가지인지 그 비중을 출력하는 문제입니다. 문제만 읽어도 한 눈에 KMP 알고리즘을 사용하는 문제라는 것을 깨달을 수 있는 쉬운 유형의 문제입니다. ↓ 풀이 코드는 아래의 접은 글에 정리되어 있습니다. 더보기 #include #include #include using names..

이 포스트에서는 프로그래밍 문제 사이트 백준 Online Judge의 7575번 : '바이러스', 10266번 : '시계 사진들' 문제에 대한 풀이 코드와 해설을 다루고 있습니다. 문제 난이도는 Solved.ac 기준 Platinum V에 해당하며, 문제를 풀이하기 위해 KMP 알고리즘에 대한 이해가 필요합니다. [C++ 알고리즘] KMP 알고리즘 (O(N+M) 문자열 탐색 알고리즘) 이 포스트에서는 O(N+M) 시간 문자열 탐색 알고리즘인 KMP 알고리즘에 대해 다루고 있습니다. 또한 KMP 알고리즘에 대해 설명하기 위해, 프로그래밍 문제 사이트 백준 Online Judge의 16916번 : '부분 문 restudycafe.tistory.com KMP 알고리즘에 대한 원리와 코드 설명은 위의 링크에 정..

이 포스트에서는 프로그래밍 문제 사이트 백준 Online Judge의 1893번 : '시저 암호'와 4354번 : '문자열 제곱' 문제에 대한 풀이 코드와 해설을 다루고 있습니다. 문제 난이도는 Solved.ac 기준 Platinum V에 해당하며, 문제 풀이를 위해 KMP 알고리즘에 대한 이해가 필요합니다. 1893번 : 시저 암호 알파벳과 찾을 문자열, 그리고 암호문이 순서대로 주어졌을 때, 주어진 알파벳 순서대로 shift한 문자열이 암호문에서 한 번만 등장하게 하는 shift 값을 출력하는 문제입니다. 알파벳 순서 자체를 정해주므로 주어진 알파벳대로 shift 해야하며, 암호문에서 2번 이상 등장하는 문자열은 배제해야 하기 때문에 고려해야 할 조건이 쉽지 않은 문제입니다. #include #inc..

이 포스트에서는 프로그래밍 문제 사이트 백준 Online Judge의 1701번 : 'Cubeditor' 문제의 풀이 코드와 해설을 다루고 있습니다. 문제 난이도는 Solved.ac 기준 Gold ~ Platinum 티어에 해당하며, 문제를 풀이하기 위해 KMP 문자열 검색 알고리즘에 대한 이해가 필요합니다. 1701번 : Cubeditor 주어진 문자열에서 두 번 이상 나오는 부분 문자열이 있을 때, 이들 중 가장 긴 길이를 출력하는 문제입니다. (물론 존재하지 않는 경우 답은 0이 됨) [C++ 알고리즘] KMP 알고리즘 (O(N+M) 문자열 탐색 알고리즘) 이 포스트에서는 O(N+M) 시간 문자열 탐색 알고리즘인 KMP 알고리즘에 대해 다루고 있습니다. 또한 KMP 알고리즘에 대해 설명하기 위해, ..

이 포스트에서는 O(N+M) 시간 문자열 탐색 알고리즘인 KMP 알고리즘에 대해 다루고 있습니다. 또한 KMP 알고리즘에 대해 설명하기 위해, 프로그래밍 문제 사이트 백준 Online Judge의 16916번 : '부분 문자열' 문제의 풀이 코드와 해설을 다루고 있습니다. (문제의 난이도는 Solved.ac 기준 Gold III에 해당합니다.) BOJ는 문제 자체가 특정 알고리즘을 구현하는 것을 목적으로 만들어진 것이 많기 때문에, 알고리즘에 대한 설명을 바로 예제를 풀면서 같이 정리하도록 하겠습니다. 16916번 : 부분 문자열 문자열 S와 검색할 부분 문자열 P가 순서대로 입력되었을 때, P가 S의 부분 문자열인지 검사하는 문제입니다. 문자열 S의 길이를 N, 부분 문자열 P의 길이를 M이라고 하였을..

이 포스트에서는 프로그래밍 문제 사이트 백준 Online Judge의 11686번 : 'Saint John Festival' 문제의 풀이 코드와 해설을 다루고 있습니다. 문제의 난이도는 Solved.ac 기준 Platinum II에 해당하며, 문제를 풀이하기 위해 Convex Hull 알고리즘과 볼록다각형 내부의 점 판정 알고리즘(O(log N))에 대해 알아야합니다. 이 포스트에 볼록 다각형 내부의 점 판정 알고리즘을 깔끔하게 정리한 코드를 정리합니다. 11686번 : Saint John Festival Large sky lanterns들 중에서 3개를 선택하여 만들 수 있는 삼각형에 포함되는 small sky lanterns의 수를 구하는 문제입니다. Convex Hull 알고리즘을 사용하여 가장 큰..