Back to the Basics

문자열 조작은 코딩 테스트에서 매우 빈번하개 출제되고 실무에서도 다양한 분야에 쓰이는 주제라고 한다. 정보 처리 분야웹 페이지를 탐색할 때 문자열 처리 애플리케이션을 이용하게 되며 문자열 처리는 정보 처리에 핵심적인 역할을 한다. 통신 시스템 분야 데이터 전송은 문자열 처리 알고리즘이 탄생한 배경 이기도 하며, 데이터 전송에서 문자열 처리는 매우 중요하다. 프로그래밍 시스템 분야 프로그램은 그 자체가 문자열이며, 컴파일러나 인터프리터는 문자열을 기계어로 번역하기 때문에 매우 정교한 문자열 처리 알고르짐 등이 사용된다. 이번 장에서는 파이썬 문자열 자료형에 있는 기능들과 문자열 조작과 처리에 사용되는 기법을 알아본다. 유효한 팰린드롬 leetcode의 125 문제인 Valid Palindrome 문제를 통..

1. 리스트 입력순서 유지, 동적 배열로 구현됨 표 5-1 언어별 동적 배열 구현 언어 동적배열 Python list() C++ std::vector JAVA ArrayList 표 5-2 리스트의 주요 연산 시간 복잡도 연산 시간 복잡도 설명 len(a) O(1) 전체 요소의 개수를 리턴한다 a[i] O(1) 인덱스 i의 요소를 가져온다 a[i:j] O(k) i부터 j까지 슬라이스의 길이만큼 k개의 요소를 가져온다. 이 경우, 객체 k개에 대한 조회가 필요하므로 O(k) 이다. elem in a O(n) elem 요소가 존재하는지 확인한다. 처음부터 순서 탐색이므로 n만큼 시간이 소요된다. a.count(elem) O(n) elem 요소의 개수를 리턴한다 a.index(elem) O(n) elem 요소의..

이번 포스팅 에서는 시간복잡도를 나타내는 빅오와 파이썬의 자료형을 공부해보자. big-O (빅오) 입력값이 커질 때 알고리즘의 실행 시간(시간 복잡도)과 함께 공간 요구사항(공간 복잡도)이 어떻게 증가하는지를 분류하는데 사용 시간 복잡도를 분석할 때 '상한'과 '최악'의 경우에 대해 혼동하는 부분이 있음 분할 상환: 함수의 동작을 설명하는 매우 중요한 방법 중 하나 파이썬의 자료형 파이썬 자료형의 특징 1. 빅오 (1) 빅오 빅오는 점근적 실행 시간(Asymptotic Running Time)을 표기할 때 가장 널리쓰이는 수학적 표기 중 하나이다. 입력값 n이 커질 때 (입력값이 무한대를 향할 때) 함수의 실행 시간의 추이를 나타낸다. 이러한 점근적 실행 시간을 시간 복잡도라고 한다. 충분이 큰 입력에서..

몇 개월 전에 배웠던 파이썬 알고리즘 인터뷰라는 책은 구입하여 공부하고 있었다. 5개월 전까지는 나름 열심히 했는데, 정처기 공부를 하게 되고 지금 코드스테이츠를 하게 되면서 이 책은 책장 안에 데코레이션처럼 들어가 있었다. 조금 아깝기도 하고, 알고리즘 공부와 함께 파이썬도 다시 공부해 볼 겸 꺼내 들었다. 물론 일주일에 1-2번 보겠지만 꾸준히 하다 보면 결국 반 이상은 하지 않을까 싶은 마음이다.. 이번 포스팅은 이 책의 초반에 소개되는 이후의 알고리즘 리뷰를 위한 파이썬 주요 문법에 대해 간략하게 정리해보겠다. (이미 깃에 정리한 것을 여기다 조금 보기 좋게 정리하는 것이지만) Python 문법 인데트(Indent) : PEP 8에 따라 공백 4칸을 원칙으로 함 PEP(Python Enhnceme..

Data Structure and Algorithm Algorithm 이란? 사전적 정의 : 어떤 문제를 해경하기 위한 절차, 방법, 명령어들의 집합 programming : 주어진 문제를 해결하기 위한 자료구조와 연산 방법에 대한 선택. 자료구조를 배워야 하는 이유 : 문제를 파악하고 내가 사용한 자료구조가 어떤 성질이여야 하는지 알아야 하기 때문 Linear Array 1) Array와 List Arrya : 원소들을 순서대로 늘어놓는 것. List : data type이 다른 원소들 사용 가능. 2) Python List에 활용할 수 있는 연산들 실행시간이 list 길이에 독립적인 연산들 O(1) .append() : 맨 끝에 원소를 덧붙인다. .pop() : 맨 끝의 원소 하나를 꺼내고 꺼낸 것을..