JinWoo Kim

백문이 불여일견, 백견이 불여일행.

4 minute read

  • 이번주부터는 ‘자료 구조’를 주제로 코딩테스트 연습을 시작했다.

기초 개념 정리

자료 구조

  • 자료구조(資料構造, 영어: data structure)는 컴퓨터 과학에서 효율적인 접근 및 수정을 가능케 하는 자료의 조직, 관리, 저장을 의미한다.(위키백과)

선형 구조

  • 스택
    • Last In, First Out (LIFO)
    • 한쪽 끝에서만 자료를 넣고 뺄수 있는 개념.
    • push로 데이터를 밀어넣고, pop으로 데이터를 뺀다.
  • 큐
    • First In, First Out (FIFO)
    • 줄을 설때, 먼저 선 사람이 먼저 들어가는것처럼 작동함.
    • put(insert)으로 데이터를 넣고, get(delete)으로 데이터를 뺀다.
  • 덱
    • 양쪽 끝에서 삽입과 삭제가 가능한 구조.
    • double-ended queue의 축약어인 deque라서 덱으로 불림.
    • 스택과 큐를 합친 형태로 생각할수 있다.

비선형 구조

  • 그래프
    • vertex(정점)와 edge(간선)로 한정된 자료구조.
    • 간선이 방향성을 갖는지의 유무로 유향 그래프, 무향 그래프로 구분한다.
  • 트리
    • 그래프의 일종으로, 여러 노드가 한 노드를 가리킬수 없는 구조.
    • 최상위 노드를 루트 노드라고 한다.
    • 노드 A가 노드 B를 가리킬 때 A를 B의 부모 노드(parent node), B를 A의 자식 노드(child node)라고 한다.
    • 자식 노드가 없는 노드를 잎 노드(leaf node, 리프 노드)라고 한다.
    • 잎 노드가 아닌 노드를 내부 노드(internal node)라고 한다.
  • 이진 트리
    • 트리 중에서 자식이 최대 두개인 트리를 이진 트리라고 한다.
    • 이진 트리의 구현은 크게 두가지 방법이 있다.
      1. 1차원 배열 표현: 이진 트리의 i번째 노드를 배열의 i번째 요소에 저장하는 방법이다.
        • 장점: 노드의 위치를 색인에 의하여 쉽게 접근할 수 있다.
        • 단점: 특정 트리에서 기억 공간의 낭비가 심할 수 있다.
      2. 연결리스트 표현: 왼쪽 자식을 가리키는 포인터 필드와 오른쪽 자식을 가리키는 포인터 필드를 포함하는 노드로 표현하는 방법이다.
        • 장점: 기억 장소를 절약할 수 있고, 노드의 삽입과 삭제가 용이하다.
        • 단점: 이진 트리가 아닌 일반 트리의 경우에는 각 노드의 차수만큼 가변적인 포인터 필드를 가져야 하기 때문에 접근상의 어려움이 따른다.

코딩테스트 연습

1. 트럭

  • 강을 가로지르는 하나의 차선으로 된 다리가 하나 있다.
  • 이 다리를 n 개의 트럭이 건너가려고 한다.
  • 트럭의 순서는 바꿀 수 없으며, 트럭의 무게는 서로 같지 않을 수 있다.
  • 다리 위에는 단지 w 대의 트럭만 동시에 올라갈 수 있다.
  • 다리의 길이는 w 단위길이(unit distance)이며, 각 트럭들은 하나의 단위시간(unit time)에 하나의 단위길이만큼만 이동할 수 있다고 가정한다.
  • 동시에 다리 위에 올라가 있는 트럭들의 무게의 합은 다리의 최대하중인 L보다 작거나 같아야 한다.

  • 참고로, 다리 위에 완전히 올라가지 못한 트럭의 무게는 다리 위의 트럭들의 무게의 합을 계산할 때 포함하지 않는다고 가정한다.

  • 예를 들어, 다리의 길이 w는 2, 다리의 최대하중 L은 10, 다리를 건너려는 트럭이 트럭의 무게가 [7, 4, 5, 6]인 순서대로 다리를 오른쪽에서 왼쪽으로 건넌다고 하자.

    • 이 경우 모든 트럭이 다리를 건너는 최단시간은 아래의 그림에서 보는 것과 같이 8 이다.

      이미지

  • 다리의 길이와 다리의 최대하중, 그리고 다리를 건너려는 트럭들의 무게가 순서대로 주어졌을 때, 모든 트럭이 다리를 건너는 최단시간을 구하는 프로그램을 작성하라.

입력

  • 입력 데이터는 표준입력을 사용한다. 입력은 두 줄로 이루어진다.
  • 입력의 첫 번째 줄에는 세 개의 정수 n (1 ≤ n ≤ 1,000) , w (1 ≤ w ≤ 100) and L (10 ≤ L ≤ 1,000)이 주어진다.
    • 이때 n은 다리를 건너는 트럭의 수, w는 다리의 길이, 그리고 L은 다리의 최대하중을 나타낸다.
  • 입력의 두 번째 줄에는 n개의 정수 a1, a2, ⋯ , an (1 ≤ ai ≤ 10)가 주어지는데, ai는 i번째 트럭의 무게를 나타낸다.

출력

  • 출력은 표준출력을 사용한다. 모든 트럭들이 다리를 건너는 최단시간을 출력하라.

풀이


# your code goes here
 
import sys
from collections import deque
 
# 입력의 첫 번째 줄에는 세 개의 정수 n (1 ≤ n ≤ 1,000), w (1 ≤ w ≤ 100) and L (10 ≤ L ≤ 1,000)이 주어지는데,
# n은 다리를 건너는 트럭의 수
# w는 다리의 길이
# 그리고 L은 다리의 최대하중을 나타낸다.
 
n,w,L = list(map(int,sys.stdin.readline().split()))
 
# 입력의 두 번째 줄에는 n개의 정수 a1, a2, ⋯ , an (1 ≤ ai ≤ 10)가 주어지는데,
# ai는 i번째 트럭의 무게를 나타낸다.
 
ai_arr = list(map(int,sys.stdin.readline().split()))
 
# 트럭의 순서는 바꿀 수 없으며, 트럭의 무게는 서로 같지 않을 수 있다.
# 다리 위에는 단지 w 대의 트럭만 동시에 올라갈 수 있다.
# 각 트럭들은 하나의 단위시간(unit time)에 하나의 단위길이만큼만 이동할 수 있다고 가정한다.
# 다리 위에 올라가 있는 트럭들의 무게의 합은 다리의 최대하중인 L보다 작거나 같아야 한다
 
# 다리는 선입 선출의 구조를 띈다.
# 다리의 내부 원소 합이 L보다 작거나 같아야 한다.
 
bridge = deque()
time = 0
 
while(True):

	# 다리와 대기중인 트럭 둘 다 비어있다면, 루프를 종료한다.
	if len(bridge) == 0 and len(ai_arr) == 0:
		break
 
	time += 1
 
	# 다리를 건너는 트럭은 다리길이 시간 이후에는 다리를 빠져나가므로, 다리시간 이후부터 다리의 제일 앞 요소를 제거한다.
	if time > w:
		del bridge[0]
 
	# 대기열이 존재하지 않을때,
	if ai_arr != []:
		# 다리 위의 모든 트럭 무게 합과 대기중인 첫번째 트럭 무게가 하중보다 작다면, 다리 위로 올라온다.
		if sum(bridge)+ai_arr[0] <= L:
			bridge.append(ai_arr.pop(0))
		# 다리 위의 모든 트럭 무게 합과 대기중인 첫번째 트럭 무게가 하중보다 크다면, 한 단위시간동안 대기한다.
		elif sum(bridge)+ai_arr[0] > L:
			bridge.append(0)
 
print(time)

채점 결과

  • 정답

더 나은 풀이법


n, w, L = map(int, input().split())
trucks = list(map(int , input().split()))
on_turn = [0] * n

on_weight = 0
on_num = 0

turn = 1
rear = 0
head = 0
while rear < n:
    if on_turn[head] != 0 and on_turn[head] + w == turn:
        on_weight -= trucks[head]
        head += 1

    if on_weight + trucks[rear] <= L:
        on_turn[rear] = turn
        on_weight += trucks[rear]
        rear += 1
        turn += 1
    else:
        turn = on_turn[head] + w

print(turn + w - 1)

더 나은 풀이법 해설

  • truck 배열에 대해 가상의 head와 rear포인트를 지정함으로 유사 큐를 구현한다.

  • on_turn배열에 각 차량이 다리에 들어간 시간을 저장하여 w시간 뒤에 나오는것을 구현.

  • on_weight를 통해 on_turn 배열에 들어가는 조건을 제어.

  • 마지막 차량이 들어간 시간 + 다리길이 - 1로 마지막 차량이 들어간 시간을 구한다.

  • 내 풀이에 비해 장점은 다음과 같다.
    • 실행시간이 짧다.
      • 실제 배열(큐)를 조작한 나와 달리, 가상의 head와 rear를 통해 포인터 형식으로 데이터를 조작했으므로, 실제 배열값을 처리하는 나의 풀이보다 훨씬 빠르게 작동한다.
    • 조금 더 큐의 작동 방식과 비슷하게 구현되어있다.
      • head와 rear를 통해 선입선출을 구현하는 방식.
  • 내 풀이가 조금 더 가지는 장점은 다음과 같다.
    • 실질적으로 다리 위에 올라가는 트럭에 대한 배열을 만들어 진행함으로 인해 생기는 직관성

You May Also Enjoy