leah

Input

첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다.

둘째 줄부터 N개의 줄에는 숫자가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다.

1
2
3
4

import sys
input = sys.stdin.readline

n = int(input())

Sort

기존의 sort 나 sorted 를 사용하면 메모리 초과가 난다.

새로운 방식으로 접근해야 함.

1
2
3
4

s = [0]*10001

for _ in range(n):
  s[int(input())] += 1

같은 요소가 여러개 있는 경우, 중복으로 저장하는 것이 아닌, 2차원 배열 형식을 이용하여 중복되는 만큼 count를 한 후 count 만큼 해당 index를 출력하면 된다. 메모리 낭비를 없앨 수 있음.

1
2
3
4

for i in range(1, len(s)):
  if s[i] > 0:
    for _ in range(s[i]):
      print(i)

Input

표준 입력으로 다음 정보가 주어진다.

첫 번째 줄에는 도시의 개수를 나타내는 정수 N(2 ≤ N ≤ 100,000)이 주어진다.

다음 줄에는 인접한 두 도시를 연결하는 도로의 길이가 제일 왼쪽 도로부터 N-1개의 자연수로 주어진다.

다음 줄에는 주유소의 리터당 가격이 제일 왼쪽 도시부터 순서대로 N개의 자연수로 주어진다.

제일 왼쪽 도시부터 제일 오른쪽 도시까지의 거리는 1이상 1,000,000,000 이하의 자연수이다. 리터당 가격은 1 이상 1,000,000,000 이하의 자연수이다.

1
2
3
4
5
6

import sys
input = sys.stdin.readline

n = int(input().rstrip())
km = list(map(int, input().split()))
p = list(map(int, input().split()))

Greedy

그리디는 일단 현재 상황에서 할 수 있는 최선의 선택을 하고보는 타입이다. 이 문제가 대표적인 예시 같은데,

• 현재 위치 기준 바로 다음 주유소의 가격이 싸면 일단 간다.

  1 2 3

  if p[now] > p[now+1]: ret += p[now] * km[now] now += 1

• 비싸면 지금보다는 싼 주유소를 찾을 때까지 계속 찾고, 싼 곳을 찾으면 거기로 이동한다.

  1 2 3 4 5 6 7 8 9

  else: dist = 0 next = 0 for next in range(now + 1, n): dist += km[next-1] if p[now] > p[next]: break ret += dist * p[now] now = next

• 이 모든 건 도착지 전까지만 해당, 도착지에 도달할 경우 종료해야 한다.

  1	while now < n-1:

  완전 탐색처럼 가장 싼 곳을 찾아서 움직이면 안 된다. 중간중간에 절약할 수 있는 경우에는 일단 절약하고 봐야 함.

lambda

JavaScript의 arrow function과 비슷하다. 함수를 재사용하지 않고 익명함수로 선언할 때 유용하게 사용해서, callback 함수로 적절

Basic Syntax

1

lambda args: exp

map

iterables 에 사용 가능하며, 모든 요소에 함수를 적용하여 결과값을 반환한다. 새로운 리스트에 해당 요소들을 받고 싶으면 list() 를 사용하면 됨. 여러 iterables를 전달할 수 있다.

Basic Syntax

1

map(function, iterable[, ...iterables])

filter

마찬가지로 iterables에 사용 가능. 함수의 결과값이 True 인 요소만 반환한다. 하나의 iterable만 전달 가능함.

Basic Syntax

1

filter(function, iterable)

Reduce

사실 이 함수 때문에 글을 작성하게 됐는데, functools 라이브러리를 사용한 reduce는 반복문 대신 사용하기 유용한 듯.

• (acc, val) 이기 때문에, lambda 작성 시 arguments로 (acc, val) 을 전달

Basic Syntax

1

reduce(function, iterable)

Example

1
2
3
4
5
6

from functools import reduce
li = [1, 2, 3, 4, 5]
sum = reduce((lambda x, y: x + y), li) # output: 15
# (1)+2
# ((1)+2)+3
# ...

Input

첫째 줄에 정수 N이 주어진다.

다음 N개의 줄에는 각 로프가 버틸 수 있는 최대 중량이 주어진다. 이 값은 10,000을 넘지 않는 자연수이다.

1
2
3
4
5

import sys
input = sys.stdin.readline

n = int(input())
s = [int(input().rstrip()) for _ in range(n)]

Greedy

처음에는 문제 이해를 잘못 했었음. 여러 물체를 들 수 있는 줄 알았지.. 근데 생각해보면 이건 그냥 sum을 구하는 문제다 ㅋㅋ 암튼

• 물체는 최대 중량으로 한 개 들어야 함
• 여러 로프로 나누어 들어도 되고, 모든 로프를 쓸 필요는 없음

일단 sorted 부터 써야 한다. 가장 작은 중량치를 가진 로프를 기준으로 할 건지, 큰 중량치를 기준으로 할 건지부터 정해야 하기 때문.

1
2

s = sorted(s)
ret = s[-1]

• 작은 중량치가 기준일 경우: n배
• 큰 중량치가 기준일 경우: 해당 중량 = 최대

1
2

for i in range(n-1):
  ret = max(s[i] * (n - i), ret)

이걸 처음엔 중첩 for문으로 작성했었다. 근데 생각해보면 쓸데없는 계산이 들어갔었음. 위와 같이 줄일 수 있다.

Input

첫째 줄에 N, K의 원소의 개수가 공백을 기준으로 구분되어 자연수로 주어진다. (10 ≤ N ≤ 100,000,000, 1 ≤ K의 원소의 개수 ≤ 3)

둘째 줄에 K의 원소들이 공백을 기준으로 구분되어 주어진다. 각 원소는 1부터 9까지의 자연수다.

단, 항상 K의 원소로만 구성된 N보다 작거나 같은 자연수를 만들 수 있는 경우만 입력으로 주어진다.

1
2
3
4
5

import sys
input = sys.stdin.readline

n, k = map(int, input().split())
s = list(map(int, input().split()))

Brute Force

• 주어진 범위 내의 수를 하나씩 체크

• 가장 큰 수를 찾으면 출력하고 프로그램 종료

• N보다 작거나 같은

  1 2	for i in range(n, 0, -1): ret = i

• 주어진 숫자의 모든 자리수가 주어진 k 에 존재해야 함

  1 2 3 4

  while ret > 0: if ret % 10 in s: ret //= 10 else: break

• 조건을 만족시킬 경우 외에는 ret 가 0이 될 수 없음

  1 2 3

  if ret == 0: print(i) exit(0)

Input

첫째 줄에 n이,

둘째 줄에 k가 주어진다.

셋째 줄부터 n개 줄에는 카드에 적혀있는 수가 주어진다.

1
2
3
4
5
6

import sys
input = sys.stdin.readline

n = int(input().rstrip())
k = int(input().rstrip())
s = [input().strip() for _ in range(n)]

Brute Force

• 순회하는 순서에 따라 조합이 달라짐 = 순열

  python library itertools.permutations

  • input: iterable[, choice]
  • output: possible combinations (iterable)

  1 2 3

  # 순열 # nPk from itertools import permutations

• 결과가 같은 경우는 제외 = set

  1	ret = set()

  1 2 3

  # k-length possible combinations (tuples) for per in permutations(s, k): ret.add(''.join(per))

Output

첫째 줄에 상근이가 만들 수 있는 정수의 개수를 출력한다.

1

print(len(ret))

Input

입력은 표준입력을 사용한다. 입력은 자연수 n을 포함하는 한 줄로 구성된다. 여기서, 1 ≤ n ≤ 50,000이다.

1
2
3
4

import sys
input = sys.stdin.readline

n = int(input().strip())

DP

• 최적의 조합을 찾아서 기존의 값을 계속 업데이트 해야 한다는 점
• min 값을 찾아야 한다는 점

이 DP의 조건이었다. 배열을 사용해서 풀어야 하고, 어떻게 접근해야 할지도 감은 잡았는데, brute force로 풀어보려니 안 풀렸었다. 문제 유형을 올바르게 파악할 것..

1

dp = [i for i in range(n+1)]

채워야 하는 n 까지 배열을 초기화시키고, i 가 제곱근일 경우 1이 되므로 알맞게 다시 초기화

1
2
3

for i in range(2, n+1):
  if i == int(math.sqrt(i)) ** 2:
    dp[i] = 1

• 다시 2부터 n까지 돌면서 이번엔 값을 알맞게 넣어야 함.

  1	for i in range(2, n+1):

• 현재 체크하고 있는 i 를 기준으로 더 작은 값 j 를 제곱하여 뺐을 때, 기존의 값*(1로만 더한 개수)* 와 다른 제곱근을 활용한 개수를 비교해서 min 값을 넣는다.

  1 2	for j in range(1, int(math.sqrt(i)) + 1): dp[i] = min(dp[i], dp[j ** 2] + dp[i - j ** 2])

Output

출력은 표준출력을 사용한다. 합이 n과 같게 되는 제곱수들의 최소 개수를 한 줄에 출력한다.

1

print(dp[n])

Input

첫째 줄에 정수 N과 M이 주어진다. N은 아이스크림 종류의 수이고, M은 섞어먹으면 안 되는 조합의 개수이다.

아래 M개의 줄에는 섞어먹으면 안 되는 조합의 번호가 주어진다. 같은 조합은 두 번 이상 나오지 않는다. (1 ≤ N ≤ 200, 0 ≤ M ≤ 10,000)

1
2
3
4
5
6
7
8
9
10

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
s = [[0]*(n+1) for _ in range(n+1)]

for i in range(m):
  j, k = map(int, input().split())
  s[j][k] = -1
  s[k][j] = -1

Brute Force

먼저 접근한 방식은 매 케이스마다 해당 조합을 제외한 n개의 요소 중 가능한 조합을 찾아서 더하는 방식이었는데, 주어진 케이스로부터도 알 수 있듯이 불필요하게 반복을 하는 경우도 존재하게 된다.

따라서 2차원 배열을 생성해 각 숫자와 불가능한 조합을 저장해두고, 어차피 순열이 아닌 조합이므로 중첩 반복문의 index가 순차적으로 증가하도록 설정한다.

1
2
3

for a in range(1, n+1):
  for b in range(a+1, n+1):
    for c in range(b+1, n+1):

그리고 불가능한 조합이 아니면 count를 증가시키면 됨

1
2
3
4
5

...
    if s[a][b] == -1: continue
    ...
      if s[a][c] == -1 or s[b][c] == -1: continue
      ret += 1

Output

첫째 줄에, 가능한 방법이 총 몇 개 있는지 출력한다.

1

print(ret)

Input

첫째 줄에는 민혁이가 영수에게 몇 번이나 질문을 했는지를 나타내는 1 이상 100 이하의 자연수 N이 주어진다.

이어지는 N개의 줄에는 각 줄마다 민혁이가 질문한 세 자리 수와 영수가 답한 스트라이크 개수를 나타내는 정수와 볼의 개수를 나타내는 정수, 이렇게 총 세 개의 정수가 빈칸을 사이에 두고 주어진다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

import sys
input = sys.stdin.readline

num = [] # string
s = []
b = []

t = int(input().strip())
ret = [False]*1000

for _ in range(t):
  temp_num, temp_s, temp_b = map(int, input().split())
  num.append(str(temp_num))
  s.append(temp_s)
  b.append(temp_b)

Brute Force

완전 탐색을 어떻게 접근해야 하는지 감을 잡았다. 중첩 반복문의 끝이라 런타임 에러든 뭐든 틀릴 줄 알았는데 맞아서 쩌매 당황;;

이 문제는 1~9 중 서로 다른 digit number을 가진 3자리 자연수 중 strike , ball 을 만족시키는 경우를 고르면 된다.

• 일단 가능한 경우의 숫자를 모두 만들어놓고

  1 2 3 4 5

  for i in range(1, 10): for j in range(1, 10): for k in range(1, 10): if i != j and j != k and i != k: ret[i*100 + j*10 + k] = True

• 여기서 조건에 맞는 경우는 남기고 아닌 경우는 제외시키면 됨

  1 2	if strike != s[idx] or ball != b[idx]: ret[t] = False

  • strike: 숫자도 위치도 같은 경우

    1 2	if temp[d] == now[d]: strike += 1

  • ball: 숫자는 같되 위치가 다른 경우

    1 2	elif now.count(temp[d]) > 0: ball += 1

Output

첫 줄에 영수가 생각하고 있을 가능성이 있는 답의 총 개수를 출력한다.

• True False 를 이용했기 때문에 sum 을 이용하면 바로 len 을 출력할 수 있음

  1	print(sum(ret))

Input

첫 줄에 DNA의 수 N과 문자열의 길이 M이 주어진다.

그리고 둘째 줄부터 N+1번째 줄까지 N개의 DNA가 주어진다. N은 1,000보다 작거나 같은 자연수이고, M은 50보다 작거나 같은 자연수이다.

1
2
3
4
5

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
s = [input().upper() for _ in range(n)]

Brute Force

hamming distance가 작다 = string.charAt(index)가 가장 빈번한 글자를 택하면 됨

원래는 dict 를 활용해서 풀었는데 주어진 케이스는 모두 맞았지만 틀렸다고 해서 배열에 ord 를 사용하는 코드로 바꿨더니 맞았다. 뭐가 다른 거지, 히든 케이스가 뭐였을까

기존 코드

1
2
3
4
5
6

count = [{'A': 0, 'T': 0, 'G': 0, 'C': 0} for _ in range(m)]

		count[j][now] += 1

for i in range(m):
  ret += max(count[i].items(), key=operator.itemgetter(1))[0]

변경 코드

1
2
3
4
5
6

count = [[0]*26 for _ in range(m)]

    count[j][ord(now)-65] += 1

for i in range(m):
  ret += chr(count[i].index(max(count[i])) + 65)

Output

첫째 줄에 Hamming Distance의 합이 가장 작은 DNA 를 출력하고,

둘째 줄에는 그 Hamming Distance의 합을 출력하시오. 그러한 DNA가 여러 개 있을 때에는 사전순으로 가장 앞서는 것을 출력한다.

1
2
3
4
5
6
7
8
9

for i in range(n):
  word = s[i]

  for j in range(m):
    if word[j] != ret[j]:
      ans += 1

print(ret)
print(ans)