본문 바로가기

백준61

[BOJ] 백준 5525번: IOIOI www.acmicpc.net/problem/5525 5525번: IOIOI 첫째 줄에 N이 주어진다. 둘째 줄에는 S의 길이 M이 주어지며, 셋째 줄에 S가 주어진다. (1 ≤ N ≤ 1,000,000, 2N+1 ≤ M ≤ 1,000,000) www.acmicpc.net 문자열을 탐색하면서 I 문자가 최대 몇 번째 Pn의 마지막 I에 해당하는지를 찾으면 쉽게 풀수있습니다. 만약 IOIOIOI 에서 세 번째 I에 대하여 str[i-2]가 I고 str[i-1]가 O이므로 P[i] = P[i-2] + 1을 갖습니다. 예제로 주어진 OOIOIOIOIIOII 의 P[1..N] = { 0, 0, 0, 0, 1, 0, 2, 0, 3, 0, 0, 1, 0} 처럼 구해집니다.이렇게 구한 P에서 길이 M보다 큰 값을 같은.. 2020. 9. 7.
c++ sort 함수 커스텀, 특정 조건 정렬, 우선순위 큐 정렬 기본적인 삽입 정렬 및 선택 정렬은 아래 링크를 참조해주세요 2020/10/21 - [알고리즘] - 삽입 정렬 (InsertionSort), 선택 정렬 (Selection Sort) 비교 및 c언어 구현 삽입 정렬 (InsertionSort), 선택 정렬 (Selection Sort) 비교 및 c언어 구현 삽입 정렬과 선택 정렬은 O(N^2)의 비효율적인 정렬 방법입니다. 효율적인 정렬을 구현하고 싶으시면 아래 링크를 봐주세요 2020/08/17 - [알고리즘] - 머지 소트, 머지 소트 트리 및 관련 백준 문제 �� seongjuk.tistory.com 알고리즘 문제를 해결하다보면 algorithm 헤더의 sort 함수를 유용하게 사용합니다. 이 sort 함수를 기존(Default) 정렬 방식이 아닌 .. 2020. 9. 7.
[BOJ] 백준 9012번: 괄호 www.acmicpc.net/problem/9012 9012번: 괄호 괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인 ‘(’ 와 ‘)’ 만으로 구성되어 있는 문자열이다. 그 중에서 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열(Valid PS, VPS)이라고 www.acmicpc.net 괄호 '(' 와 ')' 가 주어졌을 때 ( )는 올바른 문자열이며 올바른 문자열 S에 대하여 ( S ) 도 올바른 문자열이고, 올바른 문자열 T와 ST를 이루는 것도 올바른 문자열일 때, 주어진 괄호 문자열이 올바른 문자열인지 판별하는 문제입니다. 문자열을 탐색하는 중 현재 문자가 ( 라면, 이 후 가장 먼저오는 )와 짝을 이뤄야합니다. Last in First out 의 특징을 .. 2020. 9. 7.
[BOJ] 백준 1654번: 랜선 자르기, 이분 탐색 (Binary Search) www.acmicpc.net/problem/1654 1654번: 랜선 자르기 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 www.acmicpc.net 이 문제는 주어진 랜선 K개의 길이를 잘라 같은 길이의 N개를 만들 때 최대 랜선의 길이를 구하는 문제입니다. 랜선의 길이가 INT_MAX 값보다 작거나 같은 자연수 이므로 Naive한 방법으로는 시간초과가 발생하므로 해결할 수 없습니다. 자를 수 있는 랜선 길이의 범위 내에서 가능한 최대 길이를 구하는 문제로 정렬된 순열에서 특정 값을 찾는 문제로 해석할 수 있고 이는 이분 탐색을.. 2020. 9. 7.

티스토리툴바