Linked List가 뭘까? Linked List를 정말로 이해하려면 연결 목록이 어떤 유형의 자료 구조인지 알아야 한다. Linked List의 한 가지 특징은 선형 자료 구조라는 것인데, 이는 그것들이 어떻게 구성되고 가로지르는지에 대한 sequence와 order가 있다는 것이다. 예를 들어 징검다리를 생각했을때 중간 지점을 가기 위해선 처음 돌부터 해당 지점까지 순차적으로 이동해야한다. 배열, 링크드 리스트 등이 선형 자료 구조이다. 비선형 자료 구조는 항목을 순서대로 정렬할 필요가 없고 비순차적으로 탐색이 가능하다. 해시 테이블 , 트리, 그래프 등이 비선형 자료 구조에 속한다. 그렇다면 배열과 링크드 리스트의 차이점이 무엇일까? 가장 큰 차이점은 시스템에서 메모리를 사용하는 방식이다. 배열이..

도서관에서 책을 분류하는 기준없이 꽂았다고 생각을 해보자. 우리는 책을 어떻게 찾을까? 자신이 원하는 책을 찾을 때까지 모든 책을 탐색할 것이다. 이 경우, 하나의 책을 확인하는데 걸리는 시간이 1초라고 가정하고 마지막 책을 확인했을때 책을 찾았다면 시간은 (도서관에 존재하는 책의 개수)초 만큼의 시간이 걸릴 것이다. 그렇다면 지금 우리의 도서관에서는 책을 찾는데 얼마나 시간이 걸릴까? 책의 제목의 맨 처음 글자로 구분했고 우리의 눈앞에 책장들이 있고 책장엔 책 하나씩만 있다고 가정했을때, '가장' 이란 책을 찾는데는 1초가 걸릴 것이다. 탐색에서 가장 쉽게 찾는 것은 무엇을 의미할까? 요소들을 하나하나 들여다볼 필요없이 '즉시' 검색하는 것이다. 그리고 이를 구현할 수 있는 추..

이 게시물은 게시자의 이해를 위하여 작성됨. " LIS ( Longest Increasing Subsequence ) 최장 증가 부분수열 알고리즘 " 최장 증가 부분수열 알고리즘은 N개의 배열의 일부 원소를 골라내서 만든 부분 수열의 각 원소가 이전 원소보다 크다는 조건을 만족하는 가장 긴 부분 수열을 의미. [ DP를 이용하는 방법 ] data = [10, 0, 20, 30] for i in range(n): DP[i] = 1 for j in range(i): if data[j] < data[i]: DP[i] = max(DP[i], DP[j] + 1) 1. i = 0일 때, DP[0] = 1 / j는 반복하지 않음. 1 2. i = 1일 때, DP[1] = 1 / for j in range(1)이기에 ..

이 게시글은 게시자의 이해를 위해 작성됨. " Longest Common Subsequence / Substring " 이는 한국어로 최장 공통 부분수열 / 문자열 이라고 함. ( 주로 최장 공통 부분수열을 말함. ) 먼저 최장 공통 문자열에 대해 알아보자. { 최장 공통 문자열 / Longest Common Substring } 최장 공통 문자열은 위처럼 연결되어있는 문자열이 같은 경우를 말함. 무조건 이어져 있어야함. 최장 공통 부분수열은 떨어져있는 경우도 생각해야하는데 이건 그렇지 않으니까 더 쉬움. 최장 공통 문자열에서 생각해야 하는 것은 두 문자열의 문자가 같은지와 문자가 연속되는지를 생각해야함. [ 두 문자의 비교 순서 ] 1. 두 문자열의 문자를 하나씩 비교. 2. 두 문자가 다르면 LCS[..

1. mutable, immutable 객체란?? 파이썬은 객체를 두 종류로 구분 - mutable : 변경되는 객체 ( 객체 상태 변경 가능 ), ex) list, set, dictionary 등 - immutable : 변경되지 않는 객체 ( 객체 상태 변경 불가능 ) ex) int, float, tuple, str, bool 등 2. 이것이 복사에서 어떤 영향을 줄까? > 파이썬에서는 immutable 객체의 값이 같은 경우에 변수에 상관없이 동일한 곳을 참조. > mutable 객체의 경우엔 각각의 객체를 모두 생성해서 참조. - immutable x, y, z라는 변수는 각각 333이란 값을 가진다..