Back to the Basics

단일 연결 리스트 자료구조 연결 리스트는 실행 시간에 메모리를 할당하거나 해제할 수 있는 동적 자료구조이다. 이번 포스팅에서는 단일 연결 리스트의 개념과 단일 연결 리스트 연산들의 구현에 대해 간단하게 정리해 보았다. 참고로 사용한 언어는 python이다. 1. 연결 리스트의 개념 연결 리스트 자료구조는 배열처럼 선형 자료구조에 속하지만 인덱스로 접근하는 것이 아닌, 각 노드가 다음 노드에 대한 참조를 갖는 구조이다. 배열처럼 자료들의 메모리가 선형적으로 저장되지 않고 흩어져(?) 있지만 각 노드의 참조를 갖고 있기 때문에, 그 참조를 따라 다음 노드로 접근할 수 있다. 아래의 그림을 보면 쉽게 이해할 수 있다. 각 노드는 데이터를 담는 data field와 다음 노드를 참조하는 pointer field..

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

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

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

5강 재귀 알고리즘 (recursive algorithms) - 응용 문제의 종류에 따라 재귀 알고리즘을 적용하여 알고리즘을 간단하고 이해하기 쉽게 서술할 수 있다는 장점이 있다. 하지만 일반적으로 주어진 문제에 대해서 반복적인 알고리즘이 제귀적인 알고리즘보다 시작적 효율이 더 높다. 그럼에도 불구하고 사람의 생각을 코드로 옮겨놓을 수 있다는 특성 때문에 tree와 같은 자료구조를 이용하는 알고리즘에는 매우 직관적으로 적용할 수 있는 경우가 많다. 재귀알고리즘을 이용하여 다음의 문제들을 풀 수 있다. (1) 조합의 수 (n 개의 서로 다른 원소애서 m개를 택하는 경우의 수) 구하기 // Trivial case를 고려해야 한다. // n=m 일 때와 m=0일 때 이외에 재귀를 사용하여 구현한다. def c..

PROMRAMMERS - PART3. SORT & SEARCHING PYTHON LIST의 정렬 (1) sorted() 내장함수 (built-in function) 정렬된 새로운 리스트를 얻어낸다. (2) sort() list의 method 해당 리스트를 정렬한다. 원래 list 자체가 정렬된다. Function와 Method의 차이는? function : class와 상관 없이 독립적이다. method : class & object와 연관이 있음. class 내에 선언되어있는 함수. # 문자열로 이루어진 리스트에서 문자열 순서로 정렬하려면, 정렬에 이용할 수 있는 Key를 지정. # 문자열로 이루러진 list의 경우 사전 순거로 정렬디 된다. (대문자>소문자) L1=['abcd','..

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