목록전체 글 (225)
컴퓨터는 잘못이 없다..
[이것이코딩테스트다]5장_탐색 알고리즘 DFS/BFS(3)_DFS,BFS에 필요한 자료구조 - 재귀 함수
#재귀 함수 재귀 함수란 : 자기 자신을 다시 호출하는 함수를 의미한다. #간단한 재귀 함수 예 def recursive_function() : print('재귀 함수를 호출합니다.') #재귀함수 호출 recursive_function() #재귀함수 호출 recursive_function() ▲설명 이 코드를 실행하면 '재귀 함수를 호출합니다.' 라는 문자열을 무한히 출력한다. 여기서 정의한 recursive_functino()이 자기 자신을 계속해서 추가로 불러오기 때문이다. 물론 어느 정도 출력하다가 다음과 같은 오류 메시지를 출력하고 멈출 것이다. RecursionError: maximum recursion depth exceeded while pickling an object 이 오류 메시지는 재..
[이것이코딩테스트다]5장_탐색 알고리즘 DFS/BFS(2)_DFS,BFS에 필요한 자료구조 - 스택, 큐
#스택 스택 : 박스 쌓기에 비유할 수 있음. 박스는 아래에서부터 위로 차곡차곡 쌓고 아래에 있는 박스를 치우기 위해서는 위에있는 박스를 먼저 내려야함. 이러한 구조를 선입후출(FILO) 구조 또는 후입선출(LIFO) 구조 라고 함 #파이썬의 스택 구현 리스트(stack=[])로 구현하며 push, pop은 아래와 같은 함수로 구현한다. i를 push : stack.append(i) 최상단 원소를 pop : stack.pop() #스택 예제 stack=[] stack.append(5) #5를 스택에 push stack.append(2) stack.append(3) stack.append(7) stack.pop() #최상단 원소를 pop stack.append(1) stack.append(4) stack...
#탐색 탐색 : 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정을 의미한다. 프로그래밍에서는 그래프, 트리 등의 자료구조 안에서 탐색을 하는 문제를 자주 다룬다. 대표적인 탐색 알고리즘으로는 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가지 방식으로 표현할 수 있다. 코딩 테스트에서는 이 두 방식 모두 필요하니 두 개념에 대해 바르게 알고 있..
