백준 1654 랜선 자르기는 전형적인 이분 탐색 문제이다. 문제에서 1~ 2^31-1에 해당하는 랜선길이에 대해 필요한 랜선 개수를 만들 수 있는 최대 랜선 길이를 알아내 출력하는 문제이다. 2^31-1 까지 모든 길이에 대하여 해보면 답은 나오겠지만 이 방법은 너무 느려 시간초과가 뜰 것이다. 그렇다면 여기서 이분 탐색을 이용하여 문제를 풀어나갈
백준 9933 민균이의 비밀번호는 주어지는 문자열이 주어진 문자열 집합에서 거꾸로 된 것과 같은 것이 있는지 확인하고 찾아 출력하는 문제이다. 너무 간단한 문제라고 생각하고 주어진 문자열에서 뒤집어서 같은 문자열이 있는지만 확인했는데 오답이 나와 무엇이 잘못됬는지 잘 몰랐다. 이 문제에는 예외가 존재하는데 길이가 1일 때와 여러개의 문자열이 있어도 문
백준 문자열 폭발은 문자열과 폭발 문자열이 주어지고 폭발 문자열을 입력받아 이 폭발문자열을 터뜨려 나온 최종 문자열을 구하는 문제이다. 폭발 문자열이 터져서 또한번 폭발문자열을 이룰 수 있으니 이점에 주의하여 풀어야 한다. 처음에는 단순히 str.find(“폭발문자열”)을 찾아 서브 스트링으로 조합한뒤 찾을 문자열이 없을때 까지 진행했는데 이 방법은
백준 14888 연산자 끼워넣기는 아주 쉬운 dfs문제이다. 숫자 1 2 3 4 5 6 이 주어지고 사용할 수 있는 연산자 + - * / 의 갯수가 주어지면 이 연산을 사용하여 앞에서부터 차례대로 연산한 결과의 최대값, 최솟값을 구하는 문제이다. 연산자 우선순위를 고려해야 하는 문제이면 꽤나 까다로운 문제이겠지만 순서대로 계산하므로 어렵지 않은 문제
파일 합치기 문제는 인접한 파일을 합치고 합쳐진 파일을 다른 파일과 합쳐나가며 이 파일을 합치는데 필요한 비용을 최소화 하는 문제이다. 이 문제는 동적 계획법으로 풀 수 있다. 이 부분에 대한 개념은 구간에 대한 개념으로 나누어 보면 쉽게 풀 수 있다. 1 ~ n까지의 구간이 있다고 하면 1~n까지의 구간의 합을 최소로 만드는 것은 임의의 j에 대하여