AquaplaneMode

문제 출처 : https://www.acmicpc.net/problem/3015 3015번: 오아시스 재결합 첫째 줄에 줄에서 기다리고 있는 사람의 수 N이 주어진다. (1 ≤ N ≤ 500,000) 둘째 줄부터 N개의 줄에는 각 사람의 키가 나노미터 단위로 주어진다. 모든 사람의 키는 231 나노미터 보다 작다. 사람 www.acmicpc.net 1. 문제 풀이 해당 문제는 스택 구조를 통하여 풀 수 있는 문제이다. 만약 두 사람 A, B가 순서대로 서있다고 가정해보자. A가 B보다 큰 경우, B 뒤에 B보다 키가 크거나 같은 사람이 올 때 A는 그 사람을 볼 수 있다. A가 B와 같은 경우, B 뒤에 B보다 키가 크더나 같은 사람이 올 때 A는 그 사람을 볼 수 있다. A가 B보다 작은 경우, B 뒤..

문제 출처 : https://www.acmicpc.net/problem/1014 1014번: 컨닝 최백준은 서강대학교에서 “컨닝의 기술”이라는 과목을 가르치고 있다. 이 과목은 상당히 까다롭기로 정평이 나있기 때문에, 몇몇 학생들은 시험을 보는 도중에 다른 사람의 답지를 베끼려 한 www.acmicpc.net 1. 문제 풀이 본 문제는 컨닝2 문제와 동일하다. 그러나, 컨닝에는 알고리즘 분류에 "비트마스킹"이 있었기 때문에, 비트마스킹으로 풀어보았다. 만약 "...X..X"와 같이 입력이 주어졌다고 가정하자. 각각의 "."와 "X"를 하나의 비트라고 가정했을 때, 총 7개의 bit가 존재하기 때문에 가능한 경우의 수는 128가지며, 비트연산자를 활용하여 부분집합을 구하는 방식으로 쉽게 모든 경우의 수를 ..

문제 출처 : https://www.acmicpc.net/problem/17349 17349번: 1루수가 누구야 (1 2)가 거짓말이라면, 선수 2가 1루수라는 주장과 1루수가 아니라는 주장이 동시에 존재하여 모순이다. (0 4)가 거짓말인 경우도, 마찬가지의 이유로 모순이다. (0 2)가 거짓말인 경우, 선수 2를 유 www.acmicpc.net 알고리즘 분류는 "많은 조건 분기"에 해당한다. 가능한 모든 경우의 수를 고려해서 처리해줘야 했기 때문에 상당히 귀찮은 문제였다. 1. 문제 풀이 일단, 2차원 배열을 통해 입력을 저장해줬다. 2차원 배열 board가 있을 때, 각 cell에 저장된 값은 다음과 같다. - board[i][0]은 i번 선수가 1루수가 아니라는 증언의 수 - board[i][1]..

문제 출처 : https://www.acmicpc.net/problem/5670 5670번: 휴대폰 자판 휴대폰에서 길이가 P인 영단어를 입력하려면 버튼을 P번 눌러야 한다. 그러나 시스템프로그래밍 연구실에 근무하는 승혁연구원은 사전을 사용해 이 입력을 더 빨리 할 수 있는 자판 모듈을 개발 www.acmicpc.net 1. 트라이 자료구조 본 문제는 문자열을 트리 형태로 저장하는 트라이(Trie)라는 자료구조를 통해 푸는 문제이다. 가령, 문제의 예시 입력처럼 'hello', 'hell', 'heaven', 'goodbye' 이라는 문자열이 들어온다면, 다음과 같은 모양을 가진다. 편의 상, 단어의 맨 마지막 노드는 얇은 윤곽선으로 표시하였다. 맨 왼쪽 부분을 보면, "hello"와 "hell"은 둘 ..

문제 출처 : https://www.acmicpc.net/problem/13907 1. 문제 풀이 본 문제에 따르면, 세금 인상 횟수는 최대 3만 번까지 발생할 수 있다. 따라서 매 번 세금이 인상될 때마다 다익스트라 알고리즘을 사용한다면 직관적으로 시간초과가 날 것을 유추할 수 있다. 만약 A 지점에서 B 지점으로 바로 갈 수 있다고 가정하자. 그렇다면 세금이 인상된다면, 세금을 한 번만 인상하면 된다. 만약 A 지점에서 B 지점으로 한 번 경유해서 갈 수 있다고 가정하자. 그렇다면 길은 총 두 번 지나기에, 총 통행료를 세금 * 2만큼 인상하면 된다. 즉, 시작 지점에서 도착 지점까지 몇 개의 길을 지나서 도착했는지를 구하면 문제를 풀 수 있다. 이를 위해 다익스트라 알고리즘을 약간 변형해서 문제를 ..

문제 출처 : https://www.acmicpc.net/problem/1533 1533번: 길의 개수 첫째 줄에 교차점의 개수 N이 주어진다. N은 10보다 작거나 같고, 시작점의 위치 S와 끝점의 위치 E, 그리고 정문이가 늦는 시간 T도 주어진다. S와 E는 N보다 작거나 같은 자연수이다. T는 1,000,000,000 www.acmicpc.net 1. 문제 풀이 1.1. 인접행렬의 특징 본 문제는 인접행렬을 통해 구현하는 문제이다. 가령 다음과 같은 행렬이 있다고 가정해보자. matrix[i][j] 는 i번 노드에서 j번 노드로 갈 수 있는 경우의 수를 표현한 것이다. 만약 i번 노드에서 j번 노드로 한 개의 노드를 경유해서 가고 싶다고 가정해보자.i = 0, j = 1이라고 가정하겠다. 그럼 다..

문제 출처 : https://www.acmicpc.net/problem/15824 15824번: 너 봄에는 캡사이신이 맛있단다 한 줄에 모든 조합의 주헌고통지수 합을 1,000,000,007로 나눈 나머지를 출력한다. www.acmicpc.net 1. 첫 풀이 : (50점) 가령 입력 배열이 다음과 같이 주어졌다고 가정하자. 1 4 5 5 6 10 해당 배열을 오름차순으로 정렬한 다음, 두 수 a, b를 뽑는다. 만약 a = 1, b = 6이라고 가정해보자. a, b는 각각 최소값, 최대값이기 때문에, 두 수 사이에 있는 음식은 먹더라도 먹지 않더라도 주헌고통지수는 변하지 않는다. - 캡사이신 수치가 4인 음식은 먹을수도 있고, 먹지 않을 수도 있다. (경우의 수 2) - 캡사이신 수치가 5인 음식은 먹..

문제 출처 : [2357.최솟값과 최댓값](https://www.acmicpc.net/problem/2357) 1. 문제 설명 정수가 차례대로 주어지고, 이후 범위가 차례대로 주어진다. 범위가 주어졌을 때, 해당 범위 내의 값 중 최솟값과 최댓값을 순서대로 출력하는 문제이다. 해당 문제는 세그먼트 트리 (Segment Tree) 자료형을 활용하는 문제이다. 세그먼트 트리는 바이너리 트리의 구조로 데이터를 저장하는 방식으로, 특정 범위 내의 통계값(최소, 최대, 합) 등을 파악하는 데 용이하다. 2. 코드 import sys input = sys.stdin.readline # 입력값 받기 num_nums, num_opers = map(int, input().split()) nums = [int(input(..

문제 : 2239. 스도쿠 코드 1 (실패) import sys input = sys.stdin.readline def cal_sqr(row_idx, col_idx): # row_idx와 col_idx를 받아, 해당 cell이 몇 번째 square에 속하는지 반환 new_row = row_idx // 3 new_col = col_idx // 3 return new_row * 3 + new_col mat = [list(map(int, list(input().rstrip()))) for _ in range(9)] zero_locs = [] # 0의 위치 num_nums = [0] * 10 # 각 숫자의 개수 refer_table = { 'row' : [0] * 9, # i번째 row의 합 'col' : [0..

문제 출처 : 7579.앱 문제 설명 각 앱은 사용중일 때의 메모리(m)과, 비활성화 했을 경우의 비용(c)에 대한 정보를 가지고 있다. 필요한 추가 메모리(M)가 주어졌을 때, 해당 메모리를 확보할 수 있는 최소 비활성화 비용을 구하는 문제이다. 문제 풀이 해당 문제는 동적 계획법(Dynamic Programming), 그 중에서도 냅색(Knapsack) 문제이다. 우선 dp 행렬을 하나 선언한다. 가로 길이는 모든 앱을 비활성화 했을 때의 비용+1, 세로 길이는 앱의 개수+1 만큼 설정한다. dp[i][j]는 i번째 까지의 앱을 활성화 하거나 비활성화하여 j 만큼의 비용이 들었을 때, 확보할 수 있는 최대한의 추가 메모리를 의미한다. 점화식에 따라 dp 배열을 갱신해준다. if col_idx < ap..