알고리즘

알고리즘/study with python
sys.stdin.readline
Java 에서 scanner 보다 buffer 가 더 가볍고 빠른 것처럼 파이썬에서도 input() 보다 sys.stdin.readline() 이 더 빠르게 작동한다. 이유는 input() 내에서 raw_input()을 evaluate 해서 라는데 자세한것은 내부를 들여다 봐야 할 것 같다. 알고리즘 문제에서 만일 입력값이 너무 크다면(백만 이상의 갯수) 한면 input()을 쓰는 것을 지양하자. 입력 속도 비교 자료 [www.acmicpc.net/blog/view/56]
→2020.09.23
알고리즘/코딩 테스트 후기
개발형 코딩테스트 준비를 위한 HTTP프로토콜, REST API with python
개발형 코딩 테스트 개념 정리 API란 무엇인가? -Application Programming Interface -프로그램끼리 데이터를 주고 받기 위한 방식 데이터를 주고 받는 서로의 규칙을 만들어 놓았다 -> 프로토콜 - 이것은 정하기 나름 - 많이 사용하는것중 하나가HTTP(hyper text transfer protocol) 예를 들어서 홈페이지에 url을 입력하면 해당 페이지로 가는데 이것이 http 프로토콜이라고 할 수 있다. (http 프로토콜 순서도) 1. 내가 보고 싶은 페이지의 url 을 브라우저에서 서버 측으로 보낸다 2. 서버는 브라우저 측으로 응답을 보내준다 3. 브라우저는 서버에서 온 응답을 가지고 시각화 하여서 화면에 나타내어 준다. Python에서 사용 방법 1. request..
→2020.09.20
알고리즘/이것이 취업을 위한 코딩테스트다 with 파이썬
Chapter 7. 이진탐색
1. 순차탐색: 리스트 안에 있는 특정한 데이터를 찾기 위해서 앞에서 부터 데이터를 하나씩 차례대로 확인하는 방법 count()메서드 또한 순차탐색이 이용된다. 2. 이진탐색: 이진탐색은 배열 내부의 데이터가 정렬되어 있어야만 사용 할 수 있는 알고리즘이다. 변수 3개를 사용하는데 시작점, 끝점 그리고 중간 점을 이용한다. 찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교해서 원하는 데이터를 찾는게 이진탐색 과정이다. 시간 복잡도는 O(nlogn)이다. (한번 확인할때 마다 확인하는 원소의 개수가 절반씩 줄어들기 때문) 이진탐색 쉽게 보지 말자!!! '존 벤틀리'(생각하는 프로그래밍의 필자) 의 말에 따르면 제대로 이진 탐색 코드를 작성한 프로그래머는 10% 내외라 할 정도로 실제 구현은 까..
→2020.09.19
알고리즘/이것이 취업을 위한 코딩테스트다 with 파이썬
Chapter 6. 정렬
1. 선택정렬: 매번 가장 작은것을 선택해서 정렬 안된 부분의 가장 첫번째 위치에 자리시킨다. tip) 파이썬의 스와이프는 매우 간단하다는 것을 이용하자 -시간 복잡도: O(n^2) 2. 삽입정렬: 이미 정렬된 리스트에 데이터 하나를 삽입 할때 적절한 위치에 삽입하면 되는 것을 착안한다는 식으로 구현하면 된다. 현재 가르키고 있는 인데스 앞부분은 이미 정렬되어 있다고 본다(실제로 정렬 되어 있을것이다.). 인덱스를 점차 증가 시키면서 앞의 배열에 삽입하는 식으로 거의 정렬된 리스트에 효과적이다. - 시간 복잡도 : O(n^2), 거의 정렬되어 잇을 경우 -> O(n) 3. 퀵정렬: 재귀식으로 작동한다. 3가지 포인트만 기억하자 1. 피벗 정하기 2. 왼쪽 부분 오른쪽 부분 각 두 지점에서 출발하여 왼쪽 ..
→2020.09.19
알고리즘/이것이 취업을 위한 코딩테스트다 with 파이썬
chapter5. DFS/BFS
탐색(Search)란? -> '많은 양의 데이터 중에서 원하는 데이터를 찾는 과정' -대표적인 탐색은 DFS, BFS 자료구조(Data Struct)란? -> '데이터를 표현하고 관리하고 처리하기 위한 구조' -대표적인 자료구조 스택과 큐 - First in Last out & Last in First out 파이썬에서 스택을 이용할 때에는 별도의 라이브러리를 사용할 필요가 없다! 기본 리스트에서 append() 와 pop()메서드를 이용하면 스택 자료구조와 동일하게 동작한다. append()메서드는 리스트의 가장 뒤쪽에 데이터를 삽입하고, pop() 메서드는 리스트의 가장 뒤쪽에서 데이터를 꺼내기 때문이다. - First in First out 파이썬에서 큐를 이용할때에는 collections 모듈에서..
→2020.08.21
알고리즘/이것이 취업을 위한 코딩테스트다 with 파이썬
chapter4. 구현
코딩 테스트 에서 구현(implementation)이란? : 머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정 이라고 책에서 소개하고 있다. 주로 머릿속에서 떠올리기는 쉽지만 구현이 복잡하거나 어려운 문제들이 출제되는 경향이 많다고 한다. 그럼 이를 위해서 우리는 피지컬을 키워야 한다고 나온다. 코딩에서 피지컬이란, 프로그래밍 문법에 능숙하고 코드작석 속도가 빠른 것을 일컫는다. 구현에서 주의 해야 할 점들을 몇가지 소개 하고 있다. 정수형 종류 자료형의 크기 자료형의 범위 int 4byte -2,147,483,648 ~ 2,147,483,647 long long 8byte -9,223,372,036,854,775,808 ~ 9,223,372,036,854,775,807 BigInteger(클래스) 가변적..
→2020.08.20
알고리즘/이것이 취업을 위한 코딩테스트다 with 파이썬
chapter 3. 그리디
그리디는 탐욕적이라는 뜻으로 '현재 상황에서 지금 당장 좋은 것만 고르는 방법'을 의미합니다. 그리디 알고리즘을 이용하면 매 순간 가장 좋아 보이는 것을 선택하며, 현재의 선택이 나중에 미칠 영향에 대해서는 고려하지 않습니다. 이 책에서는 그리디 알고리즘은 다른 알고리즘과 비교해서 비교적 '사전에 외우고 있지 않아도 풀 수 있을 가능성이 높은 문제 유형' 이라고 소개 해고 있습니다. 하지만 다익스트라 같은 알고리즘도 최단거리 이면서 그리디로 분류 되므로 무조건적이지는 않습니다. 몇가지 감만 익히면 그리디 알고리즘을 코딩테스트에서 틀릴 일을 없다고 생각이 듭니다. 제가 이 책으로 공부하면서 얻은 그리디 문제 풀이 방법에 대한 팁은 최소한의 문제에 대한 아이디어를 떠올리고 그리디적 사고가 타당한지를 스스로 ..
→2020.08.19

알고리즘/이것이 취업을 위한 코딩테스트다 with 파이썬
책 구매 '이것이 취업을 위한 코딩 테스트다 with 파이썬' -나동빈 지음-
저는 나동빈님을 굉장히 repect 합니다. 이분께서 책을 출판 하셧다길래 바로 겟도다찌ㅎ 해버렸습니다. 유투브로 매주마다 Live로 특강도 해주시길래 이거 보면서 강의 들을라고 바로 샀습니다. 바로 공부 들어갑니다. 우리 모두 화이팅 합시다.... [책 구매: www.aladin.co.kr/shop/wproduct.aspx?ItemId=247882118]
→2020.08.18

• 1