의미있는 커밋 의미있는 커밋

전체 글

• 백준 1406번 어떻게 풀었나. 파이썬 내장함수 시간복잡도 정리

  백준 2023. 1. 6. 00:01

  푼 방법 처음엔 insert와 del을 사용하였다. 그랬더니 시간초과가 나왔다. 왜 그린지 못찾겠어서 구글링했다. insert와 del은 시간복잡도가 O(n)이다. 사용을 지양하는 것이 좋다. 구글링을 한 결과, 스택을 두개 사용하여 풀 수 있었다. 고치면 좋을 부분 파이썬의 내장함수의 시간복잡도를 잘 알아야 겠다. 걸리는 시간을 고려하지 않고 작성했다. 계획하기 단계를 좀 더 체계적으로 해야 될거 같다 .readline().strip() 보다 .readline().rstrip()이 더 빠를거 같다. 파이썬 내장함수 시간복잡도 정리 https://wayhome25.github.io/python/2017/06/14/time-complexity/ 코드 import sys stackLeft = list(sys..

  Read More
• 백준 10828번 어떻게 풀었나, 스택(Stack) 구현

  백준 2023. 1. 5. 00:01

  푼 방법 문제에 적혀있는 데로 구현 해 주었다.. 더 알고 싶은 부분 한줄에 조건문 쓰는 법 if 아래 두 코드는 똑같다. if animal is dog: ret = dog if animal is dog: ret = dog if - else 결과 = A if 조건 else B if - elif - else 결과 = A if 조건 else B if 조건 else C 코드 import sys N = int(sys.stdin.readline()) stack = [] for i in range(N): cmd = sys.stdin.readline().strip() # push X: 정수 X를 스택에 넣는 연산이다. if "push" in cmd: stack.append(cmd[5:]) # pop: 스택에서 가장 ..

  Read More
• 큐(Queues)와 스택(Stacks)

  영상, 글 요약 2023. 1. 4. 00:01

  #1 서론 꼭 알고있어야 하는 자료구조 큐와 스택을 설명한다. #2 본론 큐와 스택은 실제로 프로그래밍 언어에 존재하지 않는다. 큐와 스택은 일종의 '규칙'이다. 이런 것들을 Abstract Data Type이라고 부른다. ADT는 자료구조의 방법이 코드로 정의된 것이 아니라 그 구조의 행동 양식만 정의된 것을 뜻한다. 큐와 스택은 배열위에서 나타날 수 있다. 큐(Queues) FIFO (First in First out) 버스정류장에서 사람들이 줄 서는 것처럼, 먼저 들어온 값이 먼저 나가는 자료구조이다. 예시 쇼핑몰 주문 처리(선착순) 콜센터 백엔드 (먼저 온 전화를 먼저 처리) 스택(stacks) LIFO (Last in First out) 마지막에 구워진 팬케이크를 먼저 먹듯이, 마지막에 들어온 ..

  Read More
• 백준 1874번 어떻게 풀었나.

  백준 2023. 1. 3. 22:33

  푼 방법 문제에 맞게 조건문 3개정도 만들었다. 잘 알고있는 stack을 사용해야 된다고 문제에서 알려주니 쉬운 문제였다. 코드 import sys n = int(sys.stdin.readline().rstrip()) stack = [] answer = [] cur = 1 for i in range(n): num = int(sys.stdin.readline().rstrip()) while cur

  Read More
• Hash Table과 array 차이점, 설명

  영상, 글 요약 2023. 1. 3. 00:01

  #1 서론 어떤 사람이 좋아하는 국가들이 배열에 저장되어있다고 가정하자. 그럼 어떤사람이 '한국'을 좋아하는지 찾으려고 한다면 선형검색(Linear Search)을 해서 찾아야 할 것이다. 그럼 시간 복잡도는 O(n)일 것이다. 이것은 그리 효율적이지 않다. 이보다 더 효율적으로 만들 수 있다. 그것을 알아본다. #1-1 시작하기 전 알아야 할 것 Hash Table Key : Value 형태로 이루어진 자료구조 예시 Python - Dictionary JS - Object 보통 시간복잡도는 O(1)이지만, 항상 그런것은 아니다. 이유는 Hash function에서 설명한다. Hash function 아래 그림1과 같이 key를 받아서 일정한 알고리즘을 거친 뒤 인덱스로 변환하여 데이터 배열에 저장한다...

  Read More
• 백준 10815번 어떻게 풀었나

  백준 2023. 1. 2. 00:01

  푼 방법 1920번 문제와 굉장히 유사하여 코드를 출력문만 바꿔서 복붙했다. 좋았던점 비슷한 문제가 생각났다. 코드 import sys # N입력받기 N = int(input()) # 리스트 입력받기 A = list(map(int, sys.stdin.readline().split())) # M 입력받기 M = int(input()) # 리스트 입력받기 cheaklist = list(map(int, sys.stdin.readline().split())) A.sort() #이진검색 for k in range(M): left = 0 right = N-1 while True: middle = (left + right) // 2 if cheaklist[k] == A[middle]: print(1, end=" ")..

  Read More
• 계수정렬(counting sort)의 원리

  영상, 글 요약 2023. 1. 1. 00:01

  계수 정렬의 아이디어는 단순하다. [5, 2, 3, 1, 4, 2, 3, 5, 1, 7]이라는 배열이 있다고 가정하자. 이 숫자를 세 보면 1 - 2개 2 - 2개 3 - 2개 4 - 1개 5 - 2개 7 - 1개 그리고 1부터 7까지 갯수대로 나열해보면, [1,1,2,2,3,3,4,5,5,7] 끝이다. https://velog.io/@chappi/알고리즘-6일차-On-정렬-계수-정렬

  Read More
• 백준 10866번 어떻게 풀었나, 덱(Deque) 구현

  백준 2022. 12. 31. 12:54

  코드 import sys N = int(sys.stdin.readline()) stack = [] for i in range(N): cmd = sys.stdin.readline().strip() # push_front X: 정수 X를 덱의 앞에 넣는다. if "push_front" in cmd: stack.insert(0, cmd[11:]) # push_back X: 정수 X를 덱의 뒤에 넣는다. if "push_back" in cmd: stack.append(cmd[10:]) # pop_front: 덱의 가장 앞에 있는 수를 빼고, 그 수를 출력한다. 만약, 덱에 들어있는 정수가 없는 경우에는 -1을 출력한다. elif cmd == "pop_front": print(stack.pop(0) if stac..

  Read More