전체 글 65
파이썬) 연결 리스트

데이터 원소들을 순서를 지어 늘어놓는다는 점에서 연결 리스트 (linked list) 는 선형 배열 (linear array) 과 비슷한 면이 있지만, 선형 배열은 "번호가 붙여진 칸에 원소들을 채워넣는" 방식이라고 한다면, 연결 리스트는 "각 원소들을 줄줄이 엮어서" 관리하는 방식에 차이점이 있다. 기본적 연결 리스트 위 그림과 같이 단순히 데이터가 늘어져있는 것이 아닌 앞에 있는 원소가 그 다음 원소를 가리키는 형식의 리스트를 연결 리스트라고 한다. 하나의 원소와 그 다음 원소를 가리키는 방향이 하나씩 담겨있는 것을 노드(Node)라고 한다. 위 노드에서 67은 노드의 data, 화살표는 link를 의미 한다. 노드내의 데이터는 숫자뿐만 아니라 문자열, 또 다른 연결리스트 등이 올 수 있다. 위 연결..
기초 알고리즘 2023.01.20

파이썬) 알고리즘의 복잡도와 Big-O 표기법

알고리즘의 복잡도는 문제를 푸는데 있어서 얼만큼의 자원을 요구하는지에 대한 지표이며 두가지로 나뉘는데 시간 복잡도 : 문제의 크기와 이를 해결하는데 걸리는 시간 사이의 관계 공간 복잡도 : 문제의 크기와 이를 해결하는데 필요한 메모리 공간 사이의 관계 컴퓨터의 성능이 발전되면서 공간 복잡도보단 시간 복잡도의 중요성이 높아보일 수 있지만 자료주고 특성상 고려해야하는 경우도 있다. 빅오(Big-O) 표기법이란 빅오는 점근 표기법중의 하나이며, 어떤 함수의 증가양상을 다른 함수와의 비교로 표현한다. 알고리즘의 복잡도를 표현하는 흔히 쓰이고 이름처럼 영문 대문자 O를 이용해 표기한다. ex) O(n), O(1) .. 만약 입력의 크기가 n일 때 빅오표기법을 사용한다면 O(logn) : 입력의 크기의 로그에 비례..
기초 알고리즘 2023.01.19

파이썬) 재귀 알고리즘

재귀함수란 하나의 함수에서 자신을 다시 호출하여 작업을 수행하는 함수이다. ex) 1부터 n까지의 자연수들의 합을 구하는 함수를 재귀함수를 이용해 풀면 다음과 같이 풀 수 있다. def sum(n): print(n) if n u : return -1 mid = (l + u) // 2 if x == L[mid]: return mid elif x < L[mid]: return solution(L,x,l,mid-1) else: return solution(L,x,mid+1,u) 앞서 포스팅했던 이진 탐색 코드와 매우 유사하다. 우선 중앙값이 찾고자 하는 값 x와 같다면 중앙값을 리턴하고, x가 중앙값보다 작다면 이진 탐색에 의해 중앙값 이상 원소는 날라가게 된다. 이를 재귀적인 방법을 이용하기 위해 retur..
기초 알고리즘 2023.01.18

파이썬) 정렬(sort)과 탐색(search)

정렬이란 여러 원소로 주어진 데이터를 정해진 기준에 맞게 늘어놓는 작업을 말한다. 그중 대표적으로 sort가 있는데 파이썬에는 함수 sorted()와 메소드 .sort()가 있다. 이 둘의 차이점을 예시로 통해 보여주자면 a=[5,7,3,9,1] a.sort() a [1, 3, 5, 7, 9] 임의의 리스트 a를 a.sort()를 이용한 후 a를 출력하면 오름차순으로 정렬된 결과가 나온다. a=[5,7,3,9,1] sorted(a) a [5, 7, 3, 9, 1] 하지만 sorted(a)를 이용한 후 a를 출력하면 a는 그대로 출력되는 것을 볼 수 있다. 이처럼 sort는 기본적으로 오름차순으로 데이터들을 정렬하고, 그 외 정렬 기준을 여러 코드를 이용해 설정할 수 있다. 탐색이란 여러 원소로 이루어진 ..
기초 알고리즘 2023.01.17

파이썬) 선형 배열 실습

1번 문제) 정렬된 리스트에 원소 삽입 문제 설명 리스트 L 과 정수 x 가 인자로 주어질 때, 리스트 내의 올바른 위치에 x 를 삽입하여 그 결과 리스트를 반환하는 함수 solution 을 완성하세요. 인자로 주어지는 리스트 L 은 정수 원소들로 이루어져 있으며 크기에 따라 (오름차순으로) 정렬되어 있다고 가정합니다. 예를 들어, L = [20, 37, 58, 72, 91] 이고 x = 65 인 경우, 올바른 리턴 값은 [20, 37, 58, 65, 72, 91] 입니다. 힌트: 순환문을 이용하여 올바른 위치를 결정하고 insert() 메서드를 이용하여 삽입하는 것이 한 가지 방법입니다. 주의: 리스트 내에 존재하는 모든 원소들보다 작거나 모든 원소들보다 큰 정수가 주어지는 경우에 대해서도 올바르게 처..
기초 알고리즘 2023.01.17

파이썬) 선형 배열(linear array)

선형 배열: 데이터들이 선처러 일렬로 늘어선 형태, 대표적으로 파이썬의 list라는 데이터형이 있다. ex) L=[12,32,65,89,98] 파이썬의 리스트는 다른 프로그래밍 언어의 배열보다 능통성이 있다. 그 예로 파이썬 리스트는 숫자,문자가 올 수 있다. M=['apple',5,4] M ['apple', 5, 4] 파이썬에서 리스트가 생성되면 원소의 순서를 나타내는 숫자도 생성되는데 이를 index라 한다. 파이썬에선 왼쪽부터 첫번째 원소 index는 0으로 시작한다. L=[12,32,65,89,98] L[0],L[1],L[2],L[3],L[4] (12, 32, 65, 89, 98) 오른쪽부터 index를 출력하려면 -1부터 시작하면 된다. L[-1],L[-2],L[-3],L[-4],L[-5] (9..
기초 알고리즘 2023.01.16
1 2 3 4 5 6 7
더보기

티스토리툴바