백준30 [알고리즘] 중량제한 (백준 1939번) 1939번: 중량제한 첫째 줄에 N, M(1≤M≤100,000)이 주어진다. 다음 M개의 줄에는 다리에 대한 정보를 나타내는 세 정수 A, B(1≤A, B≤N), C(1≤C≤1,000,000,000)가 주어진다. 이는 A번 섬과 B번 섬 사이에 중량제한이 C인 다리 www.acmicpc.net 전형적인 'BFS + BinarySearch' 유형의 문제이다. BinarySearch로 최대값 혹은 최소값을 찾되 BFS로 현재 값이 타당한지를 판단하는 문제 유형이다. Solution 이 문제는 트럭에 실릴 수 있는 최대 중량을 구하라는 문제이다. 만약 트럭의 특정 중량을 기준으로 도착지까지 갈 수 없다면, 그보다 더 높은 중량으로는 당연히 도착지까지 갈 수가 없기에 search하는 값들이 정렬이 되어 있기에 .. 2020. 9. 1. [알고리즘] 에디터 (백준 1406번) 1406번: 에디터 첫째 줄에는 초기에 편집기에 입력되어 있는 문자열이 주어진다. 이 문자열은 길이가 N이고, 영어 소문자로만 이루어져 있으며, 길이는 100,000을 넘지 않는다. 둘째 줄에는 입력할 명령어의 개수� www.acmicpc.net 자료구조를 적절히 사용해서 시간 효율성을 따지는 문제이다. 함부로 내장 라이브러리를 사용하게 된다면 O(NM) 시간이 걸리기에 무조건 시간초과가 발생한다. 때문에 한 번에 명령에 O(1) 시간이 걸려야하므로 총 O(M) 시간에 문제를 해결해야 한다. Solution 기본적으로 ArrayList, LinkedList 등은 내부적으로 값을 삽입, 조회, 삭제 시 O(N)시간이 걸리기에 사용해선 안된다. 난 Stack 2개를 활용해서 커서를 기준으로 왼쪽 문자열 스택.. 2020. 8. 31. [알고리즘] 쇠막대기 (백준 10799번) 10799번: 쇠막대기 여러 개의 쇠막대기를 레이저로 절단하려고 한다. 효율적인 작업을 위해서 쇠막대기를 아래에서 위로 겹쳐 놓고, 레이저를 위에서 수직으로 발사하여 쇠막대기들을 자른다. 쇠막대기와 레이저� www.acmicpc.net 스택 사용 문제이다. 생각보다 해결 방법을 떠올리는 데 시간이 오래 걸렸다. 막대기가 겹쳐져있다는 조건 때문에 당황했다. 다른 사람들은 더 효율적인 방법으로 하긴 했는데 우선 내가 한 방법은 레이저를 나타내는 "()" 괄호쌍을 다른 문자로 대체하고 닫힌 괄호 ')'를 만났을 때 괄호쌍 대신 저장해놓은 문자들을 pop해서 개수를 센 뒤 문자 개수 +1 만큼 결과값에 더하는 방법을 택했다. import org.omg.PortableInterceptor.INACTIVE; imp.. 2020. 8. 30. [알고리즘] 찾기 KMP (백준 1786번) 1786번: 찾기 첫째 줄에, T 중간에 P가 몇 번 나타나는지를 나타내는 음이 아닌 정수를 출력한다. 둘째 줄에는 P가 나타나는 위치를 차례대로 출력한다. 예컨대, T의 i～i+m-1번 문자와 P의 1～m번 문자가 차례로 � www.acmicpc.net 정확하게 KMP를 구현하는 문제다. 패턴 매칭 실패 시 패턴 인덱스 j 가 돌아갈 곳을 지정하는 failureFunction을 구하는 메서드와 그걸 이용해서 패턴 매칭을 하는 KMP 메서드로 이루어져있다. 주로 겹쳐져있는 패턴도 찾아낼 때에 사용한다. EX) 텍스트 : ababa, 패턴 : aba → 패턴 개수 : 2개 String.replace로는 찾아낼 수 없는 경우임 import java.io.BufferedReader; import java.io.. 2020. 8. 27. 이전 1 ··· 3 4 5 6 7 8 다음
