본문 바로가기

Solved.ac26

[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.
[BOJ] 백준 1929번: 소수 구하기, 에라토스테네스의 체 어떤 수 X가 소수인지 판별하는 것은 O(lgX) 복잡도로 판별 가능합니다. 2~x^1/2 범위 내에서 하나라도 나누어 떨어지는 수가 있다면 그 수는 소수가 아니게 되죠. 범위 a~b 사이의 모든 수를 위의 아이디어로 판별한다고 해도 무리는 없습니다. 다만 우리는 좀 더 효율적으로 소수를 찾고 이를 활용할 수 있습니다. 특정 범위에 존재하는 수들 중 소수를 찾는 문제는 에라토스네테스의 체를 이용합니다. www.acmicpc.net/problem/1929 1929번: 소수 구하기 첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다. www.acmicpc.net 1929번: 소수 구하기 문제는 N이 1.. 2020. 9. 7.
[BOJ] 백준 1014번: 컨닝 https://www.acmicpc.net/problem/1014 1014번: 컨닝 문제 최백준은 서강대학교에서 “컨닝의 기술”이라는 과목을 가르치고 있다. 이 과목은 상당히 까다롭기로 정평이 나있기 때문에, 몇몇 학생들은 시험을 보는 도중에 다른 사람의 답지를 베끼 www.acmicpc.net 교실 정보가 주어질 때, 위의 그림처럼 컨닝이 가능해 A,C,D,E 중 한 자리라도 사람이 앉아있으면 컨닝을 방지하기 위하여 해당 자리를 앉지못하게 합니다. 위의 규칙을 만족하면서 최대한 몇명의 사람이 앉을 수 있는지 구하는 문제입니다. 저는 동적계획법으로 해결하였습니다. (입력이 10X10이므로 꽤 다양한 알고리즘으로 해결가능하다고 생각합니다.) DP[i][j] 는 i-1번째 줄에 j 상태로 앉아있을 때 i번째.. 2020. 8. 11.

티스토리툴바