mojo's Blog

문제 링크 => 2805번: 나무 자르기 (acmicpc.net) 2805번: 나무 자르기 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보 www.acmicpc.net 처음으로 접한 이분탐색 문제가 이 문제인거 같다. 나무를 자르는 범위를 first ~ end사이에 존재한다고 할 때 다음과 같은 과정을 통해 구해주도록 한다. (이때 first = 0, end = 나무들 중에 최댓값) (1) 범위의 first 값이 end 값보다 큰 경우가 아닐 경우 계속해서 찾아주도록 한다. (2) first 값과 end 값 사이의 값을 m..

문제 링크 => 5525번: IOIOI (acmicpc.net) 5525번: IOIOI N+1개의 I와 N개의 O로 이루어져 있으면, I와 O이 교대로 나오는 문자열을 PN이라고 한다. P1 IOI P2 IOIOI P3 IOIOIOI PN IOIOI...OI (O가 N개) I와 O로만 이루어진 문자열 S와 정수 N이 주어졌을 때, S안에 PN이 몇 www.acmicpc.net 문자열 관련 문제이다. 이문제의 핵심은 시간복잡도 O(N) 으로 해결하도록 하는것이다. 문자열의 index = 0 부터 접근한다고 할 때, 'I' 를 발견하는 경우에 대해 살펴보도록 한다. (이때, 'O', 'I' 가 iterate 하는 것을 판별하기 위한 변수 j 와 IOI, IOIOI, IOIOIOI, ... 를 판별하기 위한 ..

문제 링크 => 7662번: 이중 우선순위 큐 (acmicpc.net) 7662번: 이중 우선순위 큐 입력 데이터는 표준입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터의 첫째 줄에는 Q에 적 www.acmicpc.net 이 문제는 multiset을 이용해서 푸는 문제이다. multiset은 원소들의 중복을 허용하며 정렬, 삭제, 삽입 등 이러한 operation을 O(logN) 만큼 빠르게 진행 해준다는 점에서 유용하다. ( 원소들이 Tree 구조로 되어있어서 시간복잡도가 logN 임을 알 수 있다 ) 이 문제를 통해 multiset 에 대한 사용법을 익히면 좋을듯 하다. 풀이 Code => #defin..

문제 링크 => 2151번: 거울 설치 (acmicpc.net) 2151번: 거울 설치 첫째 줄에 집의 크기 N (2 ≤ N ≤ 50)이 주어진다. 다음 N개의 줄에는 N개의 문자로 집에 대한 정보가 주어진다. ‘#’는 문이 설치된 곳으로 항상 두 곳이며, ‘.’은 아무 것도 없는 것으로 빛은 www.acmicpc.net BFS 문제이며 문제를 접근한 알고리즘은 다음과 같다. 1. 시작 지점의 방향은 -1로 설정해두고 그 이후로는 0~3(상하좌우) 가 되도록 구현하였다. => 이때, class Light 를 활용하여 위치(x, y), 방향(direction)을 설정하도록 하였고, queue q; 에서 int는 거울을 배치한 갯수를 담도록 설정하였다. 또한 시작지점의 방문처리도 해주었다. (1로 설정하였는..