https://www.acmicpc.net/problem/15828

문제

인터넷을 사용하기 위해서는 컴퓨터에 인터넷 회선을 연결하거나 Wi-Fi를 연결해야 한다. 이렇게 연결된 네트워크를 통해 컴퓨터에는 통신이 가능하다. 마음에 드는 노래나 동영상이 있는 곳에 파일을 전송해달라는 요청을 보내고 파일을 받는 식으로 말이다.

우리가 보낸 요청은 어떻게 목적지까지 도달하는 것일까? 컴퓨터에서는 패킷이라고 하는 형태로 정보를 주고 받는다. 네트워크의 유저들은 1:1로 연결되어 있지 않으므로, 일반적으로 패킷은 라우터라는 장비를 여러 번 거친다. 그러면 라우터에서는 패킷을 다른 라우터로 보내거나, 만약 목적지와 직접적으로 연결되어 있다면 그곳으로 보낼 수도 있다. 즉, 택배 회사의 물류 센터와 비슷한 역할을 한다고 보면 된다.

그림1. 네트워크에 존재하는 라우터들의 구성 예시

라우터 내부를 들여다보면 처리해야 할 패킷을 임시적으로 보관하기 위한 버퍼가 존재한다. 이 버퍼에는 라우터에 입력으로 들어온 패킷들이 순서대로 위치하고, 라우터에서는 먼저 온 패킷부터 하나씩 처리한 후 버퍼에서 제거한다. 만약 라우터가 패킷을 처리하는 속도보다 패킷이 들어오는 속도가 더 빠를경우 버퍼가 꽉 차거나 넘쳐버릴 것이다. 그렇게 되면 버퍼에 공간이 생길 때까지 입력받는 패킷은 모두 버려진다.

통신의 원리를 배웠으니까 간단하게 라우터의 작동 원리를 구현해보자. 물론 하나의 라우터만 존재한다고 가정하며, 우리가 다룰 부분은 라우터의 입출력이 주어졌을 때 버퍼의 상태가 어떻게 변하는가이다. 그러니까 라우터가 패킷을 구체적으로 어떤 방식으로 처리하고, 어디로 보내고 이런 것들은 생각하지 말자.

풀이방법

사용한 알고리즘 : 큐

1. 버퍼의 사이즈를 입력을 받습니다.

2. -1을 입력받을 때까지 실행합니다.

3. 0과 -1을 제외한 입력은 버퍼에 추가를 합니다.

4. 버퍼의 크기가 N과 같은 경우 넘어갑니다.

5. 0을 입력받은 경우 버퍼에서 하나를 제거합니다.

6. -1을 입력받은 경우 while문을 탈출합니다

7. 버퍼가 비었다면 empty, 비어있지 않다면 버퍼 내부를 출력합니다.

코드

# silver 4
# 15828번, Router

import collections
import sys

input = sys.stdin.readline
deq = collections.deque()

# Queue size 입력
N = int(input())

while True:
    temp = int(input())
    if temp == -1:
        break
    elif temp == 0:
        deq.popleft()
    else:
        if len(deq) < N:
            deq.append(temp)
        else:
            continue

#출력부
if len(deq) == 0:
    print("empty")
else:
    for i in deq:
        print(i, "", end="")

결론

큐를 사용하니까 너무 간단했다.

다행히 학교 전공으로 Router에 대해 배워서 빠르게 이해할 수 있었다. 

상당히 간단한 문제다.

https://www.acmicpc.net/problem/2164

문제

N장의 카드가 있다. 각각의 카드는 차례로 1부터 N까지의 번호가 붙어 있으며, 1번 카드가 제일 위에, N번 카드가 제일 아래인 상태로 순서대로 카드가 놓여 있다.

이제 다음과 같은 동작을 카드가 한 장 남을 때까지 반복하게 된다. 우선, 제일 위에 있는 카드를 바닥에 버린다. 그 다음, 제일 위에 있는 카드를 제일 아래에 있는 카드 밑으로 옮긴다.

예를 들어 N=4인 경우를 생각해 보자. 카드는 제일 위에서부터 1234 의 순서로 놓여있다. 1을 버리면 234가 남는다. 여기서 2를 제일 아래로 옮기면 342가 된다. 3을 버리면 42가 되고, 4를 밑으로 옮기면 24가 된다. 마지막으로 2를 버리고 나면, 남는 카드는 4가 된다.

N이 주어졌을 때, 제일 마지막에 남게 되는 카드를 구하는 프로그램을 작성하시오.

풀이방법

사용한 알고리즘 : 큐 

큐를 사용한 이유는 카드를 빼고나서 뒤에 넣는 과정을 반복한다. 즉, 선입선출(FIFO, First Input First Output) 방식을 사용한다는 것을 통해서 큐를 사용했다.

과정은 이러하다

1. queue에 입력받은 숫자만큼 카드를 넣는다.

2. 큐의 사이즈가 1이 된다면 큐의 남은 숫자를 출력한다.

3. 큐의 사이즈가 1이 아니면 맨 앞의 숫자를 제거한다.

4. 맨 앞의 숫자를 제거 후 맨 뒤에 추가한다.

5. 2의 과정으로 돌아간다.

생각보다 간단한 문제이다.

코드

# silver 4
# 2164번, 카드2

from collections import deque

que = deque()

N = int(input())

# queue에 카드 넣기
for i in range(1,N+1):
    que.append(i)

# queue size 가 1 될 때까지 카드를 버리고 옮기기 반복

while len(que) != 1:
    que.popleft()
    que.append(que.popleft())

print(que[0])

결론

큐를 알고있다면 상당히 간단히 풀리는 문제이다.

https://www.acmicpc.net/problem/10845

문제

정수를 저장하는 큐를 구현한 다음, 입력으로 주어지는 명령을 처리하는 프로그램을 작성하시오.

명령은 총 여섯 가지이다.

• push X: 정수 X를 큐에 넣는 연산이다.
• pop: 큐에서 가장 앞에 있는 정수를 빼고, 그 수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다.
• size: 큐에 들어있는 정수의 개수를 출력한다.
• empty: 큐가 비어있으면 1, 아니면 0을 출력한다.
• front: 큐의 가장 앞에 있는 정수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다.
• back: 큐의 가장 뒤에 있는 정수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다.

입력

첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 않은 명령이 주어지는 경우는 없다.

출력

출력해야하는 명령이 주어질 때마다, 한 줄에 하나씩 출력한다.

풀이과정

총 3가지의 방법을 사용하면서 1번째는 실패한 것, 2번째와 3번째는 성공한 방법이다.

 1번째는 제목을 보자마자 Queue 클래스를 생각해서 봐로 구현을 해봤다. 하지만 index에서 오류가 발생했다. len을 사용해보기도 하고 queue.qsize()를 사용해봤지만 index자체에 접근을 할 수 없다고 한다. queue클래스는 index사용을 하지 않을 때 사용할 것을 알았다.

2번째는 list를 사용했다. list에서 추가와 삭제를 할 수 있는 method가 insert, append, pop 정도가 있다. 

append와 pop은 모두 list원소의 마지막만을 수정하는 method이다. 그래서 FIFO인 큐를 구현하기 위해서 insert를 사용한다.

첫번째 원소에 insert method를 사용해 삽입하고 제거할 때 pop method를 사용해서 큐를 구현했다.

3번째 collections.deque 를 사용해서 구현했다. deque는 list와 다르게 popleft, pop, appendleft, append 형식으로 왼쪽과 오른쪽을 method를 사용해 가독성이 좋게 구현할 수 있다. 이것을 통해서 2번째 방법보다 쉽고 가독성있게 구현했다.

2번째와 3번째 모두 왼쪽은 back, 오른쪽은 front이다.

코드

1번째  큐 클래스 사용

# silver 4
# 10845번, 큐

import queue, sys
N = int(input())
que = queue.Queue()

for i in range(N):
    # 명령어 입력
    cmd = sys.stdin.readline().rstrip().split()
    if cmd[0] == 'push':
        que.put(cmd[1])
    elif cmd[0] == 'pop':
        if not que.empty():
            print(que.get())
        else:
            print(-1)
    elif cmd[0] == 'size':
        print(que.qsize())
    elif cmd[0] == 'empty':
        if que.empty():
            print(1)
        else:
            print(0)
    elif cmd[0] == 'front':
        if que.empty():
            print(-1)
        else:
            # 인덱스 오류 발생
            print(que[len(que)-1])
    elif cmd[0] == 'back':
        if que.empty():
            print(-1)
        else:
            # 인덱스 오류 발생
            print(que[0])

큐 클래스는 index를 지원하지 않기 때문에 오류가 발생한다. 

2번째 list 사용

# silver 4
# 10845번, 큐
# list 사용

import sys

N = int(input())
que = list()

for i in range(N):
    # 명령어 입력
    cmd = sys.stdin.readline().rstrip().split()
    # 왼쪽이 뒤, 오른쪽이 앞
    if cmd[0] == 'push':
        que.insert(0, cmd[1])
    elif cmd[0] == 'pop':
        if len(que) == 0:
            print(-1)
        else:
            print(que.pop())
    elif cmd[0] == 'size':
        print(len(que))
    elif cmd[0] == 'empty':
        if len(que) == 0:
            print(1)
        else:
            print(0)
    elif cmd[0] == 'front':
        if len(que) == 0:
            print(-1)
        else:
            print(que[-1])
    elif cmd[0] == 'back':
        if len(que) == 0:
            print(-1)
        else:
            print(que[0])

3번째 collections.deque 사용

# silver 4
# 10845번, 큐
# collections.deque 사용

import sys, collections

N = int(input())
que = collections.deque()

for i in range(N):
    # 명령어 입력
    cmd = sys.stdin.readline().rstrip().split()
    # 왼쪽이 뒤, 오른쪽이 앞
    if cmd[0] == 'push':
        que.appendleft(cmd[1])
    elif cmd[0] == 'pop':
        if len(que) == 0:
            print(-1)
        else:
            print(que.pop())
    elif cmd[0] == 'size':
        print(len(que))
    elif cmd[0] == 'empty':
        if len(que) == 0:
            print(1)
        else:
            print(0)
    elif cmd[0] == 'front':
        if len(que) == 0:
            print(-1)
        else:
            print(que[-1])
    elif cmd[0] == 'back':
        if len(que) == 0:
            print(-1)
        else:
            print(que[0])

결론

성능차이는 크게 없는 것 같지만 가독성이 좋은 collections.deque를 사용해야겠다.

참고로 시간복잡도는 2번째 O(n) 3번째 O(1)이라고는 하는데 큰 차이를 모르겠다..

마지막 글 쓴게 2020년 11월이네요 

저 때 진짜 열심히 살려고 했었는데 막상 2주도 안되서 블로그 접은 거 보면 의지박약이네

그리고 네.. 뭐.. 입대했습니다. 맘 같아선 그냥 사진 올려버리고 싶은데(대충 빡빡이인 사진) 다들 눈은 소중하니까 생략하겠습니다.

그리고 군대에서 갓생살려고 블로그 작성할려고 또 맘을 먹었었네요

이렇게 맘먹고 하나도 안썼습니다. 왜냐면 바빴거든요 ㅋ 일병주제에 군생활 적응해야지 뭘 할 수 있겠나요....

어찌어찌 군생활이 끝나고 나서 정말 뭔가 많이 할 줄 알았는데 그냥 열심히 놀았습니다. 정말 최선을 다해서 놀았습니다.

등등등 그래도 동해 빼고는 다 놀러갔다 온 거 같아요 

또 자취도 했었는데 진짜 안 비싸면 또 하고 싶네요ㅠㅠㅠㅠㅠ

정말 예뻤는데... 역시 사람은 고층에 살아야해.. 야경이 진짜 최고입니다 다들 고층사세요 그러면 항상 눈이 호강합니다. 진짜 송도는 야경 원툴이지만 그거 하나는 최고입니다. 다들 놀러오세요 송도 진짜 좋아요(걸어다니는 거는 진짜 최고에요) 

그런데 말이에요
제 자취방을 지들 요리하는 곳으로 쓰는 나쁜 사람들이 있네요

2022년 어쩌다 MT도 갔습니다 늙은이들 끼리 모여서 라떼 얘기 중이였을 겁니다..

아무것도 모르는 그냥 감자가 어쩌다보니 해커톤도 나갔습니다

가서 그냥 놀다가 왔습니다. 코딩하는 사람은 따로 있었고 전 그냥 감자역할을 했습니다. 

그리고 나서 드디어 복학을 했습니다. 진짜 3년만에 제대로 학교 다니네요 근데 뭐 사진은 없고 그냥 학식만 열심히 먹었습니다. 

그리고 대망의 화요일입니다. 이날 17명 예약했는데 어쩌다보니 3학년만 20명이서 먹게 되었네요 

복학하니까 별별 사람이 다 있네요

과제하다가 빡친 모습도 보이고 과제하다가 포기해서 자고 과제를 모르는 사람들도 있고 정말 혼란스럽네요

 술도 조금만 먹고 놀았습니다. 공부 안했습니다.

그리고 한강도 가고 야구장도 가고

잠실, 여의도, 고척, 문학 진짜 재밌었습니다. 근데 왜 항상 야구는 지는지... 그래도 뭐 즐거우면 된거지

야구는 하이라이트로만 보세요 정신건강에 상당히 해롭습니다..(물론 한화 야구가)

중간중간 운동도 했습니다. 나보다 달리기 빠른 이XX, 조XX 때문에 진짜 힘들었는데 진짜 개 빠른 사람들

혼돈의 카오스인 기말고사 기간  밤새고 -> 아침먹고 -> 자고 -> 저녁에 일어나서 공부하고 밤새고 -> 아침먹고 -> 자고

이렇게 한학기를 열심히 놀았더니 첫 성적부터 바로 씨를 뿌려버리네요 아이고... 교수님... 

죄송합니다... 재수강할 수 있으면 해볼게요... 교수님...

그래도 시험보느라 고생한 동기들끼리 바다보고 왔습니다

(학교 바로 앞이 바다인데 또 바다를 보러갔네)

마지막으로 제 종강 후 계획입니다.

split 함수

문자열을 '특정 문자'를 기준으로  리스트로 바꾸는 함수이다.

string -> list

S="Python javaScript"

# 리스트로 나눌려고 하는 문자열을 입력한다.
# split함수를 쓰고 나누려는 문자열을 입력한다.
# 공백인 경우는 ' '를 기준으로 나눈다.

print(S.split())
# 출력결과
# ['java', 'javaScript']

print(S.split('a'))
# 출력결과
# ['Python j', 'v', 'Script']

# 만약 원소 하나씩 리스트에 넣으려고 한다면 list 함수

print(list(S))
# 출력결과
# ['P', 'y', 't', 'h', 'o', 'n', ' ', 'j', 'a', 'v', 'a', 'S', 'c', 'r', 'i', 'p', 't']

join 함수

리스트를 문자열로 바꿔주는 함수이다.

'특정 문자'를 리스트 사이에 넣어서 문자열로 바꿔준다.

list->string

S= ['python','c++','c','java','javascript']
# 리스트를 사이에 넣을 특정 문자를 입력한다.
# join 함수를 적는다.
# 문자열로 변환할 리스트를 적는다.

print("".join(S))
# 출력결과
# pythonc++cjavajavascript

print(",".join(S))
# 출력결과
# python,c++,c,java,javascript

최대공약수(Greatest Common Divisor)

두 수 x와 y가 주어졌을 때 두 수의 공통인 약수 중에서 가장 큰 약수를 최대공약수라고 한다. 최대공약수를 구하는 방법 중에서 하나인 유클리드 호제법을 사용해서 구할 것이다. 

파이썬 코드

def gcd(x,y): 		# 1번
    while(True):	
        if(y==0): break # 2번
        x,y=y,x%y	# 3번,4번
    return x

print(gcd(30,16))

# 출력결과
# 2

파이썬 내장함수를 이용한 방법

from math import gcd

print(gcd(30,16))

# 출력결과
# 2

1.reverse()

리스트의 원소들의 순서를 역순으로 바꿔줍니다.

a=[1,2,3,4,5]
a.reverse()
print(a)

# 출력결과
# [5,4,3,2,1] 

2.reversed()

리스트의 원소들을 역순으로 바꿔준 값을 반환합니다.

reverse 함수와는 다릅니다. 리스트의 값들을 역순으로 바꿔줍니다.

reversed 함수는 쉽게 말해 a의 리스트의 값을 뒤에서부터 하나하나 출력해주기만 하는 역할을 한다고 생각하시면 됩니다.

a=[1,2,3,4,5]

list(reversed(a))
print(a)
# 출력결과
# [1, 2, 3, 4, 5]

print(list(reversed(a)))
# 출력결과
# [5, 4, 3, 2, 1]

print(a)
# 출력결과
# [1, 2, 3, 4, 5]