Classic_Blue_Note

문제

www.acmicpc.net/problem/2164

풀이

큐 자료구조를 사용하는 문제이다. 선입선출의 원리를 이용한다.

자료구조는 python collections 모듈의 deque를 사용했고, 해당 자료구조를 이용하여 큐를 구현하였다.

큐 자료구조의 원리를 안다면 간단히 풀리는 문제이다.

종종 인덱스 에러가 발생하는 경우가 있는데, 인덱스 에러가 발생할 경우 경계값 부분을 디버깅 해 볼 필요가 있다. 조건을 확인하고, 해당 조건에서는 1과 500000이 경계값이므로 해당 값이 적절하게 들어가는지 확인해 볼 필요가 있다.

코드

from collections import deque

N = int(input())

queue = deque()

for i in range(N):
    queue.appendleft(i+1)

while True:
    if len(queue) == 1:
        break
    queue.pop()
    tmp = queue.pop()
    queue.appendleft(tmp)

print(queue[0])

문제

www.acmicpc.net/problem/18258

풀이

이번 문제는 큐를 구현하는 문제이다. 파이썬에서는 collections 모듈의 deque 클래스를 이용하여 큐를 이용할 수 있다.(엄밀히는 덱이지만, 덱을 큐처럼 사용하면 된다.)

앞의 스택 구현 문제와 유사하게, isempty 함수만 별도로 구현하여 사용하였고, 나머지는 바로 출력하였다.

그러나 처음에는 시간 초과 에러가 발생했는데, 이유를 처음에는 찾지 못했으나 최대한 시간을 줄이기 위해 구글링해 본 결과 입력 과정에서 오버헤드가 발생한다는 것을 확인할 수 있었다. 실제로 sys.stdin.readline() 메소드를 이용하여 입력받으니 시간 초과가 발생하지 않았으며, 문제를 정상적으로 해결할 수 있었다.

이번 문제를 풀면서 큐의 기본적인 사용 방법을 확인할 수 있었고, 파이썬의 입력 과정에서 생각보다 큰 오버헤드가 발생할 수 있다는 점을 알 수 있었다. 다음부터는 sys 모듈을 이용하여 입력받는 습관을 들이는 편이 시간 단축에 더 유리할 것 같다.

코드

from collections import deque
import sys

N = int(input())


def isempty(data):
    return len(data) == 0


queue = deque()

for i in range(N):
    cmd = sys.stdin.readline().split()
    if cmd[0] == "push":
        queue.append(int(cmd[1]))
        
    elif cmd[0] == "pop":
        if isempty(queue):
            print(-1)
        else:
            print(queue.popleft())
            
    elif cmd[0] == "size":
        print(len(queue))
        
    elif cmd[0] == "empty":
        if isempty(queue):
            print(1)
        else:
            print(0)
            
    elif cmd[0] == "front":
        if isempty(queue):
            print(-1)
        else:
            print(queue[0])
            
    elif cmd[0] == "back":
        if isempty(queue):
            print(-1)
        else:
            print(queue[-1])

문제

www.acmicpc.net/problem/9012

풀이

스택 개념을 이용하되, 실제로 스택을 구현하지 않고 풀이하였다.

우선 데이터를 입력받은 뒤, VPS를 확인해주는 함수를 작성하였다. 이때, VPS를 판별하기 위해 별도의 sum이라는 값을 활용했는데, 예외 상황을 모두 고려하기 위해 if-else문을 이용하여 작성하였다.

(을 만날 때마다 1씩 더하고, )을 만나면 1을 뺀다. 이때 (가 모두 사라진 상태에서 )를 만날 경우 VPS가 아니기 때문에 NO를 출력한다.

모든 연산이 끝난 상태에서 (와 )의 개수가 같을 경우 sum값이 0이어야 하기 때문에, 이때 YES를, 아닌 경우 NO를 출력한다.

연산이나 저장 장소가 필요한 경우 스택을 사용해도 되지만, 이 문제에서는 별도의 연산이 필요 없고, 존재 유무 및 스택의 길이 정도만 확인하면 되기 때문에 스택을 직접 사용하지는 않고 해당 개념만 차용했다.

코드

T = int(input())

data = []
for i in range(T):
    data.append(input())


def VPS(test):
    sum = 0
    
    for char in test:
        if char == "(":
            sum += 1
            
        else:
            if sum == 0:
                return "NO"
                
            else:
                sum -= 1
                
    if sum == 0:
        return "YES"
        
    else:
        return "NO"

for test in data:
    print(VPS(test))

문제

www.acmicpc.net/problem/10828

풀이

스택을 구현하는 문제이다. 파이썬의 경우, 스택을 직접 구현하지 않고도, 리스트를 이용해서 유연하게 사용할 수 있다.

push의 경우 operand가 존재하기 때문에 입력받을 때부터 split 메소드를 이용하여 입력받았다.

좀더 스택스럽게 구현하기 위해 isempty 함수만 별도로 구현했고, 나머지는 기존 리스트 클래스에 존재하는 메소드를 이용하여 구현하였다.

인덱스 값 중 -1은 맨 뒤의 위치를 의미하는 인덱스이다. append 메소드를 사용하면 리스트에서 자연스럽게 뒤쪽으로 값이 추가되기 때문에, 뒤의 값을 빼내기 위해 -1 인덱스를 활용하였다. insert 메소드를 통해 값을 앞에 넣을수도 있지만, append는 O(1)의 시간 복잡도를 갖고, insert는 O(n)의 시간 복잡도를 갖기 때문에 append 메소드를 활용하였다.

코드

N = int(input())

op_list = []

for i in range(N):
    op_list.append(input().split(" "))


def isempty(stack):
    return len(stack) == 0


st = []

for op in op_list:
    if op[0] == "push":
        st.append(int(op[1]))
        
    elif op[0] == "pop":
        if isempty(st):
            print(-1)
        else:
            print(st.pop(-1))
            
    elif op[0] == "size":
        print(len(st))
        
    elif op[0] == "empty":
        if isempty(st):
            print(1)
        else:
            print(0)
            
    elif op[0] == "top":
        if isempty(st):
            print(-1)
        else:
            print(st[-1])

문제

www.acmicpc.net/problem/1158

풀이

해당 문제는 비교적 간단한 solved.ac 기준 실버 5급 문제로, 처음에는 원형 큐를 사용해야 할 지 고민했지만, 조금 생각해 보니 굳이 원형 큐를 구현할 필요 없이, 리스트와 인덱스 포인터만을 이용하여 간단하게 해결할 수 있다.

필자의 경우, 우선 사람 배열을 만들고, 제거할 사람의 위치를 가리키는 인덱스 포인터를 지정했다. 그리고 해당 인덱스 포인터에 K값을 더해 가면서, 해당 값이 사람 배열의 크기보다 커지면 나눠 줘 가면서 원형으로 이동하는 것을 표현했다.

그리고 사람을 빼낸 다음, 빼낸 사람을 그대로 요세푸스 배열에 추가한다. 이때 사람을 빼낸 후 인덱스 포인터를 1만큼 감소시켜야 하는데, 그 이유는 사람을 빼내면서 자연스럽게 인덱스 포인터가 다음 사람을 가리키게 되기 때문에, 다음 사람을 1번째 사람으로 표현하기 위해서는 인덱스 포인터를 함께 1만큼 감소시켜 줘야 한다.

출력 형식에서 약간의 문제가 있었는데, 파이썬 메소드 중 __str__ 메소드를 이용하여 간단하게 해결하였다. 리스트의 경우 __str__ 메소드를 거치면 [a, b, c] 형태로 출력되기 때문에, 해당 메소드를 호출한 뒤 맨 앞과 맨 뒤의 문자만 제거하고, 해당 부분에 <, >를 넣어 출력하는 식으로 해결하였다.

코드

N, K = map(int, input().split(" "))

people = []
for i in range(N):
    people.append(i+1)

yosep = []
people_index = -1

while True:
    people_index += K
    people_index = people_index % len(people)
    yosep.append(people.pop(people_index))
    people_index -= 1
    if len(people) == 0:
        break

print("<{}>".format(yosep.__str__()[1:-1]))

네트워크 관련 전공강의를 듣던 중, PC에서 구글 홈페이지가 뜨기까지 네트워크에서 어떤 일이 발생하는가?라는 질문을 제시해 주셨다. 그래서 집 인터넷을 이용하여 구글을 켜기까지 네트워크 속에서 어떤 과정들을 거치는지 필자가 아는 선에서 간단히 정리해 보았다.

1. DHCP 할당
   
   • 우선 집 인터넷에 내 PC를 연결하면, IP를 할당받아야 한다. 이때 DHCP를 이용하여 동적으로 할당받고자 한다.
   • IP를 할당받기 위해, DHCP Discover를 UDP 프로토콜을 이용하여 브로드캐스트로 보낸다.
   • 이후 홈 네트워크 상의 DHCP 서버에서 해당 신호를 확인하고, DHCP Offer를 통해 서버의 주소와 할당받을 수 있는 IP를 PC에 보낸다.
   • PC는 다시 DHCP Request 신호를 통해 IP주소를 요청한다.
   • DHCP 서버는 DHCP Ack 신호를 통해 IP 주소 및 기타 연결 정보를 제공한다.
2. Arp를 통한 라우터 확인
   • IP를 할당받은 PC에서 라우터를 확인하기 위해 Arp Request를 브로드캐스트한다.
   • 이를 확인한 라우터는 해당 PC에게 Arp Reply 신호를 보내 서로 주소를 확인한다.
3. DNS를 통한 구글 웹 서버 확인
   • DNS 서버에 google.com이라는 hostname에 대응하는 IP를 요청하여 구글 웹 서버의 IP를 확인한다.
4. 구글 웹 서버와의 통신
   • 구글 웹 서버와 TCP 연결을 수행한다.
     • 연결을 위해 TCP 3-way-handshake를 수행한다. 우선 내 PC에서 구글 웹 서버로 SYN 신호를 보낸다.
     • 구글 웹 서버는 연결할 준비가 되면 SYN/ACK 신호를 내 PC로 보내준다.
     • 이후 내 PC는 준비가 완료되면 ACK 신호를 보내고, TCP 소켓이 구성된다.
   • 구글 웹 서버와 HTTP 통신을 진행한다.
     • 내 PC에서 구글 웹 서버로 HTTP Request를 보낸다.
     • 구글 웹 서버에서는 해당 Request를 토대로 처리를 수행한 후 내 PC로 Response를 보내 준다.
   • 구글 웹 서버와 TCP 연결을 종료한다.
     • 연결 종료를 위해 TCP 4-way-handshake를 수행한다. 우선 내 PC에서 연결을 닫을 준비를 하고 구글 웹 서버로 FIN 신호를 보낸다.
     • 구글 웹 서버는 신호를 확인하고, ACK 신호를 보낸다. 이후 연결을 닫을 준비가 완료되면 FIN 신호를 보낸다.
     • 내 PC에서 FIN 신호를 받으면, 연결을 닫으며 ACK 신호를 보낸다.
     • 구글 웹 서버에서 ACK 신호를 받으면 최종적으로 연결을 닫으면서 연결이 종료된다.