MancityBallboy 흔적 남기기

(백준) 평범한 배낭

30 Nov 2020

문제

이 문제는 아주 평범한 배낭에 관한 문제이다.

한 달 후면 국가의 부름을 받게 되는 준서는 여행을 가려고 한다. 세상과의 단절을 슬퍼하며 최대한 즐기기 위한 여행이기 때문에, 가지고 다닐 배낭 또한 최대한 가치 있게 싸려고 한다.

준서가 여행에 필요하다고 생각하는 N개의 물건이 있다. 각 물건은 무게 W와 가치 V를 가지는데, 해당 물건을 배낭에 넣어서 가면 준서가 V만큼 즐길 수 있다. 아직 행군을 해본 적이 없는 준서는 최대 K무게까지의 배낭만 들고 다닐 수 있다. 준서가 최대한 즐거운 여행을 하기 위해 배낭에 넣을 수 있는 물건들의 가치의 최댓값을 알려주자.

예제 입력

4 7
6 13
4 8
3 6
5 12

정답 : 14

Solution

import sys
input = sys.stdin.readline

N, K = list(map(int, input().split()))
dp = [0] * (K + 1)  ## 각 무게에 따른 최대 value 값 저장하는 배열
items = [list(map(int, input().split())) for _ in range(N)]
visit = [0] * (K + 1)  ## 사용할 수 있는 무게를 체크 하기 위한 배열 똑같은 무게가 여러번 쓰이는 것을 방지 하기 위함
visit[0] = 1
items.sort()

for weight, value in items:
    for idx in range(K, -1, -1):
        if weight + idx > K or visit[idx] == 0:
            continue
        visit[weight + idx] = 1
        if value + dp[idx] > dp[weight + idx]:
            dp[weight + idx] = value + dp[idx]

print(max(dp))
  1. 배낭에 넣을 수 있는 제품을 무게가 작은 순대로 정렬한다.
  2. 한 제품을 넣을 때는 dp리스트에서 무게가 높은 순서로 체크해서 넣는다.
    • 작은 무게 부터 더 해버리면 같은 무게가 여러번 들어가는 현상이 생길 수 있다.
  3. 작은 무게 부터 배낭에 넣으면서 dp리스트에 같은 무게 일때 높은 value를 저장한다.
  4. 그리고 dp리스트에서 가장 큰 값을 프린트 하면 된다!!

(프로그래머스)풍선 퍼뜨리기

26 Nov 2020
문제 설명

일렬로 나열된 n개의 풍선이 있습니다. 모든 풍선에는 서로 다른 숫자가 써져 있습니다. 당신은 다음 과정을 반복하면서 풍선들을 단 1개만 남을 때까지 계속 터트리려고 합니다.

  1. 임의의 인접한 두 풍선을 고른 뒤, 두 풍선 중 하나를 터트립니다.
  2. 터진 풍선으로 인해 풍선들 사이에 빈 공간이 생겼다면, 빈 공간이 없도록 풍선들을 중앙으로 밀착시킵니다.

여기서 조건이 있습니다. 인접한 두 풍선 중에서 번호가 더 작은 풍선을 터트리는 행위는 최대 1번만 할 수 있습니다. 즉, 어떤 시점에서 인접한 두 풍선 중 번호가 더 작은 풍선을 터트렸다면, 그 이후에는 인접한 두 풍선을 고른 뒤 번호가 더 큰 풍선만을 터트릴 수 있습니다.

당신은 어떤 풍선이 최후까지 남을 수 있는지 알아보고 싶습니다. 위에 서술된 조건대로 풍선을 터트리다 보면, 어떤 풍선은 최후까지 남을 수도 있지만, 어떤 풍선은 무슨 수를 쓰더라도 마지막까지 남기는 것이 불가능할 수도 있습니다.

일렬로 나열된 풍선들의 번호가 담긴 배열 a가 주어집니다. 위에 서술된 규칙대로 풍선들을 1개만 남을 때까지 터트렸을 때 최후까지 남기는 것이 가능한 풍선들의 개수를 return 하도록 solution 함수를 완성해주세요.

제한 사항
  • a의 길이는 1 이상 1,000,000 이하입니다.
    • a[i]는 i+1 번째 풍선에 써진 숫자를 의미합니다.
    • a의 모든 수는 -1,000,000,000 이상 1,000,000,000 이하인 정수입니다.
    • a의 모든 수는 서로 다릅니다.
def find_min_num(start, end, a, check_min_num, direction):
    start_num = a[start]
    for idx in range(start, end, direction):
        if start_num < a[idx]:
            check_min_num[idx] += 1
        else:
            start_num = a[idx]
    return check_min_num


def solution(a):
    answer = 0
    if len(a) < 3:
        return len(a)
    else:
        answer += 2
        check_min_num = [0] * len(a)
        check_min_num = find_min_num(0, len(a) - 1, a, check_min_num, 1)
        check_min_num = find_min_num(len(a) - 1, 0, a, check_min_num, -1)
        for idx in range(1, len(a) - 1):
            if check_min_num[idx] < 2:
                answer += 1
    return answer

이 문제의 핵심은 각각의 풍선 좌, 우에 존재하는 풍선들의 최솟값을 구했을때 좌, 우에 존재하는 최솟값이 모두 대상 풍선보다 작을 때만 그 풍선은 마지막에 남을 수 없다는 것이다. 즉 한쪽의 최솟값만 대상 풍선보다 크더라도 그 풍선은 끝까지 남는게 가능하다는 말이다.

핵심을 깨달은 후에는 시간이 초과되지 않게 문제를 풀기만 하면된다.

(독후감) 비전공자를 위한 이해할 수 있는 IT지식

26 Nov 2020

스스로 CS가 부족함을 느끼고 CS 공부를 해야겠다는 생각을 굉장히 많이 했다. 하지만 어떻게 공부를 해야할지에 대해 감이 전혀 오지 않아서 무엇부터 시작해야 하는지에 대한 고민을 하다가 이 책을 접하고 이 책은 나를 위한 책이 겠구나 하고 구매해서 읽어 보았다.

이 책에 대해서 간단한 소감을 얘기하자면 나에게는 너무나도 쉬운 책이었다. 책의 제목에서 알 수 있듯이 비전공자를 위한 책이지만 IT지식을 가르쳐 주긴 하지만 IT 지식 즉 CS를 직접적으로 100% 이해하고 사용해야하는 개발자보다는 개발자 곁에서 함께 일하는 비 개발자이자 비 전공자들을 위한 책이다. 개발자들과 IT 용어로 소통을 해야하지만 IT 지식을 잘 알지 못해 소통을 하지 못하는 사람들에게 큰 도움이 될 것이라고 생각한다.

비록 나에게는 큰 도움이 되지 않았지만 도움이 아예 안된 것은 아니다. 나 스스로도 sw 개발 공부를 시작한지 1년이 되었지만 전반적인 CS지식은 매우 부족하다. 하지만 이 책을 읽으면서 CS 지식들이 어떻게 이용되며 왜 알아야 하는지에 대해 틀이 잡혔다고 생각한다. 그리고 이 책은 대부분의 원리를 실 예를 통해서 설명을 하다보니 잘 모르는 사람도 쉽게 이해할 수 있게 구성 되어있다. 나는 이 책은 개발자가 되고 싶은 비전공자들이 개발을 배우기 시작할 때 읽으면 좋을 것이라고 생각한다. 기본을 알고 시작하는 것과 모르고 시작하는 것은 엄청난 차이가 있고 실력이 상승하는 속도도 다르다고 생각한다.

Python을 이용한 로컬 채팅 서버 만들기

25 Nov 2020

오늘은 모 회사 면접에서 멀티 스레드에 대한 질문이 들어왔지만 운도 떼지 못한게 너무 아쉬워서 멀티 스레드를 이용한 채팅 서버를 만들어 보겠습니다.

우선 채팅 서버를 만들기 위해서는 소켓과 스레드라는 개념이 필요합니다.

소켓과 스레드에 대해서 간단히 알아만 보고 가겠습니다.

소켓

네트워크 상에서 클라이언트와 서버가 서로 통신을 가능하게 해주는 장치 이다.

스레드

프로세스 행위의 단위로써 2가지 이상의 스레드를 이용하는것을 멀티 스레드라 합니다.

server.py

from socket import *
import threading

port = 10000

server_socket = socket(AF_INET, SOCK_STREAM) ## 소켓을 정의합니다.
server_socket.bind(('', port))               ## 서버가 정해진 포트번호로 지정된 소켓을 생성합니다.
server_socket.listen(5)                      ## 최대로 들어올 수 있는 소켓 갯수를 지정합니다.

user_list = {}                               ## 채팅 유저관리를 위한 딕셔너리입니다.
def receive(client_socket, addr, user):
    while 1:                                 
        data = client_socket.recv(1024)      ## 클라이언트 소켓에서 데이터를 받아 옵니다.
        string = data.decode()               ## 받아온 데이터는 비트로 인코딩 되있기 때문에 디코딩을 해줍니다. 

        if string == "/종료" :                           
            msg = f'{user.decode()}가 퇴장하였습니다.'
            for con in user_list.values():                    
              try:
                  con.sendall(msg.encode())
              except:
                  print("연결이 비 정상적으로 종료된 소켓 발견")
            print(msg)
            break
        string = "%s : %s"%(user.decode(), string)
        print(string)
        for con in user_list.values():                    ## 채팅에 참여하고 있는 클라이언트들에게 받아온 메시지 전달
            try:
                con.sendall(string.encode())            
            except:
                print("연결이 비 정상적으로 종료된 소켓 발견")
    del user_list[user]                                   ## 채팅서버를 나간 클라이언트는 딕셔너리에서 제거
    client_socket.close()                                 ## 클라이언트 소켓 제거

while True:
    client_socket, addr = server_socket.accept()          ## 클라이언트 소켓 정의
    user = client_socket.recv(1024)                       ## 처음 클라이언트 소켓이 정의되고 난 후 처음 받는 데이터
                                                          ## 클라이언트는 채팅 유저의 이름을 보냅니다.
    user_list[user] = client_socket                       ## 유저 리스트에 유저 추가
    print(f'{user.decode()}가 입장하였습니다.')          

    receive_thread = threading.Thread(target=receive, args=(client_socket, addr,user))
    ## 각각의 클라이언트 서버가 채팅을 따로 치기 위해 각 클라이언트로 부터 데이터를 받고 보내는 부분은 스레드로 정의해줍니다.
    receive_thread.start()

Client.py

from socket import *
import argparse
import threading

client_socket = socket(AF_INET, SOCK_STREAM)  
client_socket.connect(('127.0.0.1', 10000))    ## 로컬에서 진행하기 때문에 로컬 주소와 지정된 포트번호로 소켓 생성

parser = argparse.ArgumentParser()             ## 파서를 통해 클라이언트의 이름을 지정할 수 있도록 정의
parser.add_argument('user')
args = parser.parse_args()
user = args.user

print(f'{user} 접속 완료')

def handle_receive(client_socket, user):       ## 서버로 부터 데이터를 받는 함수
    while 1:
        try:
            data = client_socket.recv(1024)    ## 서버로 부터 데이터가 온다면 데이터를 프린트하고 오지 않는 다면 
                                               ## 서버로부터 연결이 끊겼음을 프린트
        except:
            print("연결 끊김")
            break
        data = data.decode()
        if not user in data:
            print(data)

def handle_send(client_socket, user):          ## 서버로 데이터를 전달
    while 1:
        data = input()
        client_socket.sendall(data.encode())
        if data == "/종료":
            break
    client_socket.close()


receive_thread = threading.Thread(target=handle_receive, args=(client_socket, user,))
receive_thread.start()
send_thread = threading.Thread(target=handle_send, args=(client_socket, user))
send_thread.start()
## 데이터를 보내는 것과 받는 것을 멀티 스레드로 지정하여서 서로 각 각 동작할 수 있도록 합니다.

client_socket.sendall(user.encode()) ## 클라이언트 소켓이 정의 된 후 보내는 첫 데이터 유저의 이름을 보냅니다.

멀티스레드가 필요한 이유

클라이언트에서 데이터를 보내는 것과 받는 것을 멀티 스레드로 지정하지 않는다면 내가 채팅을 한 번 친다면 무조건 한 번 받은 후에 다시 쳐야한다. 그렇게 된다면 진정한 의미의 채팅이라고 할 수 없다.

채팅을 보내는 것과 받는 것을 멀티 스레드로 지정함으로써 자유롭게 이야기를 나눌 수 있게 된 것이다.

채팅 서버 시연

채팅서버시연

맨 왼쪽이 서버이고 오른쪽 3개가 각 각의 클라이언트 입니다.

참고사이트

https://sungmin-joo.tistory.com/60

https://sungmin-joo.tistory.com/61?category=863420

CodingTest에 도움 될수 있는 Python 토막 지식

22 Nov 2020

Python을 이용한 Coding Test에 도움이 될 수 있는 몇 가지

제가 경험한 바에 의하면 python 코딩 테스트는 아무래도 구현보다는 최적화에서 많은 사람들이 어려움을 겪는 것 같습니다.

코드를 어떤식으로 빠르게 바꿀 수 있는가에 대한 방법은 2가지 정도 인것 같습니다.

  1. 문제에 알맞은 알고리즘을 이용한다.
    • 문제에 알맞는 알고리즘을 이미 알고 있다면 아마 굉장히 빠르게 해결 할 수 있습니다.
  2. 알려진 보다 빠른 방법을 숙지하고 이용한다.
    • 이 부분은 사실 좀 과대평가 되었다고 볼 수 도 있습니다. 왜냐하면 대부분 1번에서 해결이 될 수 있는 문제이기 때문입니다.
    • 그저 알려지지 않은 알고리즘이나 빡빡한 시간제한 때문에 고통받는 사람에게 도움이 되고 싶은 마음입니다.

일단 이번 포스팅은 2번에만 국한 되어 있는 포스팅입니다. 적지 않은 문제를 풀어오면서 저에게 문제를 푸는데 많은 도움을 준 방법들을 이야기 해 보겟습니다.

  1. 문자열을 concat할 때는 string에서 +를 이용해 직접 합치기 보다는 list에 append하여서 ''.join()으로 출력하는 것이 빠릅니다.

  2. 조합이나 순열문제가 나올 때는 재귀 보다는 import itertools를 적극적으로 이용하자.

    • 단 재귀를 이용해 풀 수 있는 사람만 이 방식을 추천드립니다.
    • 재귀가 익숙하지 않은 사람은 재귀를 이용해서 푸는 방법부터 충분히 익힌 후에 이용하시기를 추천드립니다.

  3. input()을 이용해 굉장히 많은 값을 입력받아야하는 경우

    import sys
input = sys.stdin.readline
   
N = int(input())
array = [int(input()) for _ range(N)]

    sys.stdin.readline을 이용하여 입력 받도록 합시다. 그냥 raw_input()으로 받는거보다 상당히 향상된 속도를 보장합니다.

  4. 정렬된 배열에서 어떤한 값을 찾을 때는 이진탐색을 이용하는 것이 좋습니다.

    • 사실 문제를 풀다보면 값을 찾는 문제가 굉장히 많습니다.
    • 이진탐색이 생각보다 이용할 수 있는 부분에 굉장히 많습니다.

시간 초과가 아닌 오류에 대응할 수 있는 방법

많이 겪어보지 못한 경우이므로 많은 해결 방안이 존재 하진 않습니다.

  1. 재귀를 이용하여 문제를 풀 경우 재귀 깊이가 충분하지 않아 생기는 RecursionError

    import sys
sys.setrecursionlimit(10^8)

    이와 같은 경우처럼 재귀의 깊이를 충분하게 조절 할 수 있습니다.

    하지만 이것이 무조건적인 해결 방안이 될 순 없습니다. 단순히 재귀 깊이를 깊게 조절 하는 것 뿐이지만 본인이 잘못 설계한 재귀에서 생기는 RecursionError는 해결 할 수 없습니다.

  2. 그래프를 이용한 문제를 풀 경우 생기는 메모리 초과 에러

    '''
input
10 8
1 2
3 4
2 3
4 5
6 7
8 9
9 10
1 10
'''
N, E = list(map(int, input().split()))
graph = [[0] * (N + 1) for _ in range(N + 1)]
for _ range(E):
    a, b = list(map(int, input().split()))
    graph[a][b] = 1
    graph[b][a] = 1                           ## 행렬을 이용한 그래프 저장 방법
       
graph = [[] for _ in range(N + 1)]
for _ range(E):
    a, b = list(map(int, input().split()))
    graph[a].append(b)
    graph[b].append(a)                        ## 인접 리스트로 저장

    무방향 그래프를 저장하는 방법은 대표적으로 행렬을 이용한 방법 인접리스트를 이용한 방법이 있습니다.

    행렬을 이용했을때 메모리초과에러가 날 경우 인접리스트를 이용해 구현 한다면 에러를 피할 수 있었습니다.

사실 이런 글을 써도 될지 모르겠을 정도로 많이 부족하다고 생각합니다. 저의 개인적인 경험으로 엮어 낸 것이다 보니 정확하지 않을 수 있다는 점 고려 부탁 드립니다. 더 나은 방법이나 바뀐 정보가 있다면 업데이트 하도록 하겠습니다.