728x90 IT 개인학습45 이진 탐색 Binary Search " 범위를 반씩 좁혀가는 탐색 " 순차 탐색 Sequential Search - 리스트 내에서 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 매우 빠르게 탐색하는 이진 탐색 알고리즘 - 예시) Greedy '거스름돈' 문제에서 가장 큰 화폐 단위부터 확인(탐색)해서 각 단위에 대하여 처리한 것 - 리스트 내에 데이터가 아무리 많아도 시간만 충분하다면 항상 원하는 원소(데이터)를 찾을 수 있다는 장점 - 데이터의 개수가 N개일 때 최대 N번의 비교 연산이 필요하므로 최악의 경우 시간복잡도 O(N) - 리스트에 특정 값의 원소가 있는지 체크할 때 순차 탐색으로 원소를 확인하고, 리스트 자료형에서 특정한 값을 가지는 원소의 개수를 세는 count() 메서드를 이용할 때에도 내부에서는 순차 탐색이 수행됨.. 2022. 8. 24. Sorting 정렬 정렬이란 " 데이터를 특정한 기준에 따라서 순서대로 나열 " 정렬 알고리즘으로 데이터를 정렬하면 => 이진 탐색(Binary Search)이 가능해짐 ??? - 정렬 알고리즘은 이진 탐색의 전처리 과정이기도 하다 https://cord-ai.tistory.com/161 정렬 알고리즘 - 선택 정렬, 삽입 정렬, 퀵 정렬, 계수 정렬 - Python에서 제공하는 기본 정렬 라이브러리 적용 가능(= 더 효율적인 정렬 수행 방법) - 면접에서도 단골 문제로 출제 # 단순 정렬해야하는 상황에서는 기본 정렬 라이브러리(sort, sorted) 사용 # 데이터의 범위가 한정되어 있으며 더 빠르게 동작해야할 경우 계수 정렬 사용 1. 정렬 라이브러리로 풀 수 있는 문제 : 단순히 정렬 기법을 알고 있는지 물어보는 문.. 2022. 8. 19. if not 문 if not x 의 조건에 들어맞는 x는 다음과 같다. 1) False 2) 0 3) 빈 리스트 [] 4) 빈 튜플 () 5) 빈 딕셔너리 {} 6) 문자길이 0의 문자열 "" 7) None 8) 등등 if 로 None 여부를 알고 싶을 때는 if x==None으로 하지 말고, if x is None 으로 하기. => 의미는 같지만, if x is None이 내부적으로 약간 빠르다고 한다. ## if not X: => X의 결과가 False 이면 해당 조건 출력 if not False: print ("not of False is True.") if not True: print ("not of True is False.") not of 0 is True. 2022. 8. 15. DFS / BFS , Graph Structure "Stack, Queue, Recursive Func는 DFS / BFS에서 가장 중요한 개념" https://cord-ai.tistory.com/156 Stack, Queue, Recursive Function " 그래프를 탐색하기 위한 대표적인 두 가지 알고리즘 " 탐색(Search)이란??? - 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정 - 프로그래밍에서는 그래프, 트리 등의 자료구조 안에서 탐색을 cord-ai.tistory.com 그래프 구조, Graph Structure - 노드 Node, 간선 Edge로 표현됨(이 때 노드를 정점 Vertex라고도 말한다) - 예를 들어 노드 == 도시, 간선 == 도로 - 그래프 탐색이란 하나의 노드를 시작으로 다수의 노드를 방문하는 것을 말한다... 2022. 8. 15. 프로세스 메모리 구조 프로세스 메모리 구조 프로그램이 실행되기 위해서는 먼저 프로그램이 운영체제로부터 메모리 공간을 할당받아야 한다. 따라서 컴퓨터의 운영체제는 프로그램의 실행을 위해 다양한 메모리 공간을 제공하는데, 프로그램이 운영체제로부터 할당받는 대표적인 메모리 공간에는 4가지 영역이 존재한다. 코드 영역과 데이터 영역은 프로세스가 실행되기 직전에 위치와 크기가 결정되고 실행되는 동안 변하지 않으므로 정적 할당 영역이라고 부른다. 1. 코드(code) 영역: 실행할 프로그램의 코드가 저장되는 영역 2. 데이터(data) 영역: 프로그램이 사용하려고 미리 정의한 변수와 데이터가 저장되는 영역 스택 영역과 힙 영역은 스레드가 작업하면서 값이 바뀌거나 새로 만들 만들어지거나 사라지는 동적 할당 영역이다. 3. 스택(stack.. 2022. 8. 15. Stack, Queue, Recursive Function " 그래프를 탐색하기 위한 대표적인 두 가지 알고리즘 " 탐색(Search)이란??? - 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정 - 프로그래밍에서는 그래프, 트리 등의 자료구조 안에서 탐색을 하는 문제를 자주 다룬다. - DFS / BFS를 제대로 이해하려면 기본 자료구조인 stack과 queue에 대한 이해가 전제되어야함 자료구조(Data Structure)란??? - 데이터를 표현하고 관리하고 처리하기 위한 구조 - Stack과 Queue는 자료구조의 기초 개념으로 다음의 두 핵심적인 함수로 구성됨 ## Python에서 스택을 이용할 때에는 별도의 라이브러리 사용할 필요가 없다. why?? append(), pop() 메서드를 이용하면 스택 자료구조와 동일하게 동작한다. * 삽입(Push.. 2022. 8. 13. Implementation(구현) '머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정' - 개발할 때 프로그래밍 언어의 문법에 능숙하고 코드 작성 속도(타이핑)가 빠른 사람을 보고 "피지컬이 좋다" 라고 함 => 구현 유형의 문제는 "피지컬을 요구하는 문제"라고도 할 수 있음 1. 알고리즘은 간단한데 코드가 지나칠 만큼 길어지는 문제 2. 특정 소수점 자리까지 출력해야 하는 문제 3. 문자열이 입력으로 주어졌을 때 문자 단위로 끊어서 리스트에 넣어야(=파싱을 해야 하는) 하는 문제 "Parsing???" - 언어학에서 parsing은 구문 분석이라고도하며 문장을 그것을 이루고 있는 구성 성분으로 분해하고 그들 사이의 위계 관계를 분석하여 문장의 구조를 결정하는 것 https://na27.tistory.com/230 Parsing (파싱) .. 2022. 8. 11. Greedy(탐욕) ' 현재 상황에서 지금 당장 좋은 것만 고르는 방법 ' ' 사전에 외우고 있지 않아도 풀 수 있을 가능성이 높은 문제 유형 ' - 최단 경로를 빠르게 찾아야 하는 문제는 플로이드 워셜(Floyd-Warshall) or 다익스트라(Dijkstra) 알고리즘을 알고 있어야한다. 특히, 다익스트라 알고리즘은 그리드 알고리즘으로 분류됨 - 그리디 알고리즘이면서도 ' 암기 ' 가 필요한 알고리즘 - But 단순 암기를 통해 모든 문제를 대처하기는 어렵다는 점을 이해하자 1. 바로 문제 유형을 파악하기 어렵다면 그리디 알고리즘을 의심하고, 문제를 해결할 수 있는 탐욕적인 해결법이 존재하는지 고민 2. 그리디 알고리즘으로 해결 방법을 찾을 수 없다면??? -> 다이나믹 프로그래밍, 그래프 알고리즘 고려 # 거스름돈 .. 2022. 8. 9. 이전 1 2 3 4 5 6 다음
