세준이는 길 한가운데에서 전광판을 쳐다보고 있었다. 전광판에는 광고가 흘러나오고 있었다. 한참을 전광판을 쳐다본 세준이는 이 광고가 의미하는 것이 무엇인지 궁금해지기 시작했다.

전광판에는 같은 내용의 문구가 무한히 반복되어 나온다. 또, 전광판의 크기는 전광판에서 한번에 보이는 최대 문자수를 나타낸다. 만약 전광판의 크기가 L이라면, 한번에 L개의 문자를 표시할 수 있는 것이다.

광고업자는 최대한의 광고효과를 내기 위해서 길이가 N인 광고를 무한히 붙여서 광고한다.

예를 들어, 광고 업자 백은진이 광고하고 싶은 내용이 aaba 이고, 전광판의 크기가 6이라면 맨 처음에 보이는 내용은 aabaaa 이다. 시간이 1초가 지날 때마다, 문자는 한 칸씩 옆으로 이동한다. 따라서 처음에 aabaaa가 보였으면 그 다음에는 abaaab가 보인다. 그 다음에는 baaaba가 보인다.

세준이가 어느 순간 전광판을 쳐다봤을 때, 그 때 쓰여 있는 문자가 입력으로 주어졌을 때, 가능한 광고의 길이중 가장 짧은 것을 출력하는 프로그램을 작성하시오.

출처 : https://www.acmicpc.net/problem/1305

2. 아이디어

• clone*

  1. KMP 알고리즘에서 겹치는 접두사 접미사 길이를 구하고 전체 길이에서 제외해준다. 출처 : https://dirmathfl.tistory.com/316

3. 코드

clone

def make_table(patten):
    table = [0] * l
    j = 0
    for i in range(1, l):
        while j > 0 and patten[i] != patten[j]:
            j = table[j - 1]
        if patten[i] == patten[j]:
            j += 1
            table[i] = j
    return l - table[l - 1]
>
if __name__ == "__main__":
    l = int(input())
    s = input()
    print(make_table(s))

워드프로세서 등을 사용하는 도중에 찾기 기능을 이용해 본 일이 있을 것이다. 이 기능을 여러분이 실제로 구현해 보도록 하자.

두 개의 문자열 P와 T에 대해, 문자열 P가 문자열 T 중간에 몇 번, 어느 위치에서 나타나는지 알아내는 문제를 '문자열 매칭'이라고 한다. 워드프로세서의 찾기 기능은 이 문자열 매칭 문제를 풀어주는 기능이라고 할 수 있다. 이때의 P는 패턴이라고 부르고 T는 텍스트라고 부른다.

편의상 T의 길이를 n, P의 길이를 m이라고 하자. 일반적으로, n ≥ m이라고 가정해도 무리가 없다. n<m이면 어차피 P는 T중간에 나타날 수 없기 때문이다. 또, T의 i번째 문자를 T[i]라고 표현하도록 하자. 그러면 물론, P의 i번째 문자는 P[i]라고 표현된다.

  1 2 3 4 5 6 7 8 9 …

T : [ A B C D A B C D A B D E ] | | | | | | X P : [ A B C D A B D ] 1 2 3 4 5 6 7 문자열 P가 문자열 T 중간에 나타난다는 것, 즉 문자열 P가 문자열 T와 매칭을 이룬다는 것이 어떤 것인지 위와 아래의 두 예를 통해 알아보자. 위의 예에서 P는, T의 1번 문자에서 시작하는 매칭에 실패했다. T의 7번 문자 T[7]과, P의 7번 문자 P[7]이 서로 다르기 때문이다.

그러나 아래의 예에서 P는, T의 5번 문자에서 시작하는 매칭에 성공했다. T의 5～11번 문자와 P의 1～7번 문자가 서로 하나씩 대응되기 때문이다.

  1 2 3 4 5 6 7 8 9 …

T : [ A B C D A B C D A B D E ] | | | | | | | P : [ A B C D A B D ] 1 2 3 4 5 6 7 가장 단순한 방법으로, 존재하는 모든 매칭을 확인한다면, 시간복잡도가 어떻게 될까? T의 1번 문자에서 시작하는 매칭이 가능한지 알아보기 위해서, T의 1～m번 문자와 P의 1～m번 문자를 비교한다면 최대 m번의 연산이 필요하다. 이 비교들이 끝난 후, T의 2번 문자에서 시작하는 매칭이 가능한지 알아보기 위해서, T의 2～m+1번 문자와 P의 1～m번 문자를 비교한다면 다시 최대 m번의 연산이 수행된다. 매칭은 T의 n-m+1번 문자에서까지 시작할 수 있으므로, 이러한 방식으로 진행한다면 O( (n-m+1) × m ) = O(nm) 의 시간복잡도를 갖는 알고리즘이 된다.

더 좋은 방법은 없을까? 물론 있다. 위에 제시된 예에서, T[7] ≠ P[7] 이므로 T의 1번 문자에서 시작하는 매칭이 실패임을 알게 된 순간으로 돌아가자. 이때 우리는 매칭이 실패라는 사실에서, T[7] ≠ P[7] 라는 정보만을 얻은 것이 아니다. 오히려 i=1…6에 대해 T[i] = P[i] 라고 하는 귀중한 정보를 얻지 않았는가? 이 정보를 십분 활용하면, O(n)의 시간복잡도 내에 문자열 매칭 문제를 풀어내는 알고리즘을 설계할 수 있다.

P 내부에 존재하는 문자열의 반복에 주목하자. P에서 1, 2번 문자 A, B는 5, 6번 문자로 반복되어 나타난다. 또, T의 1번 문자에서 시작하는 매칭이 7번 문자에서야 실패했으므로 T의 5, 6번 문자도 A, B이다.

따라서 T의 1번 문자에서 시작하는 매칭이 실패한 이후, 그 다음으로 가능한 매칭은 T의 5번 문자에서 시작하는 매칭임을 알 수 있다! 더불어, T의 5～6번 문자는 P의 1～2번 문자와 비교하지 않아도, 서로 같다는 것을 이미 알고 있다! 그러므로 이제는 T의 7번 문자와 P의 3번 문자부터 비교해 나가면 된다.

이제 이 방법을 일반화 해 보자. T의 i번 문자에서 시작하는 매칭을 검사하던 중 T[i+j-1] ≠ P[j]임을 발견했다고 하자. 이렇게 P의 j번 문자에서 매칭이 실패한 경우, P[1…k] = P[j-k…j-1]을 만족하는 최대의 k(≠j-1)에 대해 T의 i+j-1번 문자와 P의 k+1번 문자부터 비교를 계속해 나가면 된다.

이 최대의 k를 j에 대한 함수라고 생각하고, 1～m까지의 각 j값에 대해 최대의 k를 미리 계산해 놓으면 편리할 것이다. 이를 전처리 과정이라고 부르며, O(m)에 완료할 수 있다.

이러한 원리를 이용하여, T와 P가 주어졌을 때, 문자열 매칭 문제를 해결하는 프로그램을 작성하시오.

출처 : https://www.acmicpc.net/problem/1786

2. 아이디어

• mine* (시간 초과‼)

  1. find함수를 사용하여 index를 받고 발견하면 그 이후 문자열 반복 재탐색

clone

1. KMP 알고리즘 활용 (https://www.youtube.com/watch?v=UcjK_k5PLHI)

3. 코드

mine (시간 초과‼)

t = input()
p = input()
>
result = []
index = -1
while True: # 있다면
  index = t.find(p, index + 1)
  if index == -1:
    break
  result.append(index + 1)
>
if result:
  print(len(result))
  for res in result:
    print(res)
else:
  print(0)

clone

def make_pi():
    pi = [0 for i in range(0, len(P))]
>
    j = 0
    for i in range(1, len(P)):
        while j > 0 and P[i] != P[j]:
            j = pi[j - 1]
>
        if (P[i] == P[j]):
            j += 1
            pi[i] = j
    return pi
>
def solution(pi):
    result = []
    count = 0
>
    j = 0
    for i in range(0, len(T)):
>
        while j > 0 and T[i] != P[j]:
            j = pi[j - 1]
>
        if T[i] == P[j]:
            if j == (len(P) - 1):
                result.append(i - len(P) + 2)
                count += 1
                j = pi[j]
            else:
                j += 1
>
    print(count)
    for element in result:
        print(element)
>
T = input()
P = input()
solution(make_pi())

출처 : https://donghak-dev.tistory.com/60

우리 나라는 가족 혹은 친척들 사이의 관계를 촌수라는 단위로 표현하는 독특한 문화를 가지고 있다. 이러한 촌수는 다음과 같은 방식으로 계산된다. 기본적으로 부모와 자식 사이를 1촌으로 정의하고 이로부터 사람들 간의 촌수를 계산한다. 예를 들면 나와 아버지, 아버지와 할아버지는 각각 1촌으로 나와 할아버지는 2촌이 되고, 아버지 형제들과 할아버지는 1촌, 나와 아버지 형제들과는 3촌이 된다.

여러 사람들에 대한 부모 자식들 간의 관계가 주어졌을 때, 주어진 두 사람의 촌수를 계산하는 프로그램을 작성하시오.

출처 : https://www.acmicpc.net/problem/2644

2. 아이디어

• mine* (틀렸습니다‼)

  1. BFS를 활용하여 큐에 인접 요소를 넣을 때 하나씩 카운트 해줬다. (카운팅 방법이 잘못됨.)

mine

1. BFS를 활용하여 큐에 인접 요소를 넣을 때 하나씩 카운트 해줬다. (다음 요소에 전 요소 +1)

clone

1. BFS를 활용하여 큐에 인접 요소를 넣을 때 하나씩 카운트 해줬다. (다음 요소에 전 요소 +1)
2. print를 함수에서 실행

3. 코드

mine (틀렸습니다‼)

import sys
from collections import deque
input = sys.stdin.readline
>
def bfs(graph, distance, start):
  # 큐(Queue) 구현을 위해 deque 라이브러리 사용
  queue = deque([start])
  # 현재 노드를 방문 처리
  distance[start] = 1
  count = 0
  # 큐가 빌 때까지 반복
  while queue:
    # 큐에서 하나의 원소를 뽑아 출력하기
    v = queue.popleft()
    # 아직 방문하지 않은 인접한 원소들을 큐에 삽입
    count += 1
    invalidity = True
    for i in graph[v]:
      if distance[i] == 0:
        invalidity = False
        queue.append(i)
        distance[i] = count
    if invalidity:
      count -= 1
>
n = int(input())
a, b = map(int, input().split())
m = int(input())
>
graph = [[] for _ in range(n+1)]
>
for _ in range(m):
    x, y=map(int, input().split())
    graph[x].append(y)
    graph[y].append(x)
>
for g in graph:
    g.sort()
>
distance = [0] * (n+1)
bfs(graph, distance, a)
distance[a] = 0
if a==b: # 본인은 0으로 간주
  print(0)
elif distance[b] == 0: # BFS로 인접요소에 카운팅되지 않았다면 -1 출력
  print(-1)
else: # a와 몇 촌인지 b의 거리 출력
  print(distance[b])

mine

import sys
from collections import deque
input = sys.stdin.readline
>
def bfs(graph, distance, start, visited):
  # 큐(Queue) 구현을 위해 deque 라이브러리 사용
  queue = deque([start])
  # 현재 노드를 방문 처리
  visited[start] = True
  # 큐가 빌 때까지 반복
  while queue:
    # 큐에서 하나의 원소를 뽑아 출력하기
    v = queue.popleft()
    # 아직 방문하지 않은 인접한 원소들을 큐에 삽입
    for i in graph[v]:
      if not visited[i]:
        queue.append(i)
        visited[i] = True
        distance[i] = distance[v] + 1
>
n = int(input())
a, b = map(int, input().split())
m = int(input())
>
graph = [[] for _ in range(n+1)]
>
for _ in range(m):
    x, y=map(int, input().split())
    graph[x].append(y)
    graph[y].append(x)
>
for g in graph:
    g.sort()
>
visited = [False] * (n+1)
distance = [0] * (n+1)
bfs(graph, distance, a, visited)
distance[a] = 0
if a==b:
  print(0)
elif distance[b] == 0:
  print(-1)
else:
  print(distance[b])

clone

N = int(input()) # 전체 사람의 수 
a,b =map(int,input().split()) # 촌수 계산해야하는 두 번호
M = int(input()) # 관계의 개수 
>
# [ [], [], [], [], [], [], [], [], [], [] ] 
#print(Matrix)
Matrix = [ [] for i in range(N+1)] 
>
# 결과를 출력할 리스트 
Res = [0]*(N+1)
for i in range(M):
  x,y  =map(int,input().split())
  # 양방향으로 값 넣음
  Matrix[x].append(y)
  Matrix[y].append(x)
>
#print(Matrix)
# [[], [2, 3], [1, 7, 8, 9], [1], [5, 6], [4], [4], [2], [2], [2]]
def BFS(start,end):
  queue = [start]
  visit = [] # 방문 리스트 
  while queue:
    V = queue.pop(0)
    visit.append(V) 
    if V==end: # 큐의 값이 End라면 while문 break
      break
   > 
    for i in Matrix[V]: # ex) Matrix[2] : 1, 7, 8, 9
      if  i not in visit: # i 값을 방문하지 않았다면 
        Res[i] = Res[V]+1 # 다음 거리 = 현재거리 + 1 
        queue.append(i)
    >    
  if Res[end]==0: # 0이면 거쳐온 단계가 없으므로 -1 
    print(-1)
  else: # 0 이 아니라면 start -> end 로 거쳐온 거리를 출력 
    print(Res[end])
>
BFS(a,b)

출처 : https://giraffecloud.tistory.com/18

신종 바이러스인 웜 바이러스는 네트워크를 통해 전파된다. 한 컴퓨터가 웜 바이러스에 걸리면 그 컴퓨터와 네트워크 상에서 연결되어 있는 모든 컴퓨터는 웜 바이러스에 걸리게 된다.

예를 들어 7대의 컴퓨터가 <그림 1>과 같이 네트워크 상에서 연결되어 있다고 하자. 1번 컴퓨터가 웜 바이러스에 걸리면 웜 바이러스는 2번과 5번 컴퓨터를 거쳐 3번과 6번 컴퓨터까지 전파되어 2, 3, 5, 6 네 대의 컴퓨터는 웜 바이러스에 걸리게 된다. 하지만 4번과 7번 컴퓨터는 1번 컴퓨터와 네트워크상에서 연결되어 있지 않기 때문에 영향을 받지 않는다.

어느 날 1번 컴퓨터가 웜 바이러스에 걸렸다. 컴퓨터의 수와 네트워크 상에서 서로 연결되어 있는 정보가 주어질 때, 1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수를 출력하는 프로그램을 작성하시오.

출처 : https://www.acmicpc.net/problem/2606

2. 아이디어

• mine*

  1. DFS로 방문 검사를 하여 1번 컴퓨터를 제외해야 되니까 방문한 수를 카운트 한 후 - 1을 했다.

clone

1. DFS로 방문할 때만 append하는 점, sort대신 dictionary와 set을 사용한 점이 다르다.

3. 코드

mine

import sys
input = sys.stdin.readline
>
def dfs(graph, v, visited):
  #현재 노드를 방문 처리
  visited[v] = True
  #현재 노드와 연결된 다른 노드를 재귀적으로 방문
  for i in graph[v]:
    if not visited[i]:
      dfs(graph, i, visited)
>
computer = int(input())
connected_pair = int(input())
>
graph = [[] for _ in range(computer+1)]
>
for _ in range(connected_pair):
    x,y=map(int, input().split())
    graph[x].append(y)
    graph[y].append(x)
>
for g in graph:
    g.sort()
>
visited = [False] * (computer+1)
dfs(graph, 1, visited)
print(visited.count(True)-1)

clone

from sys import stdin
read = stdin.readline
dic={}
for i in range(int(read())):
    dic[i+1] = set()
for j in range(int(read())):
    a, b = map(int,read().split())
    dic[a].add(b)
    dic[b].add(a)
>
def dfs(start, dic):
    for i in dic[start]:
        if i not in visited:
            visited.append(i)
            dfs(i, dic)
visited = []
dfs(1, dic)
print(len(visited)-1)

출처 : https://chancoding.tistory.com/60

4. 결과 비교

1. mine 2. clone

정수로 이루어진 크기가 같은 배열 A, B, C, D가 있다.

A[a], B[b], C[c], D[d]의 합이 0인 (a, b, c, d) 쌍의 개수를 구하는 프로그램을 작성하시오.

출처 : https://www.acmicpc.net/problem/7453

2. 아이디어

• clone*

  1. 4개를 동시에 계산하면 시간초과
  2. 딕셔너리를 활용하여 a,b를 계산하고 c,d를 계산한 다음 (a,b 계산결과) == -(c,d 계산 결과)가 성립하면 총 합은 0이다.

3. 코드

mine

import sys
input = sys.stdin.readline
>
n = int(input())
result = 0
a_b_dict = dict()
arr_a, arr_b, arr_c, arr_d = [], [], [], []
for _ in range(n):
    a, b, c, d = map(int,sys.stdin.readline().split())
    arr_a.append(a)
    arr_b.append(b)
    arr_c.append(c)
    arr_d.append(d)
>
for a in arr_a:
    for b in arr_b:
        a_b_dict[a+b] = a_b_dict.get(a+b, 0) + 1
>
for c in arr_c:
    for d in arr_d:
        result += a_b_dict.get(-(c+d), 0)
>
print(result)

출처 : https://jjangsungwon.tistory.com/112 https://jaeyoon-95.tistory.com/168

연종이는 엄청난 기억력을 가지고 있다. 그래서 하루 동안 본 정수들을 모두 기억 할 수 있다. 하지만 이를 믿을 수 없는 동규는 그의 기억력을 시험해 보기로 한다. 동규는 연종을 따라 다니며, 연종이 하루 동안 본 정수들을 모두 ‘수첩1’에 적어 놓았다. 그것을 바탕으로 그가 진짜 암기왕인지 알아보기 위해, 동규는 연종에게 M개의 질문을 던졌다. 질문의 내용은 “X라는 정수를 오늘 본 적이 있는가?” 이다. 연종은 막힘없이 모두 대답을 했고, 동규는 연종이 봤다고 주장하는 수 들을 ‘수첩2’에 적어 두었다. 집에 돌아온 동규는 답이 맞는지 확인하려 하지만, 연종을 따라다니느라 너무 힘들어서 여러분에게 도움을 요청했다. 동규를 도와주기 위해 ‘수첩2’에 적혀있는 순서대로, 각각의 수에 대하여, ‘수첩1’에 있으면 1을, 없으면 0을 출력하는 프로그램을 작성해보자.

출처 : https://www.acmicpc.net/problem/2776

2. 아이디어

• mine*

  1. 이진 탐색 활용

3. 코드

mine

import sys
input = sys.stdin.readline
>
def binary_search(a, x):
  start = 0
  end = len(a)-1
>
  while start <= end:
    mid = (start+end) // 2
    if x == a[mid]: # 발견 
      print(1)
      return
    elif x > a[mid]: # 찾는 값이 크면 오른쪽으로 범위를 좁혀 계속 탐색
      start = mid + 1
    else: # 찾는 값이 작으면 왼쪽으로 범위를 좁혀 계속 탐색
      end = mid - 1
  print(0) # 미발견
>
t = int(input())
for _ in range(t):
  n1 = int(input())
  arr1 = list(map(int, input().split()))
  n2 = int(input())
  arr2 = list(map(int, input().split()))
  arr1.sort() # 탐색할 리스트 정렬
  for i in arr2:
    binary_search(arr1, i)

김형택은 지금 몰래 Spider Solitaire(스파이더 카드놀이)를 하고 있다. 형택이는 이 게임을 이길 때도 있었지만, 질 때도 있었다. 누군가의 시선이 느껴진 형택이는 게임을 중단하고 코딩을 하기 시작했다. 의심을 피했다고 생각한 형택이는 다시 게임을 켰다. 그 때 형택이는 잠시 코딩을 하는 사이에 자신의 게임 실력이 눈에 띄게 향상된 것을 알았다.

이제 형택이는 앞으로의 모든 게임에서 지지 않는다. 하지만, 형택이는 게임 기록을 삭제 할 수 없기 때문에, 자신의 못하던 예전 기록이 현재 자신의 엄청난 실력을 증명하지 못한다고 생각했다.

게임 기록은 다음과 같이 생겼다.

게임 횟수 : X 이긴 게임 : Y (Z%) Z는 형택이의 승률이고, 소수점은 버린다. 예를 들어, X=53, Y=47이라면, Z=88이다. X와 Y가 주어졌을 때, 형택이가 게임을 최소 몇 번 더 해야 Z가 변하는지 구하는 프로그램을 작성하시오.

출처 : https://www.acmicpc.net/problem/1072

2. 아이디어

• mine*

  1. Z = (y+a)/(x+a)*100
  2. a = ((x * z) + x - (100 * y)) / (99 - z)
  3. 승률 99퍼 이상인 경우 승률이 오를 수 없으므로 -1 출력, 그게 아닌 경우 주어진 조건 활용

3. 코드

mine

import sys
from math import ceil
input = lambda : sys.stdin.readline()
x, y = map(int, input().split())
z = y * 100 // x
if z >= 99:
    print(-1)
else:
    a = ceil(((x * z) + x - (100 * y)) / (99 - z))
    print(a)

국가의 역할 중 하나는 여러 지방의 예산요청을 심사하여 국가의 예산을 분배하는 것이다. 국가예산의 총액은 미리 정해져 있어서 모든 예산요청을 배정해 주기는 어려울 수도 있다. 그래서 정해진 총액 이하에서 가능한 한 최대의 총 예산을 다음과 같은 방법으로 배정한다.

모든 요청이 배정될 수 있는 경우에는 요청한 금액을 그대로 배정한다. 모든 요청이 배정될 수 없는 경우에는 특정한 정수 상한액을 계산하여 그 이상인 예산요청에는 모두 상한액을 배정한다. 상한액 이하의 예산요청에 대해서는 요청한 금액을 그대로 배정한다. 예를 들어, 전체 국가예산이 485이고 4개 지방의 예산요청이 각각 120, 110, 140, 150이라고 하자. 이 경우, 상한액을 127로 잡으면, 위의 요청들에 대해서 각각 120, 110, 127, 127을 배정하고 그 합이 484로 가능한 최대가 된다.

여러 지방의 예산요청과 국가예산의 총액이 주어졌을 때, 위의 조건을 모두 만족하도록 예산을 배정하는 프로그램을 작성하시오.

출처 : https://www.acmicpc.net/problem/2512

2. 아이디어

• mine*

  1. 이진 탐색 활용
  2. 중간 지점을 정하여 숫자가 중간 지점보다 크면 중간 지점값을, 아니면 숫자를 total에 더해준다.
  3. total이 m보다 크면 그보다 아래쪽을 탐색하고 아니면 위쪽을 탐색한다.
  4. 이를 반복하여 result를 구한다.

3. 코드

mine

import sys
from bisect import bisect_left
input = sys.stdin.readline
>
n = int(input())
arr = list(map(int, input().split()))
m = int(input())
result = 0
start = 0
end = max(arr)
>
while start <= end:
  total = 0
  mid = (start + end) // 2
  for i in arr:
    if i > mid:
      total += mid
    else:
      total += i
  if total > m:
    end = mid - 1
  else:
    result = mid
    start = mid + 1
>
print(result)

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.

예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.

출처 : https://www.acmicpc.net/problem/14002

2. 아이디어

• mine* (원인 불명 실패 - 틀렸습니다❗)

  1. bisect를 사용한 LIS

clone

1. bisect를 사용한 LIS 리스트 : q
2. (들어갈 위치, 값)의 쌍을 넣는 배열 : t
3. 들어갈 위치와 인덱스를 비교하여 ans에 추가 -> [50, 30, 20, 10]

3. 코드

mine

import sys
from bisect import bisect_left
input = sys.stdin.readline
>
def get_lis_improved(sequence):
  L = [sequence[0]]
  for i in range(1, len(sequence)):
    if L[-1] < sequence[i]:
      L.append(sequence[i])
    else:
      lower_bound = bisect_left(L, sequence[i])
      L[lower_bound] = sequence[i]
  # print(L)
  return L
>
n = int(input())
arr = list(map(int, input().split()))
result = get_lis_improved(arr)
print(len(result))
for res in result:
  print(res, end = ' ')

clone

import sys
from bisect import bisect_left
n=int(sys.stdin.readline())
arr=list(map(int,sys.stdin.readline().split()))
>
q=[arr[0]]
t=[] # (들어갈 위치, 값)의 쌍을 넣는 배열
# 여기는 이전 문제들과 비슷하다.
#  다만 t라는 새로운 배열에 갱신되는 배열 요소의 위치, 요소 값에 대한 정보도 추가하는게 다르다
for x in arr:
    if q[-1]<x:
        q.append(x)
        t.append((len(q)-1,x))
    else:
        idx=bisect_left(q,x)
        q[idx]=x
        t.append((idx,x))
>
# 최종 배열의 길이를 구했으면 마지막 위치부터 가장 큰 요소를 넣는다 (실제 요소)       
last_idx=len(q)-1
>
# 덮어씌워진 요소가 아니라 기존 요소를 넣어준다 
ans=[]
for i in range(n-1,-1,-1):
    if t[i][0]==last_idx:
        ans.append(t[i][1])
        last_idx-=1
>
print(len(q))
# *을 붙이면 자동으로 리스트 요소를 공백으로 구분해 반환해준다
print(*reversed(ans))

출처 : https://haerang94.tistory.com/131

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.

예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.

출처 : https://www.acmicpc.net/problem/12738

2. 아이디어

• mine*

  1. 반도체 설계와 같은 원리

3. 코드

mine

import sys
from bisect import bisect_left
input = sys.stdin.readline
>
def get_lis_improved(sequence):
  L = [sequence[0]]
  for i in range(1, len(sequence)):
    if L[-1] < sequence[i]:
      L.append(sequence[i])
    else:
      lower_bound = bisect_left(L, sequence[i])
      L[lower_bound] = sequence[i]
  # print(L)
  return len(L)
>
n = int(input())
arr = list(map(int, input().split()))
print(get_lis_improved(arr))

정수가 주어지면, 그 수의 정수 제곱근을 구하는 프로그램을 작성하시오.

출처 : https://www.acmicpc.net/problem/2417

2. 아이디어

• mine*

  1. 제곱근을 구한 후 ceil 함수를 통해 올림

11060445.038765619 -> 11060446

3. 코드

mine

import sys
from math import ceil
input = sys.stdin.readline
>
n = int(input())
result = ceil(n ** 0.5)
print(result)

반도체를 설계할 때 n개의 포트를 다른 n개의 포트와 연결해야 할 때가 있다.

예를 들어 왼쪽 그림이 n개의 포트와 다른 n개의 포트를 어떻게 연결해야 하는지를 나타낸다. 하지만 이와 같이 연결을 할 경우에는 연결선이 서로 꼬이기 때문에 이와 같이 연결할 수 없다. n개의 포트가 다른 n개의 포트와 어떻게 연결되어야 하는지가 주어졌을 때, 연결선이 서로 꼬이지(겹치지, 교차하지) 않도록 하면서 최대 몇 개까지 연결할 수 있는지를 알아내는 프로그램을 작성하시오

출처 : https://www.acmicpc.net/problem/2352

2. 아이디어

• mine + clone* (❗)

  1. LIS(가장 긴 증가하는 부분 수열)를 사용해야 되는 것은 알았지만 파이썬 bisect로 구현할 줄 몰라서 찾아봄.
  2. 이해를 위해 파이썬 튜터 사용 (http://pythontutor.com/visualize.html#mode=display)
  3. bisect로 L에 들어갈 위치를 찾아서 넣거나 추가해주는 방법(코드와 파이썬 튜터 참고)

출처 : https://lgphone.tistory.com/129

3. 코드

mine + clone

import sys
input = sys.stdin.readline
>
# O(N log N)
from bisect import bisect_left
>
def get_lis_improved(sequence):
  L = [sequence[0]]
  for i in range(1, len(sequence)):
    if L[-1] < sequence[i]:
      L.append(sequence[i])
    else:
      lower_bound = bisect_left(L, sequence[i])
      L[lower_bound] = sequence[i]
  # print(L)
  return len(L)
>
n = int(input())
arr = list(map(int, input().split()))
print(get_lis_improved(arr))

숫자 카드는 정수 하나가 적혀져 있는 카드이다. 상근이는 숫자 카드 N개를 가지고 있다. 정수 M개가 주어졌을 때, 이 수가 적혀있는 숫자 카드를 상근이가 몇 개 가지고 있는지 구하는 프로그램을 작성하시오.

출처 : https://www.acmicpc.net/problem/10816

2. 아이디어

• mine* (시간 초과❗)

  1. 이진탐색으로 찾은 숫자를 이진탐색을 한 범위내에서 count해준다.

• clone1

  1. dictionary로 각 요소마다 카운트를 해서 key-value 매칭을 한다.
  2. 해당 숫자의 count 값을 출력한다.

출처 : https://tmdrl5779.tistory.com/116

• clone2

  1. bisect_left, bisect_right 사용
  2. bisect_right - bisect_left를 하면 count 할 수 있음

출처 : https://www.youtube.com/watch?v=jjOmN2_lmdk&list=PLVsNizTWUw7H9_of5YCB0FmsSc-K44y81&index=27

3. 코드

mine

import sys
input = sys.stdin.readline
>
def binary_search(a, x):
  start = 0
  end = len(a)-1
>
  while start <= end:
    mid = (start+end) // 2
    if x == a[mid]: # 발견 
      return a[start:end+1].count(x)
    elif x > a[mid]: # 찾는 값이 크면 오른쪽으로 범위를 좁혀 계속 탐색
      start = mid + 1
    else: # 찾는 값이 작으면 왼쪽으로 범위를 좁혀 계속 탐색
      end = mid - 1
  return False # 미발견
>
n1 = int(input())
arr1 = list(map(int, input().split()))
n2 = int(input())
arr2 = list(map(int, input().split()))
arr1.sort() # 탐색할 리스트 정렬
for i in arr2:
  result = binary_search(arr1, i)
  if result:
    print(result, end = ' ')
  else:
    print(0, end = ' ')

clone1

n = int(input())
cards = list(map(int, input().split(' ')))
cards.sort()
>
m = int(input())
targets = list(map(int, input().split(' ')))
>
dic = dict()
>
for i in cards:
    if i in dic:
        dic[i] += 1
    else:
        dic[i] = 1
>
for i in range(m):
    if targets[i] in dic:
        print(dic[targets[i]], end=' ')
    else:
        print(0, end=' ')

출처 : https://tmdrl5779.tistory.com/116

clone2

import sys
from bisect import bisect_left, bisect_right
input = sys.stdin.readline
>
def count_by_range(arr, left_value, right_value):
  right_index = bisect_right(arr, right_value)
  left_index = bisect_left(arr, left_value)
  return right_index - left_index
>
n1 = int(input())
arr1 = list(map(int, input().split()))
n2 = int(input())
arr2 = list(map(int, input().split()))
arr1.sort()
for i in arr2:
  result = count_by_range(arr1, i, i)
  if result == 0:
    print(0, end = ' ')
  else:
    print(result, end = ' ')

출처 : https://www.youtube.com/watch?v=jjOmN2_lmdk&list=PLVsNizTWUw7H9_of5YCB0FmsSc-K44y81&index=27

4. 결과 비교

1. mine 시간 초과
2. clone1
3. clone2

숫자 카드는 정수 하나가 적혀져 있는 카드이다. 상근이는 숫자 카드 N개를 가지고 있다. 정수 M개가 주어졌을 때, 이 수가 적혀있는 숫자 카드를 상근이가 가지고 있는지 아닌지를 구하는 프로그램을 작성하시오.

출처 : https://www.acmicpc.net/problem/10815

2. 아이디어

• mine*

  1. 이분 탐색을 한다.
  2. 찾으면 1을 출력 후 return 아니면 0을 출력

이분탐색 출처 : https://wayhome25.github.io/cs/2017/04/15/cs-16/

3. 코드

mine

import sys
input = sys.stdin.readline
>
def binary_search(a, x):
  start = 0
  end = len(a)-1
>
  while start <= end:
    mid = (start+end) // 2
    if x == a[mid]: # 발견 
      print(1, end = ' ')
      return
    elif x > a[mid]: # 찾는 값이 크면 오른쪽으로 범위를 좁혀 계속 탐색
      start = mid + 1
    else: # 찾는 값이 작으면 왼쪽으로 범위를 좁혀 계속 탐색
      end = mid - 1
  print(0, end = ' ') # 미발견
>
n1 = int(input())
arr1 = list(map(int, input().split()))
n2 = int(input())
arr2 = list(map(int, input().split()))
arr1.sort() # 탐색할 리스트 정렬
for i in arr2:
  binary_search(arr1, i)

전화번호 목록이 주어진다. 이때, 이 목록이 일관성이 있는지 없는지를 구하는 프로그램을 작성하시오.

전화번호 목록이 일관성을 유지하려면, 한 번호가 다른 번호의 접두어인 경우가 없어야 한다.

예를 들어, 전화번호 목록이 아래와 같은 경우를 생각해보자

긴급전화: 911 상근: 97 625 999 선영: 91 12 54 26 이 경우에 선영이에게 전화를 걸 수 있는 방법이 없다. 전화기를 들고 선영이 번호의 처음 세 자리를 누르는 순간 바로 긴급전화가 걸리기 때문이다. 따라서, 이 목록은 일관성이 없는 목록이다.

출처 : https://www.acmicpc.net/problem/5052

2. 아이디어

• mine* (문법 오류❗)

  1. 전화번호를 오름차순으로 정렬하면 i와 i+1만 비교하면 된다.
  2. 포함 여부를 확인할 때 문법적인 오류때문에 실패했다.

• clone

  1. NO가 나오면 break
  2. arr[i+1][:len(arr[i])]

출처 : https://jinho-study.tistory.com/311

3. 코드

mine

import sys
input = sys.stdin.readline
t = int(input())
for _ in range(t):
  n = int(input())
  arr = []
  tag = True
  for __ in range(n):
    arr.append(input())
  arr.sort()
  for i in range(n-1):
    if arr[i] in arr[i+1]:
      print('NO')
      tag = False
  if tag:
    print('YES')

clone

import sys
>
t = int(sys.stdin.readline())
>
endFlag = False
>
for _ in range(t):
    n = int(sys.stdin.readline())
    numberList = list(sys.stdin.readline().rstrip() for _ in range(n))
    numberList.sort()
>
    for i in range(len(numberList)-1):
        if numberList[i] in numberList[i+1][:len(numberList[i])]:
            print("NO")
            endFlag = True
            break
    if endFlag == False:
        print("YES")
    endFlag = False

출처 : https://kyoung-jnn.tistory.com/88

언제나 최고만을 지향하는 굴지의 대기업 진영 주식회사가 신규 사원 채용을 실시한다. 인재 선발 시험은 1차 서류심사와 2차 면접시험으로 이루어진다. 최고만을 지향한다는 기업의 이념에 따라 그들은 최고의 인재들만을 사원으로 선발하고 싶어 한다.

그래서 진영 주식회사는, 다른 모든 지원자와 비교했을 때 서류심사 성적과 면접시험 성적 중 적어도 하나가 다른 지원자보다 떨어지지 않는 자만 선발한다는 원칙을 세웠다. 즉, 어떤 지원자 A의 성적이 다른 어떤 지원자 B의 성적에 비해 서류 심사 결과와 면접 성적이 모두 떨어진다면 A는 결코 선발되지 않는다.

이러한 조건을 만족시키면서, 진영 주식회사가 이번 신규 사원 채용에서 선발할 수 있는 신입사원의 최대 인원수를 구하는 프로그램을 작성하시오.

출처 : https://www.acmicpc.net/problem/1946

2. 아이디어

• mine* (시간 초과❗)

  1. 서류 순위를 기준으로 오름차순 정렬을 한다.
  2. 처음부터 마지막까지 자신보다 면접 순위가 높은 항목이 있으면 count를 해주고 두 번째 순위가 1인 것을 만나면 break
  3. 전체를 반복해 준 후 카운트값이 가장 큰 값을 출력.

• clone

  1. 서류 순위를 기준으로 오름차순 정렬을 한다.
  2. 첫 번째 사람을 기준으로 하여 높은 면접 순위가 있으면 count를 해주고 기준을 높은 면접 순위로 바꿔준다.
  3. 이를 반복한다.

출처 : https://kyoung-jnn.tistory.com/entry/%EB%B0%B1%EC%A4%801946%EB%B2%88%ED%8C%8C%EC%9D%B4%EC%8D%ACPython-%EC%8B%A0%EC%9E%85-%EC%82%AC%EC%9B%90

3. 코드

mine

import sys
input = sys.stdin.readline
t = int(input())
for _ in range(t):
  n = int(input())
  arr = []
  maxCount = 0
  count = 1
  for __ in range(n):
    arr.append(list(map(int, input().split())))
  arr.sort()
  for i in range(n-1):
    for j in range(i+1, n):
      if arr[i][1] > arr[j][1]:
        count += 1
        if arr[j][1] == 1:
          break
    if maxCount < count:
      maxCount = count
    count = 1
  print(maxCount)

clone

import sys
>
T = int(input()) #테스트케이스
>
for i in range(0,T):
    Cnt = 1
    people = []
 >   
    N = int(input())
    for i in range(N):
        Paper, Interview = map(int,sys.stdin.readline().split())
        people.append([Paper, Interview])
>
    people.sort() # 서류 기준 오름차순 정렬
    Max = people[0][1]
 >   
    for i in range(1,N):
        if Max > people[i][1]:
            Cnt += 1
            Max = people[i][1]
>
    print(Cnt)

출처 : https://kyoung-jnn.tistory.com/entry/%EB%B0%B1%EC%A4%801946%EB%B2%88%ED%8C%8C%EC%9D%B4%EC%8D%ACPython-%EC%8B%A0%EC%9E%85-%EC%82%AC%EC%9B%90

심해에는 두 종류의 생명체 A와 B가 존재한다. A는 B를 먹는다. A는 자기보다 크기가 작은 먹이만 먹을 수 있다. 예를 들어, A의 크기가 {8, 1, 7, 3, 1}이고, B의 크기가 {3, 6, 1}인 경우에 A가 B를 먹을 수 있는 쌍의 개수는 7가지가 있다. 8-3, 8-6, 8-1, 7-3, 7-6, 7-1, 3-1.

두 생명체 A와 B의 크기가 주어졌을 때, A의 크기가 B보다 큰 쌍이 몇 개나 있는지 구하는 프로그램을 작성하시오.

출처 : https://www.acmicpc.net/problem/7795

2. 아이디어

• mine* (시간 초과❗)

  1. 정렬 후 b에 있는 가장 큰 숫자부터 시작하여 a의 수 중 현재 b의 숫자보다 큰 수를 만나면 카운트. ex) b : 6, a : 8 이면 b에서 6의 인덱스는 2이고 정렬된 (1, 3, 6) 상태이므로 인덱스 + 1 을 해줘서 a의 8보다 작은 b의 숫자를 3으로 카운트.

• clone

  EX) A = [2, 7, 13], B = [11, 103, 215, 290] 일 때 cnt = 0 A[0] = 2 -> B에는 2보다 작은 수가 없음 -> res = -1 -> cnt += (-1 + 1) -> cnt = 0 A[1] = 7 -> B에는 7보다 작은 수가 없음 -> res = -1 -> cnt += (-1 + 1) -> cnt = 0 A[2] = 13 -> B에서 13보다 작은 수는 2 인덱스는 0 -> res = 0 -> cnt += (0 + 1) -> cnt = 1 결과: 1

출처 : https://jinho-study.tistory.com/311

3. 코드

mine

import sys
input = sys.stdin.readline
t = int(input())
result = []
for i in range(t):
  count = 0
  a, b = map(int, input().split())
  a = list(map(int, input().split()))
  b = list(map(int, input().split()))
  a.sort()
  b.sort()
  for j in a:
    for k in reversed(range(len(b))):
      if j > b[k]:
        count += k + 1
        break
  result.append(count)
for res in result:
  print(res)

clone

import bisect
>
for _ in range(int(input())):
    N, M = map(int, input().split())
    A = sorted(list(map(int, input().split())))
    B = sorted(list(map(int, input().split())))
    cnt = 0
    for a in A:
        cnt += (bisect.bisect(B, a-1))
    print(cnt)

출처 : https://jinho-study.tistory.com/311

여자친구와 함께 보드게임카페에 간 주언이는, 여러 보드게임을 하며 데이트를 즐겼다. 3시간 커플세트로 결제를 하려던 순간, 주언이는 가격표 옆에 쓰여 있는 새로운 이벤트를 보았다.

바로 “사장님과의 게임에서 이기면 무료, 지거나 비기면 5000원 추가 지불” 이벤트였다. 보드게임에 자신이 있는 주언이는 사장님에게 게임 룰을 물어보았고, 그 룰은 다음과 같았다.

각자 N장의 카드를 받는다. (N은 홀수다) 각자 카드를 1장씩 골라서 카드에 적힌 수의 크기를 비교한다. (각 카드에 적힌 수는 0이상, 100,000이하의 정수다) 더 작은 수가 적힌 카드를 낸 사람이 1점을 얻고, 승부에 사용된 카드는 버린다. (무승부의 경우, 둘 다 점수를 획득하지 못한다) 총 N번의 승부 후, (N+1)/2점 이상의 점수를 획득한 사람이 승리한다. (N+1)/2점 이상의 점수를 획득한 사람이 없을 경우, 승자가 없는 것으로 게임이 끝난다. 주언이는 자신이 이길 확률이 조금이라도 있을 경우 게임을 하고자 한다.

사장님이 받은 카드에 적힌 수들과, 주언이가 받은 카드에 적힌 수들이 주어질 때, 주언이가 게임을 해도 되는지 확인하자.

출처 : https://www.acmicpc.net/problem/16471

2. 아이디어

• mine* (시간 초과❗)

  1. 사장님과 주언이의 카드를 오름차순으로 정렬한다.
  2. 사장님의 첫번째 카드부터 꺼내어 주언이가 사장님보다 큰 카드가 최초로 나올 때까지 탐색한다. 나온다면 주언이의 해당 카드를 pop시키고 승점을 올린 후 다음 탐색을 진행한다.
  3. 탐색이 끝났는데도 주언이의 승점이 없다면 무승부거나 패배이므로 사장님의 승점을 올린다.
  4. 주언이의 승점이 전체 카드의 중간값보다 많다면 YES 출력
  5. 아니면 NO

• clone

  1. 사장님의 중간 이후 값과 주언이의 중간 이전 값을 비교하여 카운트값이 카드 개수의 절반 초과이면 YES, 아니면 NO

3. 코드

mine

import sys
input = sys.stdin.readline
n = int(input())
ceo_win = 0
jueon_win = 0
win = False
ceo = list(map(int, input().split()))
jueon = list(map(int, input().split()))
ceo.sort()
jueon.sort()
for i in range(len(ceo)):
  past_jueon_win = jueon_win
  for j in range(len(jueon)):
    if ceo[i] < jueon[j]:
      jueon_win += 1
      jueon.pop(j)
      break
  if past_jueon_win == jueon_win:
    ceo_win += 1
  if jueon_win > int(n/2):
    print('YES')
    win = True
    break
if not win:
  print('NO')

clone

import sys
>
n = int(input())
juon = list(map(int, sys.stdin.readline().split()))
sajang = list(map(int, sys.stdin.readline().split()))
>
juon.sort()
sajang.sort()
>
cnt = 0
>
for i in range(n // 2 + 1):
    if juon[i] < sajang[n // 2 + i]:
        cnt += 1
>
if cnt > n // 2:
    print("YES")
else:
    print("NO")

출처 : https://github.com/mori8/baekjoon-algorithm-python/commit/a1282322f59c87abbcf0b01618975a2aea2381b3

수 N개 A1, A2, ..., AN이 주어진다. A를 오름차순 정렬했을 때, 앞에서부터 K번째 있는 수를 구하는 프로그램을 작성하시오.

출처 : https://www.acmicpc.net/problem/11004

2. 아이디어

• mine*

  1. 입력 받은 리스트에서 k-1 출력

3. 코드

mine

n, k = map(int, input().split())
arr = list(map(int, input().split()))
arr.sort()
print(arr[k-1])

2차원 평면 위의 점 N개가 주어진다. 좌표를 x좌표가 증가하는 순으로, x좌표가 같으면 y좌표가 증가하는 순서로 정렬한 다음 출력하는 프로그램을 작성하시오.

출처 : https://www.acmicpc.net/problem/11650

2. 아이디어

• mine*

  1. x좌표 크기를 우선적으로 정렬한 후 y좌표를 정렬해준다.

• clone*

  1. 2차원 배열에서는 그냥 sort()를 했을 경우 첫 번째 키 값이 동일하면 자동으로 그 다음 키 값에 따라 정렬 (출처 : https://dev-note-97.tistory.com/13)

3. 코드

mine

n = int(input())
xy = []
for _ in range(n):
  xy.append(list(map(int,input().split())))
xy.sort(key = lambda x : (x[0],x[1])) # 그냥 sort()도 됨
for result in xy:
  print(result[0], result[1])

4. 결과 비교

1. mine 2. clone

• 속도는 큰 차이가 없으나 메모리 측면에서 clone 코드가 나의 코드보다 8000KB정도 절약된다.