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

이진 탐색탐색의 범위를 반으로 줄여나가면서 데이터를 빠르게 탐색하는 기법.특징이진 탐색은 배열 내부의 데이터가 정렬되어 있을 때만 사용데이터의 개수가 1000만개를 넘어가거나 탐색 범위의 크기가 2000만-1000억 이면 이진 탐색으로 접근하길 권한다.3가지 변수(시작점, 끝점, 중간점)가 사용된다.시작점, 끝점 : 탐색하고자 하는 범위를 나타내기 위해 사용중간점 : 중간점에 있는 데이터와 찾고자 하는 데이터가 일치하는지 비교기위해 사용.시간 복잡도: O(logN) -> 한 번 비교때마다 반 씩 줄어드니까!소스코드 (재귀, 반복문)1. 재귀# 이진 탐색 소스코드 구현 (재귀 함수)def binary_search(array, target, start, end): if start > end: ..

코딩테스트의 정렬 알고리즘이 사용되는 경우는 크게 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..

1. 문제 https://www.acmicpc.net/problem/1541 1541번: 잃어버린 괄호 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 www.acmicpc.net 2. 문제 풀이 첫 번째 '-' 이전의 값은 더하고, 그 이후의 값은 모두 빼준다. '-', '+' 를 기준으로 나누고, '-'의 위치를 기준으로 숫자들의 합을 주해주면 되기 때문에 필요하기 때문에 정규식(re)이 필요했다. 정규식 정규식(re) 패턴 참고 사이트 []: 안에 들어간 문자를 기준으로 모두 구분한다. ex) '[AB]' : A또는 B를 기준으로 나눈다. (): 구분자..

탐색(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

브루트 포스(brute force) 완전탐색 알고리즘. 즉, 가능한 모든 경우의 수를 모두 탐색하면서 요구조건에 충족되는 결과만을 가져온다. 이 알고리즘의 강력한 점은 예외 없이 100%의 확률로 정답만을 출력한다. 알고리즘 설계의 가장 기본적인 접근 방법은 해가 존재할 것으로 예상되는 모든 영역을 전체 탐색하는 방법이다. 선형 구조(저장되는 자료의 전후관계가 1:1 )를 전체적으로 탐색하는 순차탐색, 비선형 구조(데이터 항목 사이의 관계가 1:n 또는 n:m (트리, 그래프)) 전체를 탐색하는 깊이 우선 탐색(DFS), 너비 우선 탐색(BFS) *너비 우선 탐색은 브루트 포스와 관련이 깊고, 깊이 우선 탐색은 다음에 작성될 백트래킹과 관련이 깊음 문제해결 방법 주어진 문제를 선형 구조로 구조화한다. 구..