본문 바로가기

Algorithm & Data Structure5

[알고리즘] 이분탐색, 투포인터 1. 이분탐색과 투포인터에 대하여 이분탐색이란? 정렬된 데이터에 대해 중간 지점의 값을 확인함으로써 탐색 범위를 절반으로 줄여나가는 탐색 방법. 시작점, 중간점, 끝점을 이용하여 탐색 범위를 조절하고, 중간값과 찾고자 하는 값을 비교하여 탐색 범위를 줄여나간다. 투포인터란? 배열이나 리스트에서 두 개의 포인터를 사용하여, 주어진 조건(ex. 합이나 차이 등)에 부합하는 요소의 조합을 찾는 방법. 두 개의 포인터(보통 시작인덱스와 끝인덱스를 활용)를 이동시키며 주어진 조건을 만족하는 요소를 찾는다. 조건에 따라 하나의 포인터만 이동시킬 수 있고, 두 포인터를 동시에 이동시켜야 하는 경우도 있다. 2. 두 알고리즘의 공통점과 차이점 공통점 1. 탐색 범위를 줄인다 : 두 알고리즘 모두 문제의 탐색 범위를 줄.. 2024. 4. 5.
[자료구조] Heap에 대하여 1. 힙(Heap)이란? 힙은 완전 이진 트리 기반의 자료구조로, 우선순위 큐를 구현하는데 주로 사용된다. 각 노드는 자식 노드보다 큰(최대 힙) 또는 작은(최소 힙) 값을 가지며, 이러한 특성을 힙 속성(heap property)이라 한다. 힙은 두 가지 주요 유형으로 분류된다. 최소 힙(Min-Heap): 각 부모 노드의 값이 자식 노드의 값보다 작거나 같아야 하며, 따라서 루트에는 힙에 있는 최솟값이 위치. 최대 힙(Max-Heap): 각 부모 노드의 값이 자식 노드의 값보다 크거나 같아야 하며, 따라서 루트에는 힙에 있는 최대값이 위치. 2. 그러면 힙은 왜 사용하지?? 일반적인 배열에서 최솟값이나 최댓값을 찾기 위해서는 Ο(n)만큼 시간이 걸린다. (배열의 길이가 최대 n개이기 떄문에) 하지만 .. 2024. 4. 4.
[알고리즘] BOJ 15686번 제출 코드 회고(Python) https://www.acmicpc.net/problem/15686 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net 문제를 요약하자면 'M개의 치킨집을 뽑아 모든 집에서 각각의 최소 치킨 거리에 맞는 치킨집을 찾아 최소 치킨 거리의 합을 구하라'는 문제였다. 문제를 보고 'DFS와 백트래킹을 이용하여 풀면 되겠다'라고 생각을했고 해당 개념의 알고리즘 문제를 푼 지 오래됐지만 호기롭게 도전해보았다. import sys input = sys.stdin.readline N, M = map(int.. 2024. 4. 3.
[알고리즘] Python zip함수와 2차원 배열 회전에 대하여 1. zip()이란? : 인덱스에 있는 요소들을 결합하여 새로운 iterable한 객체를 생성하는 함수이다. 코드로 빠르게 확인해 보자! nums = [1, 2, 3] strings = ["a", "b", "c"] new_obj = zip(nums, strings) print(type(new_obj)) # print(list(new_obj)) #[(1, 'a'), (2, 'b'), (3, 'c')] nums 배열과 strings 배열에서 각각의 인덱스에 맞게 요소들이 매핑되어 새로운 객체를 생성해 낸 것을 볼 수 있다. 단, 주의해야 할 점이 있는데 만약 서로 다른 두 길이의 객체를 매핑시키려 하면 가장 짧은 길이의 객체를 기준으로 매핑을 하게 되고 나머지는 버려진다. nums = [1, 2, 3, 4,.. 2024. 4. 1.
[알고리즘] Recursion 1. 재귀함수란? ‘어떤 사건이 자기 자신을 포함하고 다시 자기 자신을 재참조하여 정의할 때’를 재귀적(recursive)라고 한다. 즉, 자기 자신과 똑같이 동작하는 함수를 재귀함수라고 한다. 2. 재귀함수는 왜 쓰는지 알고리즘 자체가 재귀함수를 쓰는 것이 자연스러울 때 코드의 가독성이 좋아지기 때문에. 변수 사용을 줄여줄 수 있다.(=mutable state를 줄일 수 있다) mutable state : 변경 가능한 상태(dict의 value, 리스트) 3. 재귀함수는 언제 쓰는지 동일한 로직이 반복될 때 재귀 함수로 구현이 가능한 것은 while문이나 for문으로도 구현이 가능하다. (물론 그 반대도 가능) 4. 재귀함수의 동작 원리 재귀함수의 가장 대표적인 사용 예제 # 팩토리얼 def facto.. 2024. 3. 29.

티스토리툴바