취업 준비 및 일상

문제 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가지고 있고, 이 크기는 자연수이다. 가장 처음에 아기 상어의 크기는 2이고, 아기 상어는 1초에 상하좌우로 인접한 한 칸씩 이동한다. 아기 상어는 자신의 크기보다 큰 물고기가 있는 칸은 지나갈 수 없고, 나머지 칸은 모두 지나갈 수 있다. 아기 상어는 자신의 크기보다 작은 물고기만 먹을 수 있다. 따라서, 크기가 같은 물고기는 먹을 수 없지만, 그 물고기가 있는 칸은 지나갈 수 있다. 아기 상어가 어디로 이동할지 결정하는 방법은 아래와 같다. 더 이상 먹을 수 있는 물고기가 공간에 없다면 아기 상어는 엄마..

처음으로 온라인 대회에 참여해 보았다(https://www.acmicpc.net/category/detail/3030). A: blobnom 탑의 구조상 2칸 이상 떨어진 블롭을 가져올 수 없다. 따라서, 그리디하게 max(탑의 양 끝의 blob 수, max(i(1~N-2)번째 타워의 blob 수 + min(i-1번째 타워의 blob 수, i+1번째 타워의 blob 수)로 구하면 된다. 첫 번째 문제다보니 가장 쉽다고 느껴지는데, 가장 탑의 양 끝 값 등의 세부 고려 사항이 살짝 있어서 정답률이 마냥 높지는 않다. 나는 3번 틀렸다 ㅎㅎ 코드 더보기 더보기 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStre..

문제 주헌이는 매운맛을 좋아한다. 정확히는, 매운맛을 먹음으로써 느낄 수 있는 고통에서 희열을 느끼는 진정한 '즐기는 자'다. '스코빌 지수'란 고추류가 가진 매운맛의 원인인 캡사이신의 농도를 수치화 한 단위이다. 주헌이가 느끼는 매운 정도는 굉장히 독특한데, 먹고 있는 메뉴의 절대 수치가 아닌 음식과의 상대수치에 기반한다. 예를 들어 [5, 2, 8]의 스코빌 지수를 가진 음식을 먹을 때 주헌이가 느끼는 매운 정도는 가장 높은 수치인 8과 가장 낮은 수치인 2의 차이인 6만큼의 매운맛을 느낀다. 이처럼 메뉴들의 스코빌 지수가 있을 때 그 최댓값과 최솟값의 차이를 "주헌고통지수"라고 정의한다. 그림1. 고추처럼 보이지만 문제와는 무관합니다. 최근 주헌이에게 좋아하는 매운맛 전문점이 생겼다. 메뉴가 아주 ..

문제 아주 먼 미래에 사람들이 가장 많이 사용하는 대중교통은 하이퍼튜브이다. 하이퍼튜브 하나는 역 K개를 서로 연결한다. 1번역에서 N번역으로 가는데 방문하는 최소 역의 수는 몇 개일까? 입력 첫째 줄에 역의 수 N과 한 하이퍼튜브가 서로 연결하는 역의 개수 K, 하이퍼튜브의 개수 M이 주어진다. (1 ≤ N ≤ 100,000, 1 ≤ K, M ≤ 1000) 다음 M개 줄에는 하이퍼튜브의 정보가 한 줄에 하나씩 주어진다. 총 K개 숫자가 주어지며, 이 숫자는 그 하이퍼튜브가 서로 연결하는 역의 번호이다. 출력 첫째 줄에 1번역에서 N번역으로 가는데 방문하는 역의 개수의 최솟값을 출력한다. 만약, 갈 수 없다면 -1을 출력한다. 풀이 1. 그래프를 인접 행렬로 저장: 역이 최대 10만개, N^2 == 10..

* 바킹독, 위키피디아 등을 참고하여 작성함. 목차 1. O(N^2) 시간복잡도 정렬 알고리즘 - 선택 정렬, 버블 정렬 2. O(NlogN) 시간복잡도 정렬 알고리즘 - 병합 정렬, 퀵소트 3. Non-comparison sorts: 카운팅 정렬, 기수 정렬 4. JAVA에서의 사용 ※ 구분 stable sort: 크기가 같은 원소들끼리 정렬 후에도 원래의 유지하는 정렬 알고리즘(↔ unstable sort) comparison sort: 우리가 일반적으로 아는, 원소의 값끼리 비교하여 정렬하는 알고리즘(↔ non-comparison sort) 1. O(N^2) 시간복잡도 정렬 알고리즘 일반적으로 구현하기 쉽다. 실제로 쓰이지 않으며, '선택 정렬과 버블 정렬의 차이점을 설명하여라'와 같은 지엽적인 질..

문제 준석이는 영어 단어를 외우려고 한다. 사전에는 N가지 단어가 적혀 있다. 모든 단어는 소문자이다. 단어 안에 있는 모든 알파벳을 알 때, 그 단어를 완전히 안다고 한다. 다음과 같은 쿼리들이 주어진다. 1 x : 알파벳 x를 잊는다. 2 x : 알파벳 x를 기억해 낸다. 처음에 모든 알파벳을 기억하는 상태고, 모음은 완벽하게 외웠기 때문에 절대 잊지 않는다. 각 쿼리마다 완전히 알고 있는 단어의 개수를 출력하여라. 입력 첫 번째 줄에는 정수 N (1 ≤ N ≤ 104)과 M (1 ≤ M ≤ 5×104)이 주어진다. 다음 N개의 줄에는 문자열이 하나씩 주어진다. 문자열의 길이는 103을 넘지 않는다. 다음 M개의 줄에는 정수 o와 문자 x가 한 줄씩 주어진다. o는 1, 2중 하나이고, x는 알파벳 ..

문제 오늘은 공주님이 태어난 경사스러운 날이다. 왕은 이 날을 기념하기 위해 늘 꽃이 피어있는 작은 정원을 만들기로 결정했다. 총 N개의 꽃이 있는 데, 꽃은 모두 같은 해에 피어서 같은 해에 진다. 하나의 꽃은 피는 날과 지는 날이 정해져 있다. 예를 들어, 5월 8일 피어서 6월 13일 지는 꽃은 5월 8일부터 6월 12일까지는 꽃이 피어 있고, 6월 13일을 포함하여 이후로는 꽃을 볼 수 없다는 의미이다. (올해는 4, 6, 9, 11월은 30일까지 있고, 1, 3, 5, 7, 8, 10, 12월은 31일까지 있으며, 2월은 28일까지만 있다.) 이러한 N개의 꽃들 중에서 다음의 두 조건을 만족하는 꽃들을 선택하고 싶다. 공주가 가장 좋아하는 계절인 3월 1일부터 11월 30일까지 매일 꽃이 한 가..

문제 한 개의 회의실이 있는데 이를 사용하고자 하는 N개의 회의에 대하여 회의실 사용표를 만들려고 한다. 각 회의 I에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 회의의 최대 개수를 찾아보자. 단, 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다. 회의의 시작시간과 끝나는 시간이 같을 수도 있다. 이 경우에는 시작하자마자 끝나는 것으로 생각하면 된다. 입력 첫째 줄에 회의의 수 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N+1 줄까지 각 회의의 정보가 주어지는데 이것은 공백을 사이에 두고 회의의 시작시간과 끝나는 시간이 주어진다. 시작 시간과 끝나는 시간은 231-1보다 작거..

문제 세준이는 양수와 +, -, 그리고 괄호를 가지고 식을 만들었다. 그리고 나서 세준이는 괄호를 모두 지웠다. 그리고 나서 세준이는 괄호를 적절히 쳐서 이 식의 값을 최소로 만들려고 한다. 괄호를 적절히 쳐서 이 식의 값을 최소로 만드는 프로그램을 작성하시오. 입력 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 많이 연속되는 숫자는 없다. 수는 0으로 시작할 수 있다. 입력으로 주어지는 식의 길이는 50보다 작거나 같다. 출력 첫째 줄에 정답을 출력한다. 풀이 나는 풀었다. 다만 바킹독 선생님 깃허브에 올려져 있는 풀이가 아름다워 이를 JAVA로 옮겨 기..

문제 오전 4시, 민재는 윷놀이를 하고 싶어졌다. 하지만 다들 자는 시간이라 윷놀이를 같이 할 사람은 없었다. 민재는 윷놀이를 혼자 할 수 있는 방법을 생각해냈다. 혼자 하는 윷놀이에 적용되는 규칙은 다음과 같다. 처음에 말은 윷판의 오른쪽 아래에 위치한다. 열 번의 차례 안에 말 하나가 완주하면 민재가 승리한다. 차례 한 번에는 윷가락 네 개를 던진 후: 뒷면이 하나인 경우 말을 한 칸 전진시킨다. 뒷면이 둘인 경우 말을 두 칸 전진시킨다. 뒷면이 셋인 경우 말을 세 칸 전진시킨다. 모두 뒷면인 경우 말을 네 칸 전진시킨 뒤, 윷을 추가로 던진다. 모두 앞면인 경우 말을 다섯 칸 전진시킨 뒤, 윷을 추가로 던진다. 윷판을 정해진 경로로 한 바퀴를 돌아 윷판의 오른쪽 아래에 도착한 뒤 한 칸 더 움직여야..