정신차려 하프물범 정신차려 하프물범

코딩테스트의 정렬 알고리즘이 사용되는 경우는 크게 3가지 유형으로 나눌 수 있다.1. 정렬 라이브러리로 풀 수 있는 문제2. 정렬 알고리즘의 원리에 대해 묻는 문제: 선택 정렬, 삽입 정렬, 퀵 정렬 등의 원리를 알아야 풀 수 있음.3. 더 빠른 정렬이 필요한 문제: 퀵 정렬 기반의 정렬 기법으론 풀 수 없고, 계수 정렬 등 다른 정렬 알고리즘을 이용하거나 문제에서 기존에 알려진 알고리즘의 구조적인 개선을 거쳐야 풀 수 있는 문제.정렬 라이브러리또한 병합 정렬과 삽입 정렬이 합해진 방식이므로, 비교하기 위해 기본 정렬 방식부터 정리하려 한다.1. 정렬 알고리즘정렬 정의 및 특징정렬(sorting)이란 데이터를 특정한 기준에 따라 순서대로 나열한 것을 말한다.정렬 알고리즘으로 데이터를 정렬하면 이진 탐색(..

이 문제는 DFS로 풀라고 나와있지만 BFS가 익숙한 나머지 BFS로 하다 한참이 걸렸다.. '0'인 노드들로 묶인 묶음을 카운트 하는 문제로 이러한 묶음을 찾아주는 프로그램은 DFS로 풀면 간단하다. (특정 시작 노드로 부터 깊이 들어가기 때문, BFS는 연결된 노드마다 주변을 살피느라 더 오래걸린다) BFS 코드 from collections import deque def bfs(matrix, start): # 상 하 좌 우 dx = [-1, 1, 0, 0] dy = [0, 0, -1, 1] queue = deque([start]) while queue: x, y = queue.popleft() for i in range(4): nx = x + dx[i] ny = y + dy[i] if..

탐색(Search)이란 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정이다. 프로그래밍에선 그래프, 트리 등 자료구조 안에서 탐색을 하는 문제를 많이 다룬다. 대표적인 탐색 알고리즘: DFS, BFS 필요한 자료구조 기초 DFS, BFS 를 이해하기 위해선 스택, 재귀함수, 큐에 대해 알아야한다. 스택, 큐, 재귀함수 스택 선입후출(FILO)/후입선출(LIFO)의 구조 파이썬에서 스택을 이용할 땐 별도의 라이브러리를 사용할 필요가 없다. 기본 리스트에서 append(), pop() 메서드 이용. 큐 선입선출(FIFO) 구조 파이썬에서 큐를 구현할 땐 collections 모듈에서 제공하는 deque 자료구조를 사용. deque란 스택, 큐의 장점을 모두 채택한 구조인데, 데이터를 넣고 빼는 속도가 일..

아이디어를 코드로 바꾸는 구현 구현(implementation) 이란 '머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정'이다. 어려운 구현문제는 어떤 유형인가? 알고리즘은 간단한데, 코드가 지나칠 만큼 길어지는 문제 특정 소수점 자리까지 출력하는 문제 문자열이 입력으로 주어졌을 때 한 문자 단위로 파싱하는 문제 등 -> 대체로 사소한 조건 설정이 많은 문제일수록 코드로 구현하기 까다롭다. 그러므로 구현 문제일수록 파이썬이 빛을 발하는 언어이다. 예를 들면, N개의 원소가 들어있는 리스트에서 R개의 원소를 뽑아 한 줄로 세우는 모든 경우(순열)를 구해야하는 문제를 만난다면 무작정 기능을 짜는 것 보다 파이썬의 itertools 와 같은 표준 라이브러리로 쉽게 해결 가능하다 1. 완전 탐색, 시뮬레이션 [이..

복잡도 알고리즘의 성능을 나타내는 척도 크게 아래 2가지를 의미하며, 둘은 trade-off 관계를 가진다. 시간 복잡도: 알고리즘을 위해 필요한 연산의 횟수 공간 복잡도: 알고리즘을 위해 필요한 메모리의 양 시간 복잡도 시간 복잡도를 표현할 때는 빅오(Big-O) 표기법을 사용한다. 간단히 정의하면, 가장 빠르게 증가하는 항만을 고려하는 표기법이다. 예로 아래 소스코드에서 가장 영향력이 큰 부분은 N에 비례하는 연산을 수행하는 반복문 부분이므로 시간을 O(N) 으로 표기한다. array = [3, 5, 1, 2, 4] summary = 0 for x in array: summary += x print(summary) #15