목록공부/알고리즘(파이썬) (64)
컴퓨터는 잘못이 없다..
#탐색 탐색 : 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정을 의미한다. 프로그래밍에서는 그래프, 트리 등의 자료구조 안에서 탐색을 하는 문제를 자주 다룬다. 대표적인 탐색 알고리즘으로는 DFS와 BFS를 꼽을 수 있다. #DFS/BFS를 위해 필요한 자료구조 스택과 큐 #자료구조란? 자료구조 : '데이터를 표현하고 관리하고 처리하기 위한 구조'를 의미한다. #스택과 큐 스택과 큐는 자료구조의 기초 개념으로 다음의 두 핵심적인 함수로 구성된다. -삽입(push) : 데이터를 삽입한다. -삭제(pop) : 데이터를 삭제한다. #오버플로우, 언더플로우 스택과 큐를 사용할 때는 오버플로우와 언더플로우를 고민해야한다. -오버플로우 : 특정한 자료구조가 수용할 수 있는 데이터의 크기를 이미 가득 찬 상태에..
출처 : 파이썬 알고리즘 인터뷰 #빅오 표기법의 종류 종류 설명 O(1) 입력값이 아무리 커도 실행 시간은 일정하다. 최고의 알고리즘이라 할 수 있다. O(logn) 여기서부터 실행 시간은 입력값에 영향을 받는다. 그러나 로그는 매우 크 입력값에도 크게 영향을 받지 않는 편이므로 웬만한 n의 크기에 대해서도 매우 견고하다. 대표적으로 이진 검색이 이에 해당한다. O(n) 입력값만큼 실행 시간에 영향을 받으며, 알고리즘을 수행하는 데 걸리는 시간은 입력값에 비례한다. 이러한 알고리즘을 선형 시간 알고리즘이라고 한다. 정렬되지 않은 리스트에서 최대값 또는 최솟값을 찾는 경우가 이에 해당한다. O(nlogn) 병합정렬을 비롯한 대부분의 효율 좋은 정렬 알고리즘이 이에 해당한다. 입력값이 최선인 경우 비교를 건..
[파이썬 알고리즘 인터뷰]6장_문자열 조작 04_가장 흔한 단어(파이썬 collections모듈의 Counter객체, most_common() 사용법, max()사용법, defaultdict사용법)
#이 포스팅에서 암기해야할 것 1. defaultdict 사용하기 2. collections 모듈의 Counter 객체 3. Counter객체의 most_common() 사용하는 법 #문제 링크 (3) Most Common Word - LeetCode Most Common Word - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com #문제 Given a string paragraph and a string array of the banned words banned..
[이것이코딩테스트다]5장_탐색 알고리즘 DFS/BFS(4)_그래프(파이썬으로 그래프 표현하기)
#책 페이지 p.134 #DFS,BFS를 알기 전 알아두어야 할 자료구조 스택, 큐, 재귀함수 #DFS란 DFS는 깊이 우선 탐색이라고도 부르며, 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이다. DFS를 설명하기 전에 먼저 그래프의 기본 구조를 알아야 한다. #그래프의 기본 구조 1. 노드와 간선 그래프는 노드(Node)(=정점(Vertex))와 간선(Edge)로 표현된다. 그래프 탐색이란 하나의 노드를 시작으로 다수의 노드를 방문하는 것을 말한다. 또한 두 노드가 간선으로 연결되어 있다면 '두 노드는 인접하다' 라고 표현한다. 2. 인접 행렬과 인접 리스트 프로그래밍에선 그래프를 크게 3가지 방식으로 표현할 수 있다. 코딩 테스트에서는 이 두 방식 모두 필요하니 두 개념에 대해 바르게 알고 있..
[파이썬 알고리즘 인터뷰]6장_문자열 조작 01_유효한 펠린드롬(파이썬 isalnum(), lower(), re.sub()으로 문자열에서 특정문자 제거 ,deque 자료형, 슬라이싱 사용,pop(0)과 popleft의 시간복잡도)
#이 포스팅에서 암기해야할 점 1. pop(0)의 시간복잡도는 O(N), 데크의 popleft()는 시간복잡도는 O(1), 둘의 기능은 같음! 2. s.isalnum() 숫자나 문자일때만 true리턴 3. s.lower() 소문자로 바꿔서 리턴 4. 데크 사용법 from collections import deque → deque=deque() 5. 슬라이싱 사용법 s[:],s[::2],s[::-1],s[-1] 등등등... 6. 정규식으로 문자 외에 것 제거하기 s=re.sub('[^a-z0-9]','',s) #a~z, 0~9 를 제외한(^) 나머지는 ''로 치환해서 s에 담아라 #책 페이지 p.138 #문제 링크 Loading... (leetcode.com) Valid Palindrome - LeetCo..
#책 페이지 p.137 #문자열 조작 -문자열 조작? 문자열을 변경하거나 분리하는 등의 여러 과정을 말한다. -문자열 조작은 어떻게 풀까? 대부분의 언어에서는 별도의 문자열 자료형과 문자열을 조작하기 위한 다양한 기능들을 기본적으로 제공하고 있기 때문에 굳이 제약을 두지 않은 한, 언어에서 제공하는 기본 기능들을 잘 활용해서 풀면 된다. -문자열 조작은 얼마나 출제될까? 문자열 조작은 코딩 테스트에서 매우 빈번하게 출제되는 주제 중 하나이다. 특히 실무에서도 다양한 분야에 쓰이는 상당한 실용적인 주제이다. -문자열 처리와 관련한 알고리즘이 쓰이는 분야는 어디가 있을까? 정보처리 분야, 통신 시스템분야, 프로그래밍 시스템 분야에 쓰인다.
