취업 준비 및 일상

문제 선주는 자신이 운영하는 N개의 논에 물을 대려고 한다. 물을 대는 방법은 두 가지가 있는데 하나는 직접 논에 우물을 파는 것이고 다른 하나는 이미 물을 대고 있는 다른 논으로부터 물을 끌어오는 법이다. 각각의 논에 대해 우물을 파는 비용과 논들 사이에 물을 끌어오는 비용들이 주어졌을 때 최소의 비용으로 모든 논에 물을 대는 것이 문제이다. 입력 첫 줄에는 논의 수 N(1 ≤ N ≤ 300)이 주어진다. 다음 N개의 줄에는 i번째 논에 우물을 팔 때 드는 비용 Wi(1 ≤ Wi ≤ 100,000)가 순서대로 들어온다. 다음 N개의 줄에 대해서는 각 줄에 N개의 수가 들어오는데 이는 i번째 논과 j번째 논을 연결하는데 드는 비용 Pi,j(1 ≤ Pi,j ≤ 100,000, Pi,j = Pj,i, Pi,..

https://www.acmicpc.net/problem/1781 1781번: 컵라면 상욱 조교는 동호에게 N개의 문제를 주고서, 각각의 문제를 풀었을 때 컵라면을 몇 개 줄 것인지 제시 하였다. 하지만 동호의 찌를듯한 자신감에 소심한 상욱 조교는 각각의 문제에 대해 데드라 www.acmicpc.net 문제 상욱 조교는 동호에게 N개의 문제를 주고서, 각각의 문제를 풀었을 때 컵라면을 몇 개 줄 것인지 제시 하였다. 하지만 동호의 찌를듯한 자신감에 소심한 상욱 조교는 각각의 문제에 대해 데드라인을 정하였다. 문제 번호데드라인컵라면 수 1 2 3 4 5 6 7 1 1 3 3 2 2 6 6 7 2 1 4 5 1 위와 같은 상황에서 동호가 2, 6, 3, 1, 7, 5, 4 순으로 숙제를 한다면 2, 6, 3..

문제 백준이는 동생에게 "가운데를 말해요" 게임을 가르쳐주고 있다. 백준이가 정수를 하나씩 외칠때마다 동생은 지금까지 백준이가 말한 수 중에서 중간값을 말해야 한다. 만약, 그동안 백준이가 외친 수의 개수가 짝수개라면 중간에 있는 두 수 중에서 작은 수를 말해야 한다. 예를 들어 백준이가 동생에게 1, 5, 2, 10, -99, 7, 5를 순서대로 외쳤다고 하면, 동생은 1, 1, 2, 2, 2, 2, 5를 차례대로 말해야 한다. 백준이가 외치는 수가 주어졌을 때, 동생이 말해야 하는 수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에는 백준이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 백준이가 외치는 정수가 차례대로..

문제 N×N의 표에 수 N2개 채워져 있다. 채워진 수에는 한 가지 특징이 있는데, 모든 수는 자신의 한 칸 위에 있는 수보다 크다는 것이다. N=5일 때의 예를 보자. 12 7 9 15 5 13 8 11 19 6 21 10 26 31 16 48 14 28 35 25 52 20 32 41 49 이러한 표가 주어졌을 때, N번째 큰 수를 찾는 프로그램을 작성하시오. 표에 채워진 수는 모두 다르다. 입력 첫째 줄에 N(1 ≤ N ≤ 1,500)이 주어진다. 다음 N개의 줄에는 각 줄마다 N개의 수가 주어진다. 표에 적힌 수는 -10억보다 크거나 같고, 10억보다 작거나 같은 정수이다. 출력 첫째 줄에 N번째 큰 수를 출력한다. 풀이 풀이 1 최소 힙을 만들고, N^2개의 숫자를 도는 동안 힙의 원소를 N개가..

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

여태까지 배우는 대로 대충 추가하곤 했었는데, 분류되지 않은 글이 너무 많아서 수정하였다. 기존에 알고리즘, 자료구조로 나눠져있던 대분류를 PS 하나로 통일하였다. 거의 모든 분류는 바킹독 선생님의 강의 주제를 기준으로 나누었다. 문자열 처리도 하나의 큰 분류인 듯한데, 없는 듯하여 추가하였다.

처음으로 온라인 대회에 참여해 보았다(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) 시간복잡도 정렬 알고리즘 일반적으로 구현하기 쉽다. 실제로 쓰이지 않으며, '선택 정렬과 버블 정렬의 차이점을 설명하여라'와 같은 지엽적인 질..