1.개발 진행 및 완료상황 2주차 python algorithm 틀린 문제 복습 완료 CSAPP 2주차 목표 읽기 업무, 개발 중 발생한 이슈/고민 또는 이를 해결한 내용 백준 2110(파이썬) 2110번: 공유기 설치 2110번 제출 맞힌 사람 숏코딩 재채점 결과 채점 현황 강의 질문 게시판 공유기 설치 다국어 시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율 2 초 128 MB 55494 18901 13282 36.209% 문제 도현이의 집 N개가 수직선 위에 있다. 각각의 집의 좌표는 x 1 , …, x N 이고, 집 여러개가 같은 좌표를 가지는 일은 없다. 도현이는 언제 어디서나 와이파이를 즐기기 위해서 집에 공유기 C개를 설치하려고 한다. 최대한 많은 곳에서 와이파이를 사용하려고 하기 때문에, 한 집에는 공유기를 하나만 설치할 수… ...
이곳에 입소한지 2주가 되었다. 하루가 길고 바쁘다보니 체감으로는 더 오래된 것처럼 느껴진다. 이 기간동안 2번 팀이 바뀌었고, 공부해야 할 주제도 2번 바뀌었다. 시간이 꽤나 느리게 간다는 생각이 든다. 하루 빨리 이곳을 나가야 한다는 생각보단하루라도 더 빨리 성장하고 싶다는 욕심 때문인듯 하다. 보름간 성장을 했다면 했다지만 여전히 배우고 익혀야 할 것은 산더미다. 끝이 있는지, 어디 쯤일지 가늠조차 못하는 주제에 왜이리 조급한지 모르겠다. 그저 더 잘하고자 하는 마음이겠거니 스스로 달랬다. 두번째 에세이를 쓰기 전, 첫 글을 읽어보았다. 다행히 난 여전히 다음날에게 부족했던 모습을 잊지 않고 전해주고 있다. 글을 쓸 때의 다짐을 잊지 않고 하루하루 살아가고 있어서 다행이다. 지금도 난 더 배우고 싶고, 잘하고 싶은 마음이 굴뚝같다. 2주간 초심을 잃지 않았다고 안심하는 꼴이 우스울수도 있지만 보름이 한달이 되고 한달이 석달이 되는 법이니까. ...
자료구조와 시간복잡도에 관한 무작위 정리 큐와 우선순위 큐의 시간복잡도차이 우선순위 큐 구현시 리스트, 힙자료구조 사용 가능 데이터 N개일때, 리스트기반시 최악의 경우 복잡도는 O(N^2), 힙은 O(NlogN) 데이터 갯수가 많아질수록 복잡도는 기하급수적으로 증가. 리스트와 딕셔너리의 차이점 list : 순서 존재, index 존재, mutable, index지정하여 값변경 가능 , 존재확인하는 in연산자는 하나씩 스캔후 반환하여 오래걸린다(성능 낮음) tuple : 순서 존재, index존재, immutable, immutable,같이 저장시 list보다 적은용량(수정 필요없고 간단한형태는 tuple이 좋다) unpacking(튜플의 값 차례대로 변수에 대입 가능 a,b = b, a가 그예임. 하나씩 안넣어도됨) dictionary : key와 value로 구성, 중복불가, 순서x, 크기와 무관하게 in 연산 속도 일정(key값만 찾으니까) set : key값으로만 구성, 중복불가, 순서 X ...
1.개발 진행 및 완료상황 2주차 python algorithm 문제 1회독 완료 이분탐색 백준 문제 복습 완료 업무, 개발 중 발생한 이슈/고민 또는 이를 해결한 내용 코드 구성에 있어서 전체적인 구조가 잘못되기 보다는 세부적으로 틀려 반례가 존재하여 오답처리 되는 경우가 많았다. 반례를 찾는게 꽤 힘들었는데 같은 수의 입력, 최솟값 이나 최댓값 입력 등인 경우가 많았다. 범위 설정 등에서 신경을 많이 썼다. 새로 배운 내용 기존에 list.sort() 를 통해 오름차순으로 정렬하는 방법을 썼다. 하지만 리스트 내 원소가 리스트인 경우, 내부 리스트의 특정 index에 맞춰 정렬한다거나, 내림차순으로 정렬하는 등 세부적인 옵션을 부가하는 방법을 몰랐다. 첫번째 줄은 정렬 후 저장하여 원형이 변형되는 경우, 두번째는 변형되지 않는 경우, 세번째줄은 reverse = True 일경우 내림차순정렬이 된다. 마지막으로 리스트인 원소의 두번째 값으로 오름차순 정렬하는 코드이다. list.sort() sorted(list) list.sort(reverse = True) list.sort(key = lambda x : x[1]) ...
1.개발 진행 및 완료상황 2주차 python algorithm 우선순위 큐 문제풀이중 업무, 개발 중 발생한 이슈/고민 또는 이를 해결한 내용 priority queue 문제를 풀때 heapq를 사용해야 하는지, 기본적인 in-built함수로 구현할 줄 알아야 하는지 궁금했다. 코치님께 질문하였는데, 그 이유를 스스로 생각해보고 찾길 원하셨는지 여러가지 질문들을 하셨다. 시간복잡도, 자료구조, list, stack, queue등을 물어보셨는데 답변을 못하였다. 기초적인 개념들에 대한 이해가 부족하다는 것을 뼈저리게 느꼈다. 이와 관련된 공부들은 3번에 후술하였다. 새로 배운 내용 array 와list, tuple, dictionary, set의 개념과 차이 : ...
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]) ...
1.개발 진행 및 완료상황 2주차 파이썬 알고리즘 공부 스택 문제 1회독 완료 업무, 개발 중 발생한 이슈/고민 또는 이를 해결한 내용 백준 문제 2493번을 파이썬으로 풀었다. 스택과 관련된 문제로 스택(파이썬에선 list지만)을 정방향으로 볼지(왼쪽부터), 반대방향으로 볼지(오른쪽)에 관련된 문제였다. 주목한 원소가 다음 원소와의 크기 비교를 통해 스택에서 pop을 할지 push를 할지 관련된 문제였는데, 경우에 따른 분류가 힘들었다. 위와 같이 정렬한 자료구조를 역순으로 바라보는 문제가 많았는데 정렬을 뒤바꾸는 것과 읽는 방향을 바꾸는 방법이 있었다. 때에 따라 사용하기 위해 둘 다 알아놓아야겠다. 밑의 첫번째는 오름차순 정렬, 두번째는 내림차순 정렬이다. list.sort() list.sort(reverse=True) ...
1.개발 진행 및 완료상황 2주차 파이썬 알고리즘 공부 이분탐색 ,분할정복 개념정리 및 문제 1회독 완료 스택 개념정리 및 난이도 하 문제 1회독 완료 업무, 개발 중 발생한 이슈/고민 또는 이를 해결한 내용 백준 문제들 중 ‘괄호’관련된 문제에서 어려움을 겪었다. 사실 단순히 완성된 괄호인지를 판별하는 문제는 스스로 만든 코드로 완성되었는데, 이 코드를 이후 계산과 연관된 문제에 적용하니 되지 않았다. 코드를 다시 한번 점검해볼 필요성을 느꼈다. 이분탐색 문제는 변수를 설정함에 따라 목표에 달성했는지, 목표를 달성하면서 변수의 최댓값이나 최솟값을 설정하는 문제가 많았다. pl,pr,pc를 index값으로 설정할 것인지 원솟값으로 설정할지 잘 생각해야 한다. ...
1.개발 진행 및 완료상황 1주차 파이썬 알고리즘 시험 종료 2주차 파이썬 알고리즘 시작 업무, 개발 중 발생한 이슈/고민 또는 이를 해결한 내용 날짜와 요일, 각 달의 일 수가 주어지고 입력한 날짜의 요일을 출력하는 프로그램이 문제로 나왔다. 2월이하(2월은 28일까지), 37월(7,8월은 둘다 31일), 812월 로 조건을 나누어서 1월1일부터 몇일 후인지 출력되도록 하였다. 그 후 7로 나눠 나머지에 따라 그에 알맞는 요일이 출력되도록 구성하였다. 접근 자체는 좋았으나 너무 코드가 길어진 듯 하다. 복습하며 코드를 간결하게 쓸 수 있는지 고민해봐야 겠다. ...
1.개발 진행 및 완료상황 1주차 Python Algorithm 문제풀이 완료 업무, 개발 중 발생한 이슈/고민 또는 이를 해결한 내용 Quick sort를 이용하여 주어진 수를 오름차순으로 정렬하고 싶었다. 교과서로 Quick sort가 가장 빠르다고 읽어서, 그냥 가장 좋은 기능이겠거니 생각하였다. 코드도 복잡해지고 잘 안되어서 단순선택 정렬로 했다. 주어진 정수 정렬하여 출력하는 문제에서 메모리가 적게 주어졌다. 다른 문제들처럼 하니 메모리 초과 문제로 오답처리 되었다. 입력되는 수의 개수는 10만개 이상이였지만 주어지는 수의 크기는 1만 이하였기에 분명히 겹칠 가능성이 있을거라 생각했다. 그래서 1만1개짜리 리스트(인덱스와 그 위치가 나타내는 수를 일치시키기 위해서)를 만들어 각 수가 나올때마다 그 수를 인덱스로히는 리스트의 원소를 1씩 늘려준 후 각 인덱스값을 원소만큼 출력하도록 반복함수를 구성하였다. ...