Algorithm76 [알고리즘] 중량제한 (백준 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. [알고리즘] 이분 탐색 (Binary Search) 이분 탐색 (Binary Search) O( log N )의 시간 복잡도로 전체 배열에서 특정 값을 찾아내는 방법 이 때 배열은 무조건 정렬이 되어있어야함 반복문 실행할 때마다 탐색 범위를 왼쪽 절반 혹은 오른쪽 절반으로 줄여 나감 응용 최대값, 혹은 최소값을 찾는 문제 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 알고리즘 left = index 최소 값 right = index 최대 값 반복문 실행 left가 right 보다 이하일 동안 반복 (left m.. 2020. 8. 31. [알고리즘] 후위 표기식 (백준 1918번) 1918번: 후위 표기식 첫째 줄에 중위 표기식이 주어진다. 단 이 수식의 피연산자는 A~Z의 문자로 이루어지며 수식에서 한 번씩만 등장한다. 그리고 -A+B와 같이 -가 가장 앞에 오거나 AB와 같이 *가 생략되는 등의 수식�� www.acmicpc.net 설마 이 문제 푼다고 한나절이 꼬박 걸릴지 몰랐다. 이전에 스택 활용에서 중위 표기식 → 후위 표기식 변환하는 메서드를 작성한 적이 있는지라 바로 할 수 있을 줄 알았는데 조건이 하나 더 있었다. 연산자 간의 우선순위를 고려해야한다. 즉 a+b*c 는 abc*+ 가 되어야한다. (오답 : ab+c*) 처음엔 무식하게 괄호를 직접 수식에 때려박을까 했는데 결국 안되었고 온전히 스택의 순수 기능을 활용하기로 했다. Solution 각 연산자의 우선순위를.. 2020. 8. 31. [알고리즘] 에디터 (백준 1406번) 1406번: 에디터 첫째 줄에는 초기에 편집기에 입력되어 있는 문자열이 주어진다. 이 문자열은 길이가 N이고, 영어 소문자로만 이루어져 있으며, 길이는 100,000을 넘지 않는다. 둘째 줄에는 입력할 명령어의 개수� www.acmicpc.net 자료구조를 적절히 사용해서 시간 효율성을 따지는 문제이다. 함부로 내장 라이브러리를 사용하게 된다면 O(NM) 시간이 걸리기에 무조건 시간초과가 발생한다. 때문에 한 번에 명령에 O(1) 시간이 걸려야하므로 총 O(M) 시간에 문제를 해결해야 한다. Solution 기본적으로 ArrayList, LinkedList 등은 내부적으로 값을 삽입, 조회, 삭제 시 O(N)시간이 걸리기에 사용해선 안된다. 난 Stack 2개를 활용해서 커서를 기준으로 왼쪽 문자열 스택.. 2020. 8. 31. 이전 1 ··· 12 13 14 15 16 17 18 19 다음
