https://www.acmicpc.net/problem/21314 21314번: 민겸 수 민겸 수 하나가 주어진다. 민겸 수는 대문자 M과 K로만 이루어진 문자열이며, 길이는 3,000을 넘지 않는다. www.acmicpc.net 규칙을 발견하면 바로 구현할 수 있는 문제이다 최솟값의 경우 M이 등장할때 M과 K를 최대한 적게 묶는다 K는 각각 하나씩 분해해서 묶고, M은 M끼리 묶는다 M/K/K/MM/K = 155105 최댓값의 경우 K가 등장할때 최대한 많은 M이랑 묶어주어야 한다. 그런데 K는 M보다 뒤에 오니까, 문자열을 선형탐색할 때 마지막 인텍스부터 첫번째 인덱스를 탐색해주어야 한다. MK/K/MMK = 505500 전체 코드는 다음과 같다 data = input() min_value = '..
Algorithm (PS)
시간제한이 0.5 인 문제 - 그래서 삽질을 좀 해야 했다.. https://www.acmicpc.net/problem/21318 21318번: 피아노 체조 피아노를 사랑하는 시은이는 매일 아침 피아노 체조를 한다. 시은이는 N개의 악보를 가지고 있으며, 1번부터 N번까지의 번호로 부른다. 각 악보는 1 이상 109 이하의 정수로 표현되는 난이도를 www.acmicpc.net x 부터 y까지 입력값을 받을 때마다 선형탐색으로 실수를 찾아내게 되면 시간초과가 뜰 것 같아서 DP 누적합으로 풀었다. 누적합 힌트를 보고 풀었고 풀이도 맞는데 시간초과가 나서 세세한 부분을 신경써주어야 하는 문제였다. 그런데 처음에는 dp를 n+1 길이로 해서 인덱스 값 헷갈리지 않게 하려고 했으나.. n+1 으로 하니 또 시간..
https://www.acmicpc.net/problem/21610 21610번: 마법사 상어와 비바라기 마법사 상어는 파이어볼, 토네이도, 파이어스톰, 물복사버그 마법을 할 수 있다. 오늘 새로 배운 마법은 비바라기이다. 비바라기를 시전하면 하늘에 비구름을 만들 수 있다. 오늘은 비바라기 www.acmicpc.net 삼성 style의 빡구현 문제 1. 시간초과 난 풀이 문제점 : [i,j] 좌표가 new_clouds 배열에 속해있는지 확인하는 in 연산이 시간을 많이 잡어먹는다.. -> 이를 해결하기 위해서 visited 2차원 배열을 만들어서 방문 여부를 표시한다. # 21610 마법사 상어와 비바라기 n, m = map(int, input().split()) # delta 방향 dx = [0, -1..
https://www.acmicpc.net/problem/2961 2961번: 도영이가 만든 맛있는 음식 첫째 줄에 재료의 개수 N(1 ≤ N ≤ 10)이 주어진다. 다음 N개 줄에는 그 재료의 신맛과 쓴맛이 공백으로 구분되어 주어진다. 모든 재료를 사용해서 요리를 만들었을 때, 그 요리의 신맛과 쓴맛은 www.acmicpc.net 브루트포스로 풀었다 재료를 1개 선택하는 경우부터 2개, 3개, ... n개까지 선택하는 경우 각각의 조합 경우의 수를 따져봤다. 그리고 신맛과 쓴맛의 차이의 최솟값이 나올 때마다 갱신했다. from itertools import combinations data = [] n = int(input()) for _ in range(n): s, b = map(int, input()..
데이터모델 : 현실 세계의 정보들을 컴퓨터에 표현하기 위해서 단순화, 추상화하여 체계적으로 표현한 개념적 모형 구조 : 논리적으로 표현된 개체 타입들 간의 관계로서 데이터 구조 및 정적 성질 표현 연산 : 데이터베이스에 저장된 실제 데이터를 처리하는 작업에 대한 명세로 데이터베이스를 조작하는 기본 도구 제약 조건 : 데이터베이스에 저장될 수 있는 실제 데이터의 논리적인 제약 조건 데이터모델의 구성요소 3가지 : 개체 , 속성, 관계 개체 : 데이터베이스에 표현하려고 하는 것. 현실 세계의 대상체 속성 : 데이터베이스를 구성하는 가장 작은 논리적 단위 도메인 : 하나의 attribute가 취할 수 있는 같은 타입의 원자 값들의 집합 무결성 : 데이터베이스에 저장된 값과 그것이 표현하는 현실세계의 실제값이 ..
https://www.acmicpc.net/problem/2531 2531번: 회전 초밥 첫 번째 줄에는 회전 초밥 벨트에 놓인 접시의 수 N, 초밥의 가짓수 d, 연속해서 먹는 접시의 수 k, 쿠폰 번호 c가 각각 하나의 빈 칸을 사이에 두고 주어진다. 단, 2 ≤ N ≤ 30,000, 2 ≤ d ≤ 3,000, 2 ≤ www.acmicpc.net 아 스시 먹고 싶다.. 🍣 배열을 두개 이어붙이는 식으로 원판을 회전하는 경우를 확인했다. n, d, k, c = map(int, input().split()) array = [] # 초밥 for _ in range(n): a = int(input()) array.append(a) # array 를 2배로 늘리기 array.extend(array) max_c..
https://www.acmicpc.net/problem/6603 6603번: 로또 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있다. 첫 번째 수는 k (6 < k < 13)이고, 다음 k개 수는 집합 S에 포함되는 수이다. S의 원소는 오름차순으로 www.acmicpc.net 쉬어가는 경우의 수 문제~ 조합 모듈 combinations를 이용하면 간단하게 풀 수 있다. from itertools import combinations while True: data = list(map(int, input().split())) if len(data) == 1: break array = list(combinations(data[1:], 6)) array.sort() ..
https://www.acmicpc.net/problem/11055 11055번: 가장 큰 증가 부분 수열 수열 A가 주어졌을 때, 그 수열의 증가 부분 수열 중에서 합이 가장 큰 것을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 인 경우에 합이 가장 큰 증가 부분 수 www.acmicpc.net # https://www.acmicpc.net/problem/11055 n = int(input()) array = list(map(int, input().split())) dp = [i for i in array] # 초기값을 원소값으로 초기화 한다 for i in range(n): for j in range(i): if array[i]..
