1.개발 진행 및 완료상황

2주차 파이썬 알고리즘 공부
‘큐’ 문제 1회독 완료

업무, 개발 중 발생한 이슈/고민 또는 이를 해결한 내용

백준 18258번 문제(파이썬) : 문제에 나온대로 입력값을 알맞게 처리하고 출력하는 문제였다. 쉽게 코드를 썼지만 시간초과로 오답처리 되었다. ‘pop’이 나올때 해당 queue에서 원솟값을 삭제하도록 만들었는데, 시간 복잡도를 낮추기 위해 냅두고 현재 주목하고 있는 index값을 올려주도록 하였다. 불필요한 과정을 없애는 것 뿐만 아니라 계산을 단순화하는 것도 하나의 방법이 될 수 있다는 것을 알았다. 아래는 정답 코드이다.

import sys n = int(sys.stdin.readline()) read = 0 answer = [] for i in range(n): order = sys.stdin.readline().strip() if order.split()[0] ==’push’: answer.append(int(order.split()[1])) elif order.split()[0] ==’pop’: if len(answer)-read == 0: print(-1) else: print(answer[read]) read += 1 elif order.split()[0] ==’size’: print(len(answer)-read) elif order.split()[0] ==’empty’: if len(answer)-read == 0: print(1) else: print(0) elif order.split()[0] ==’front’: if len(answer)-read ==0: print(-1) else: print(answer[read]) elif order.split()[0] ==’back’: if len(answer)-read ==0: print(-1) else: print(answer[-1])

백준 2164번 문제(파이썬) : 1~n까지 숫자를 규칙적으로 삭제하고 배열을 바꾸는노트에 직접 해보면서 규칙성을 일반화하였다. n이 짝수일때는 2의 배수만 남고, 홀수일때는 맨앞에 n과 그 이후 2의 배수만 남는다. 규칙성에 맞게 반복문을 이용한 코드를 짰으나 시간초과로 오답처리 되었다. 결국 남는 한자리 수 또한 일반화 할수 있음을 발견하여 그에 맞게 코드를 짜니 해결되었다. 시간초과때 발견한 규칙성을 더욱 확장하여 적용시켜봐야겠다. 위는 반복문 코드(시간초과), 아래는 정답 코드다.

import sys n = int(sys.stdin.readline()) def cal_e(x,a): return x == x/2 , a == list(range(1,x+1,2)) def cal_o(x,a): return x == (x-1)/2, a == list(cal_e(x-1,a)) if n == 1: print(1) elif n == 2: print(2) else: arr = [] while n>1: if n%2 == 0: cal_e(n,arr) else: cal_o(n,arr) if n == 1: print(arr)

import sys n = int(sys.stdin.readline()) x=0 if n == 1: print(1) elif n == 2: print(2) else: while 1+2x <= n: x += 1 k = n - (1+2(x-1)) print(2*(k+1))

백준 11866번 문제(파이썬) : 요세푸스 순열 문제였다. stack이나 queue 모두 파이썬에서는 list로 표현되다보니 두 개념의 특성을 이용하는데 어려움을 겪었다. 다른 정답들에서는 library를 통해 deque를 이용하여 풀었는데, 나는 내장함수로만 풀고 싶었다. K를 이용하여 index값을 설정하고 해당 데이터를 pop()한 후 다음 index값을 어떻게 줘야할지 많이 헷갈렸다. 다음 index 값이 +k가 아닌 +(k-1)인 이유는 원소 하나가 pop으로 빠져서 1개만큼 덜 갈 수 있기 때문이다. 그리고 index값이 남은 queue의 길이보다 길다면 index값을 남은 큐의 길이로 나눈 나머지로 변경하고 처음부터 다시 시작했다.(예를 들어, k가 3이고 남은 queue원소가 2개라면 index를 1로 변경한다. 총 3칸 가야 하니 새롭게 앞에서부터는 1칸만 가면 되니까) pop된 원소들은 서로 다른 list에 추가하여 출력되도록 하였다. 예제에서 규칙성을 발견하였지만 일반화하여 프로그램 코드를 만드는데 어려웠다. 아래는 정답코드다.

import sys

n, k = map(int, sys.stdin.readline().split())

queue = [i for i in range(1, n + 1)] temp = [] index = 0 # 제거할 인덱스

while queue: # 제거할 인덱스를 더해서 제거할 인덱스 위치를 바꾼다. index += k - 1

# 인덱스의 크기가 남은 큐의 길이보다 크다면

if index >= len(queue): # 인덱스의 크기를 나눠 나머지로 바꾼다. # 한바퀴 돌았기 때문 index %= len(queue)

# 큐에서 해당 인덱스를 제거하고 제거한 요소를 리스트에 추가한다.

temp.append(str(queue.pop(index)))

sep 함수를 통해 소괄호 공간을 없앤다.

print(“<”, ‘, ‘.join(temp), “>”, sep=””)

백준 3190번 문제(파이썬) : 난이도가 ‘중’이였지만 문제가 워낙 상세하게 나와 큰 힌트를 얻었다. 뱀의 이동 과정을 1. 머리를 옮긴다. 2. 이상이 없다면 꼬리를 당긴다. 2-1. 사과가 있다면 먹어 치우고 꼬리를 당기지 않는다. 로 생각하여 코드를 짜니 쉽게 짤 수 있었다. 다만 나는 x,y 그래프로 생각하여 보드판의 모서리를 (0,0),(n,0),(0,-n),(-n,-n)으로 구성했었는데 문제에서는 행렬로 전제하여 말하다 보니 틀렸었다. 또한 사과를 먹으면 사과가 없어진다는 것을 설정하지 않아 예제는 맞았지만 제출 시 오답처리 되었다. 두 문제를 해결하니 정답이었다. 아래는 정답코드다.

import sys n = int(sys.stdin.readline().strip()) # 보드크기 k = int(sys.stdin.readline().strip()) # 사과 갯수 apple = [] for _ in range(k): apple.append(list(map(int,sys.stdin.readline().rstrip().split()))) # 사과 좌표목록 l = int(sys.stdin.readline()) # 뱡향변화 횟수 move = [] for _ in range(l): #뱡향변화 목록 move.append(list(sys.stdin.readline().split())) snake = [[1,1]] #매초 뱀이 존재하는 좌표 표시 t = 0 # 시간 x_direction = [1,0,-1,0]l # 방향전환시 x,y의 변화값 list 만들어놓기 y_direction = [0,-1,0,1]l x_w = 4(l//2) # 바로 우회전 할수 있으니 0이아니라 중간에 놔야함 y_w = 4(l//2) # 생각해보니 x_w 가 -1이되면 x_direction의 맨뒤를 지칭? x = 1 #시작위치 y = 1 while t >= 0: t += 1 x += x_direction[x_w] y += y_direction[y_w] if snake.count([x,y]) == 1: #머리의 목적지에 뱀의 몸이 있다면 print(t) break elif x < 1 or x > n or y < 1 or y > n: # 머리의 목적지가 보드 밖이라면 print(t) break else: snake.append([x,y]) # 머리 이동 if apple.count([y,x]) == 0: # 머리의 목적지에 사과가 없다면 snake.pop(0) # 꼬리를 당긴다 else: apple.remove([y,x]) # 있다면 꼬리는 당기지 않고 사과만 삭제한다. for i in move: if int(i[0]) == t: # 이 시간에 등록된 방향전환이 있는지 찾는다. if i[1] == ‘L’: #좌회전 x_w += 1 y_w += 1 break elif i[1] == ‘D’: #우회전 x_w -= 1 y_w -= 1 break

새로 배운 내용

index값을 이용하여 list의 원소 지우기 : del 구문을 통하여 특정 위치, 범위를 index값으로 가지는 원소들을 삭제할 수 있었다.

list = [1,2,3,4,5,6,7] del list[3] print(list) [1,2,3,5,6,7] list = [1,2,3,4,5,6,7] del list[0:4:2] print(list) [2,5,6,7]

조건문으로 list가 empty인지 확인하기 : 그동안은 len의 길이가 0이라는 조건을 이용하였는데, 다른 방식도 익혔다. 또한 특정 원소가 있는 지 확인하기 위해 list.count(x) >= 1 을 이용했었는데 새롭게 공부하였다.

list_1 = [] list_2 = [1,2,3] key = 2 if not list_1: print(“list_1 is empty”) if list_2: print(“list_2 is not empty”) if key not in list_1: print(“list_1 doesn’t have key”) if key in list_2: print(“list_2 has key”) list_1 is empty list_2 is not empty list_1 doesn’t have key list_2 has key

list 앞 *의 의미 : list를 print 하면 [a,b,…] 형태로 나오게 되는데 원소만 출력하고 싶다면 list 앞에 *를 붙이면 된다. sep을 이용해 공백이나 중간중간 추가된 문자열도 출력 시킬수 있다. print 내에서만 사용하고, 연속으로 출력된 원소들을 다른 변수로 지정하고 싶다면 아래의 join을 이용해야 한것 같다.

list = [1,2,3,4,5] print(list) print(list) print(list, sep = ‘’) [1, 2, 3, 4, 5] 1 2 3 4 5 12345

join 함수 : 리스트 내의 원소들을 합쳐서 하나의 문자열로 바꾸어 반환하여 준다. ‘구분자’.join(리스트)의 형태로 쓸 수 있다. print와 함께 쓰기도 하고, 여러자리 숫자에서 각 자리의 수를 이용하는 문제에서도 사용할 수 있었다. 구분자 자리를 비우면 공백없이 연속해서 출력한다. list내 원소들이 str 형태가 아니면 오류가 발생한다. 또한 str형태로 숫자를 넣어서 결과가 나오더라도 str이다.

list_1 = [‘1’,’2’,’3’] list_2 = [‘a’,’b’,’c’] result_1 = ‘‘.join(list_1) result_2 = ‘틈새라면’.join(list_2) print(result_1) print(result_2) if result_1 == 123: print(‘Same’) else: print(‘different’) 123 a틈새라면b틈새라면c different

참고할 만한 레퍼런스들

자료구조와 함께 배우는 알고리즘 입문 파이썬편(BohYoh Shibata 지음, 강민 옮김, 이지스 퍼블리싱)
https://www.lainyzine.com/ko/article/how-to-delete-elements-of-a-list-in-python/
https://codechacha.com/ko/python-check-empty-list/
https://blockdmask.tistory.com/468
특이사항
회고
토요일 저녁~ 일요일 오후 까지 쉬었지만 혹여나 월요일 다시 몰입된 환경으로 돌아오는 것이 더뎌질까 싶어 저녁부터 공부를 시작했다.
각 문제별로 헷갈렸거나 어려운 부분에 대해 주석을 쓰고 공부하면서 알게 된 내용과 링크를 따로 기록해두니 기록일지가 더 의미있어 보인다. 내가 하루 했던 고민과 생각, 그 결과를 기록하는 것이니 빠짐없이 성실하게 기록해야 겠다.
CSAPP 좀 읽자. (제발좀)
TO-DO-LIST

우선순위 큐 문제풀이
CSAPP 읽기

파이썬 알고리즘 2주차 : 큐 2, 카드2, 요세푸스 문제 0, 뱀

정글일지 8

sep 함수를 통해 소괄호 공간을 없앤다.

CATALOG