Redddy's Devlog

a = [1,2,3,4,4,4,5] 위에 a 리스트에서 4를 지우고 싶다. 물론 a.remove(4)를 하면 되지만 그럴 경우 4 하나만 지워지고 두개의 4가 아직 남아있다. 이럴때 해결방법!! a = [1,2,3,4,4,4,5,5,6] remove_set = {4,6} result = [i for i in a if not in remove_set] print(a) >> [1,2,3,5,5] remove_set 이라는 set을 만들어준다음 a가 remove_set에 포함되어 있다면 result에 담지 않는 것이다!

● 스택을 사용한 문제 ● 그리고 - 가 입력됐을때 어떻게 처리할지가 키포인트 우선 입력이 들어오면 바로 리스트에 담지 않고 입력이 ,- 중에 있는지 먼저 체크하였다. 만약

처음에 제목보고 재밌을거 같아서 시도해본 문제이다. 그러나 해결 알고리즘을 찾지 못해서 잠시 묵혀두었다가 스터디 시작하면서 다시 손을 대본 문제! 조합을 사용하여 시도했고 도중에 튜플을 리스트로 바꾸지 못해서 헤매었다.ㅎㅎ 해결 알고리즘: 나와 상대방이 뽑은 자연수를 같은 list에 담고 그 list를 set로 변경해줄때 변하는 길이의 변화를 갖고 풀었다.

문제해결: 입력받은 값을 가장 큰 팩토리얼 숫자부터 내림차순으로 빼준다. https://www.acmicpc.net/problem/2057

프로그램 내에서 바로 시간 복잡도를 측정할 수 있는 외장함수가 있다. time 을 import 해서 시작 부분에 시간을 start_time에 넣고 코드 마지막에 end_time을 넣어 그때의 시간을 측정한다음 뺄셈을 해준다. 그러면 그 사이 코드가 수행된 시간을 알 수 있다.

coordinate 라는 리스트를 만들어준 다음 입력 받은 것을 넣어 주었다. 여기서 coordinate는 좌표라는 뜻! 넣어줄때 [x, y] 로 넣어준게 아니라 [y, x] 로 넣어주었는데 문제가 y가 증가하는 순으로 출력하는 것이니 sort() 함수를 써주기 위해 y를 먼저 집어넣었다.

브루트 포스 (Brute-force) 는 '무차별 대입' 이라는 의미이다. 말 그대로 모든 경우의 수를 대입해보는 것이다. 완전탐색 전략을 사용하여 확실하게 답을 구하는 알고리즘이지만 단점은 시간복잡도에 있다. 모든 경우를 돌아보기 때문에 문제에서 시간초과가 발생 할 수 있다. 다음 문제를 보자. N개의 수를 입력 받아서 두 수를 뽑아 합이 가장 클 때는? 브루트 포스를 사용한다면 2중 for문을 돌면서 두 수를 골라 더해서 최댓값을 갱신하면 '두 수를 뽑는 모든 경우'를 살펴보게 되고, 답을 확실하게 구할 수 있다. 이때 시간 복잡도는 O(N^2)이 된다. 버뜨 list 사용해서 최댓값 찾고 그 두개를 더하면 시간복잡도는 O(NlogN)이다. 브루트 포스로 문제를 풀 때는 반복문을 사용할 때도 있고, ..

우선순위 큐는 내부적으로 힙(heap)이라는 완전이진트리 Complete binary Tree로 되어 있다. 힙 트리의 루트 노드(root node)에는 데이터들 중에 가장 큰 값 혹은 가장 작은 값을 담게 되는데, 전자는 최대힙(max-heap), 후자는 최소힙(min-heap)이라 한다. 어떤 값을 넣어도 항상 루트에 가장 큰 값 또는 가장 작은 값이 위치하도록 자동으로 갱신한다. 이 과정이 꽤 효율적이라 우선순위 큐의 값 삽입/삭제 시간 복잡도는 O(log N)이다. 무작위 숫자들을 힙에 전부 넣고 하나씩 빼면 정렬된 결과를 얻을 수 있는데, 이게 힙정렬이다. from queue import PriorityQueue pq = PriorityQueue() pq.put(123) pq.put(789) p..

Queue는 스택과 상반된 특징을 띄고 있는 자료구조이다. 둘 다 선형 자료구조이지만, 데이터 입출 순서가 달라지는 부분이 있다. 큐에는 데이터를 넣은 순서 그대로 빼게 된다. 첫 번째로 넣은 데이터가 첫 번째로 빠지며 이를 FIFO라 한다. 큐에 데이터를 넣고 뺄 때 시간 복잡도는 O(1)이므로 N개의 데이터를 넣고 빼야 한다면 총 O(N)이 될 것이다. from queue import Queue q = Queue() q.put(123) q.put(456) q.put(789) while not q.empty(): print(q.get()) 이렇게 import 해서 사용하면 된다. 위 코드에서 대문자 Q로 시작하는 Queue 모듈은 멀티스레딩 환경까지 고려해서 스레드 간에 안전한 방식으로 동작하는 모듈이..

Stack은 '쌓다', '무언가가 쌓여 있는 더미' 등을 의미한다. 스택은 의미 그대로 어떤 데이터를 삽입/삭제하는 과정을 '쌓는' 형태로 나타낼 수 있는 자료구조이다. 스택의 특징은 FILO (First In Last Out) 즉 먼저 저장된 데이터가 가장 나중에 나가는 방식으로 저장된다. 이름에서 힌트를 준것처럼 데이터가 차례대로 쌓인다. 가장 나중에 들어온 데이터는 먼저 나간다 LIFO (Last In First Out). 풜스트인풜스트 아웃 이말은 전에 TV 프로그램을 보다가 소방관 얘기가 나왔을 때 먼저 접했던 것 같다. 자료구조 얘기 하다가 뭔 소방관 얘기냐? 할 수 있겠는데 소방관들이 화재 현장을 들어 갈 때 FILO을 한다고 한다. 즉 먼저 들어가서 구조를 하고 끝까지 현장에 남아서 구조를..