mojo's Blog

문제 링크 => 19637번: IF문 좀 대신 써줘 (acmicpc.net) 19637번: IF문 좀 대신 써줘 첫 번째 줄에는 칭호의 개수 N (1 ≤ N ≤ 105)과 칭호를 출력해야 하는 캐릭터들의 개수 M (1 ≤ M ≤ 105)이 빈칸을 사이에 두고 주어진다. (1 ≤ N, M ≤ 105) 두 번째 줄부터 N개의 줄에 각 칭 www.acmicpc.net 이분탐색 문제이다. 이문제에서 Input 은 n 개의 (string, long long) 형태로 주어지는데 long long 값이 오름차순으로 주어지는 것에 대해서 눈여겨 볼 필요가 있다. 즉, 벡터에다가 값을 push한 후에 정렬하는 operation을 하지 않고 바로 이분탐색을 할 수 있다는 것이 핵심이다. 풀이 code #define _CR..

문제 링크 => 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로 설정하였는..