영상, 글 요약
-
가장 기본적인 알고리즘, 브루트 포스(Brute Force) : 모든 경우 고려하는 알고리즘영상, 글 요약 2023. 1. 20. 00:01
#1 들어가기 전 브루트 포스(Brute Force) brute: 무식한, force: 힘 브루트 포스는 모든 경우를 고려하는 알고리즘이다. 그러므로, 시간을 오래 걸리더라도 100% 정확한 답을 찾을 수 있다. #2 본론 브루트 포스 알고리즘을 문제에 직접 적용하려면 우선 인풋의 범위와 시간제한을 확인해야 한다. 모든경우를 고려했을때, 예상되는 연산의 수를 계산해 보고 그 연산을 시간제한 안에 완료할 수 있는지 여부를 확인하는 작업이다. pypy3로 제출 할 경우, 1초에 약 2000만~1억번의 연산이 가능하다. 일반 python3로 제출할 경우, 1초에 약 2000만번의 연산이 가능하다. 또한 c++의 경우, 1초에 약 1억번의 연산이 가능하다고 한다. 예를들어 주어진 배열중에 " 1 " 을 찾는다고..
-
이진검색(binary search) 파이썬 반복문으로 구현영상, 글 요약 2023. 1. 19. 00:01
#1 서론 이진검색(binary search)는 시간복잡도가 O(log n)으로 빠르다. 다만 구현이 조금 까다롭다. 이번 글에선 구현을 완전 익혀보려 한다. #2 본론 찾고자하는 값을 target변수에 저장해 주었고, target이 들어있는 배열 A를 저장 해 주었다. 이진검색을 사용하려면 배열이 오름차순으로 정렬되어있어야 한다. 구현: A = [1, 2, 3, 4, 5, 6] target = 5 start = 0 end = len(A)-1 while start A[mid]: start = mid +1
-
링크드리스트 설명영상, 글 요약 2023. 1. 18. 00:01
#1 서론 링크드 리스트에 대해 설명한다. 싱글리 링크드 리스트와 더블리 링크드 리스트의 차이점을 설명하긴 하나, 구체적인 설명은 글에 모두 담기 힘들어 생략한다. 다만 본질적인 차이점을 알려주니, 연산을 구현할때를 생각해 보면 차이점을 알 수 있을 것이다. #2 본론 링크드 리스트 설명 링크드리스트는 배열과 다르게 RAM에 데이터를 연속적으로 저장하지 않는다. 즉, RAM에 각 데이터가 흩어져 있다는 말이다. [배열은 RAM에 데이터를 어떻게 저장하나] 그럼 데이터가 흩어져 있는데, 어떻게 순서를 만들어서 리스트를 만드느냐, 그것은 바로 노드 덕분이다. 링크드 리스트는 '노드(node)'들을 연결 해서 리스트를 만든 것이다. 각 노드는 다음과 같이 구성되어있다. 구분 노드 싱글리 링크드 리스트 data..
-
정적배열, 동적배열 차이점 설명영상, 글 요약 2023. 1. 17. 00:01
#1 서론 정적배열, 동적배열은 조금 다르다. 이 둘의 차이점을 알아본다. #들어가기 전 들어가기전에 우리가 프로그램(파이썬, C)를 사용해서 데이터를 배열이나 리스트, 딕셔너리 등에 저장할때 그 데이터가 컴퓨터 어디에 저장되는지 알아보자. 우리가 프로그램으로 데이터를 저장하면, RAM에 저장된다. RAM은 Random access memory로 우리가 필요로 하는 값을 저장한 '주소'만 알고 있으면 바로 값을 가져올 수 있다. #2 본론 정적배열과 동적배열 정적배열과 동적배열의 차이점은 '저장공간을 예약했냐' 이다. 정적배열은 RAM에 저장할 데이터의 길이를 미리 예약해 둔다. RAM은 한 칸에 '바이트'의 데이터를 저장할 수 있는데, 정적배열은 그 칸을 연속적으로 길이만큼 예약하는 것이다. 그래서 정..
-
큐(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) 마지막에 구워진 팬케이크를 먼저 먹듯이, 마지막에 들어온 ..
-
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를 받아서 일정한 알고리즘을 거친 뒤 인덱스로 변환하여 데이터 배열에 저장한다...
-
big O 간단한 설명영상, 글 요약 2022. 12. 26. 18:18
#1 서론 bigO는 알고리즘의 스피드를 표현하기 위해 만들어졌다. 알고리즘의 스피드를 '시간'으로 표현할 수 도 있다. 하지만 그렇게되면 기준이 정확하지 않다. 왜냐하면 실행하는 컴퓨터에 따라 실행 속도에 차이가 있기 때문이다. #2 본론 big O는 완료까지 걸리는 절차의 수이다. big O = n개의 인풋을 넣었을때, 아웃풋이 나오기까지 걸리는 절차의 수. 주의) 상수는 버린다. #3 결론 일일이 따지고 들어가면 헷갈리지만 간단히 정리해 보았다. #4 참고자료 https://youtu.be/BEVnxbxBqi8