728x90 분류 전체보기302 [Algorithm] 4. 그래프 탐색 알고리즘 [Algorithm] 4. 그래프 탐색 알고리즘 탐색이란 많은 양의 데이터 중 원하는 데이터를 찾는 과정이다 대표적인 그래프 탐색 알고리즘은 DFS, BFS가 있다. DFS/BFS는 코테에서 매우 자주 등장하는 유형이기에 반드시 숙지해야 한다. 1. 필수 개념 자료구조의 기초 개념으로 스택과 큐가 있으며, 두 핵심적인 함수로 구성된다. Push(삽입) : 데이터를 삽입한다. Pop(삭제) : 데이터를 삭제한다. 스택과 큐는 오버플로우, 언더플로우를 고민해야 한다. 오버플로우는 자료구조가 수용할 수 있는 데이터 크기를 가득 찬 상태에서 삽입 연산할 때 발생 언더플로우는 데이터가 없는 상태에서 삭제 연산을 할 때 발생 2022. 4. 27. [Algorithm] 3. 구현 [Algorithm] 3. 구현 1. 개념과 접근 1) 개념 머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정이다. problem - thinking - soultion 문제가 있고, 그것을 생각해서 해결점을 제시하는 것, 모든 문제가 구현 유형의 문제라고 할 수 있다. 모든 문제가 구현의 과정을 거쳐야 한다. 피지컬이 좋다 => 구현을 잘한다. (기초 체력과 같다.) 다만 협의적으로 볼 때, 구현이 어려운 문제를 ‘구현’ 유형의 문제라고 한다. 2) 접근 방법 풀이를 떠올리는 것은 쉽지만, 소스코드로 옮기기 어려운 문제가 이에 해당한다. ex. 알고리즘은 간단한데 코드가 지나칠 만큼 길어지는 문제 실수 연산을 다루고, 특정 소수점 자리까지 출력해야 하는 문제 문자열을 특정한 기준에 따라서 끊어 처리해야 .. 2022. 4. 27. [Algorithm] 2. 그리디 알고리즘(Greedy) [Algorithm] 2. 그리디 알고리즘(Greedy) 1. 개념과 접근 방법 1) 개념 : 현재 상황에서 지금 당장 좋은 것만 고르는 방법이다. 2) 접근 방법 일반적으로 문제를 풀기 위한 최소한의 아이디어를 떠올릴 수 있는 능력을 요한다. 특정 문제를 만났을 때 단순히 현재 상황에서 가장 좋아 보이는 것만을 선택해도 문제를 풀 수 있는지를 파악할 수 있어야 한다. 이를 위해 정당성 분석이 가장 중요하다. 단순히 가장 좋아 보이는 것을 반복적으로 선택해도 최적의 해를 구할 수 있는 지 검토하여야 한다. 다양한 아이디어를 떠올려보면서 고민을 해야 하고 창의적 발상을 통한 가정과 그 풀이 방법에 대한 검증이 필요하다. 보통 ‘최소’의 횟수, 금액, 개수 등을 요구한다. 그리디는 최적의 해를 보장할 수 없.. 2022. 4. 27. [Algorithm] 1. 시간 복잡도, 공간 복잡도 [Algorithm] 1. 시간 복잡도, 공간 복잡도 1. 복잡도란? 더보기 알고리즘의 성능을 나타내는 척도 얼마나 복잡한지를 의미한다. 높아질 수록 좋지는 않은 것이다. 알고리즘은 컴퓨터 속에서 돌아간다. 그렇기 때문에 얼마나 더 오래 걸리느냐, 얼마나 더 큰 용량을 차지하느냐로 복잡도를 계산한다. 이를 각각 시간 복잡도, 공간 복잡도라고 한다. 시간 복잡도와 공간 복잡도는 일종의 거래 관계에 있다. 마치 역세권을 희망하면 월세가 높아지고, 월세를 낮추려면 역세권을 포기해야 하는 것처럼 메모리를 더 사용하는 대신 시간을 줄일 수도 있고 시간을 더 쓰는 대신 메모리 용량을 작게 사용할 수 있다. 이 계산은 우리가 유한한 성능을 가진 컴퓨터와 기기들을 가지고 있기 때문에, 효율적이고 더 빠르고, 더 경제적.. 2022. 4. 27. [백준] 10816 숫자 카드 2 python 알고리즘 문제 문제 10816. 숫자 카드 2 1. 나의 코드와 발상 과정 (1) 제출 답안 from bisect import bisect_left, bisect_right import sys n = int(input()) num_list = list(map(int, sys.stdin.readline().split())) m = int(input()) find_list = list(map(int, sys.stdin.readline().split())) num_list.sort() def count_by_range(array, left, right): right_index = bisect_right(array, right) left_index = bisect_left(array, left) return right_ind.. 2022. 4. 25. [백준] 1920 수 찾기 python 알고리즘 문제 문제 1920. 수 찾기 1. 나의 코드와 발상 과정 import sys n = int(input()) num_list = list(map(int, sys.stdin.readline().split())) m = int(input()) find_list = list(map(int, sys.stdin.readline().split())) num_list.sort() def count_by_range(array, target, start, end): if start > end: return 0 mid = (start + end) // 2 if array[mid] == target: return 1 elif array[mid] > target: return(count_by_range(array, target, .. 2022. 4. 25. 이전 1 ··· 43 44 45 46 47 48 49 ··· 51 다음 728x90
