이분탐색 정렬되어 있는 배열에서 찾고자 하는 x를 가지고 배열을 둘로 나누어가면서(이분) 탐색하는 방법 정렬의 특성을 극대화한 알고리즘이다. 만약 N길이의 배열에서 x이하의 가장 큰 수를 찾는다는 문제가 있을 때 배열의 모든요소를 하나씩 탐색한다면 최대 시간복잡도는 O(N)이 나올 것이다. 하지만 이분탐색을 이용하면 처음부터 끝까지 순차적으로 배열을 탐색하지 않고, 탐색 시작지점(L, Left)과 끝지점(R, Right)을 설정해서 중간지점(mid)을 탐색하여 빠르게 탐색한다. 만약 중간지점의 값이 x이상이라면 그 이후의 값들은 고려할 필요가 없어진다. 반대로 x이하라면 그 이전의 값들을 고려할 필요가 없어진다. 이를 보장하기 위해서는 배열이 정렬되어있어야한다. 그러면 탐색의 끝지점(R)을 중간지점의 바..
문제 설명 n개의 음이 아닌 정수들이 있습니다. 이 정수들을 순서를 바꾸지 않고 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다. -1+1+1+1+1 = 3 +1-1+1+1+1 = 3 +1+1-1+1+1 = 3 +1+1+1-1+1 = 3 +1+1+1+1-1 = 3 사용할 수 있는 숫자가 담긴 배열 numbers, 타겟 넘버 target이 매개변수로 주어질 때 숫자를 적절히 더하고 빼서 타겟 넘버를 만드는 방법의 수를 return 하도록 solution 함수를 작성해주세요. 첫 번째 풀이 DFS를 이용한 풀이 answer = 0 def graph(signs, numbers, target): global ans..
https://www.acmicpc.net/problem/4779 4779번: 칸토어 집합 칸토어 집합은 0과 1사이의 실수로 이루어진 집합으로, 구간 [0, 1]에서 시작해서 각 구간을 3등분하여 가운데 구간을 반복적으로 제외하는 방식으로 만든다. 전체 집합이 유한이라고 가정하고, www.acmicpc.net import sys input = sys.stdin.readline def cantorian(num): if num == 1: return '-' l = num//3 str = cantorian(l) return str + ' '*l + str while True: try: n = int(input()) num = 3**n print(cantorian(num)) except: break 재귀적으로..
7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 출발지가 여러개인 bfs 문제이다. 박스 안에 토마토의 상태를 -1, 0, 1로 표현하고 (-1 : 토마토 없음. 0 : 안익은 토마토. 1: 익은 토마토) 토마토가 전부 익을때 까지 걸리는 일수를 구한다. 익은 토마토는 하루에 상하좌우 한 칸씩 영향을 미쳐 주변 토마토가 익게한다. 풀이과정 값 입력 및 변수 초기화 from collections import deque dx = [1, -1, 0, 0] dy = [0, 0, 1, -1] M, N ..
다이나믹프로그래밍에 첫 번째 문제이다. 다이나믹 프로그래밍, 즉 동적계획법은 메모리를 더 사용하지만 실행 시간을 줄일 수 있는 기법이다 1. 큰 문제를 작은 문제로 나눌 수 있고 2. 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일할 때 동적 계획법을 사용할 수 있다. (참고 : https://techblog-history-younghunjo1.tistory.com/183) 재귀용법을 사용해서 피보나치 수를 구현하게 되면 작은 수에 대한 피보나치 함수를 반복해서 호출하게 된다. fibonacci(3)을 호출하면 다음과 같은 일이 일어난다. fibonacci(3)은 fibonacci(2)와 fibonacci(1) (첫 번째 호출)을 호출한다. fibonacci(2)는 fibonacci(1) ..
안정정렬은 정렬을 할 때 중복된 값이 있다면 그 순서를 유지하며 정렬하는 것이고 불안정정렬은 중복된 값들의 순서를 유지하지 않고 정렬하는 것이다. 안정 정렬 알고리즘 삽입정렬 버블정렬 병합정렬 불안정 정렬 알고리즘 선택정렬 퀵정렬 힙정렬 파이썬의 기본 제공 정렬 함수 sort와 sorted는 안정 정렬이다. 백준 11650 좌표정렬하기 문제에서 유용하게 사용했다 n = int(input()) lst = [] for _ in range(n): lst.append(list(map(int, input().split()))) lst = sorted(lst) for v in lst: print(v[0], v[1])
퀵 정렬 분할정복을 이용한 정렬의 방법 합병정렬과 달리 분할의 과정에서 정렬이 일어난다! 배열에서 한 요소를 피봇으로 설정하고 그 요소보다 작은 수들은 왼쪽, 큰 수들은 오른쪽으로 나누는 것이다 간단하게 엑셀로 정렬과정을 나타내보았다 피봇은 어떤 것이 설정되어도 상관없으므로 첫번째 요소로 설정하고 5보다 작은 수들은 왼쪽으로 큰 수들은 오른쪽으로 보냈다 왼쪽 오른쪽으로 나눈후 나뉜 배열에서 또 다시 첫번째 요소를 피벗으로 하여 분할을 진행한다. 모든 배열의 길이가 1이 될때까지 분할을 진행하면 정렬이 완료된다. 나누는 과정에서 정렬이 이루어지니 합병과정에 별다른 로직처리를 하지 않아도 된다 평균적으로 nlogn 시간 복잡도를 가지고 순차적 또는 역순으로 정렬된 배열의 경우에는 최악의 시간복잡도 n^2을 ..
카운팅 정렬을 이용해서 푸는 문제이다 카운팅 정렬은 입력의 범위가 정해져있을때 사용할 수 있는 아주 빠른 정렬 방법으로, O(N)의 시간복잡도를 가지는 정렬방법이다. n = int(input()) result=[0 for i in range(n+1)] for i in range(n) : temp = int(input()) result[temp] += 1 for idx in range(1, n+1) : length = result[idx] for n in range(result[idx]): print(idx) 제일 처음 카운팅 정렬을 알고 풀었던 코드이다. 정렬은 되지만 메모리 초과로 실패했다. 이 문제에서 가장 주의해야할 것은 메모리이다. 그래서 다른 코드를 찾아보기전에 먼저 변수 선언을 최대한 줄여보았..
