전체 글

[Algorithm] BackTracking(백트래킹) 알고리즘

백트래킹 알고리즘은 기본적으로는 완전탐색이면서 DFS에서 가능성이 없는 경우를 가지치기하면서 탈출조건을 만들어 DFS의 성능을 높이는 알고리즘 입니다. 백트래킹에 대해 설명한 블로그의 링크를 걸어놓겠습니다. https://velog.io/@mmindoong/알고리즘-백트래킹BackTracking [알고리즘] 백트래킹(BackTracking) 백준 문제를 풀면서 알고리즘도 같이 정리해두면 좋을 것 같아서 정리해보겠다-! 💡 백트래킹 백트리킹이란 "가능한 모든 방법을 탐색한다"의 아이디어를 가진다. 즉, 백트래킹은 현재 상태에 velog.io 백트래킹의 입문문제인 N과 M 시리즈의 1번 문제입니다. https://hgk5722.tistory.com/84 [백준] 15649 파이썬(python) : N과 M ..

[백준] 2309 파이썬(python) : 일곱 난쟁이

https://www.acmicpc.net/problem/2309 2309번: 일곱 난쟁이 아홉 개의 줄에 걸쳐 난쟁이들의 키가 주어진다. 주어지는 키는 100을 넘지 않는 자연수이며, 아홉 난쟁이의 키는 모두 다르며, 가능한 정답이 여러 가지인 경우에는 아무거나 출력한다. www.acmicpc.net import sys height = [ int(sys.stdin.readline()) for _ in range(9)] total = sum(height) for i in range(9): for j in range(i+1, 9): if 100 == total - (height[i]+height[j]): #1 num1 = height[i] #2 num2 = height[j] height.remove(num..

[Algorithm] 다이나믹 프로그래밍(DP) - 탑다운, 바텀업

컴퓨터의 연산 속도에는 한계가 있고 그 속도를 단축 시켜줄 방법이 필요합니다. 연산속도와 메모리 공간을 효율적으로 활용할 수 있는 알고리즘 방법이 있습니다. 다이나믹 프로그래밍 우리말로는 동적 계획법이라고 불리우는 알고리즘입니다. 다이나믹 프로그래밍을 이용하여 풀 수 있는 문제를 알아보겠습니다. 피보나치 수열 : 인접 한 두 수를 더해서 다음 수를 구하는 수열 1 1 2 3 5 8 13 21 34 55 89.... 피보나치 수열 코드 def fibo(x): if x == 1 or x == 2: return 1 else: return fibo(x-2) + fibo(x-1) print(fibo(10)) 결과) 55 10을 수행하는데 시간이 조금 걸린다. 더 빠르게 수행하기 위해 다이나믹 프로그래밍을 사용할 ..

[Python] 2차원 배열과 3차원 배열 작성법

2차원 배열 1. 행 3, 열 4이고 모든 값이 0인 2차원 그래프 n, m = 3, 4 graph = [ [0] * m for _ in range(n) ] print(graph) 결과) [[0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0]] 높이 3의 길이 4인 그래프가 완성됩니다. x, y 값이 3, 4이므로 n, m = x, y라 하면 y를 안쪽에 x를 바깥쪽에 입력해 줍니다. graph = [ [0]* y for _ in range(x) ] 2. 3행 4열의 값을 입력 받는 경우 n, m = 3, 4 graph = [ list(map(int, input().split())) for _ in range(n) ] 3차원 그래프 graph[a][b][c]의 값을 찾아야 하는 경우 ..

[Python] insert연산

insert() array.insert(i, num) 형태가 기본형입니다. i는 인덱스의 위치이고 num은 넣어줄 원소입니다. 이렇게 해서 인덱스 i의 앞에 원소 num을 넣어주게 됩니다. ex) array = [ 1, 2, 3, 4, 5, 6 ] array.insert(0, 9) print(array) 결과) [9, 1, 2, 3, 4, 5, 6] 인덱스 0의 앞에 원소 9를 넣어줬습니다. ex) array = [ 1, 2, 3, 4, 5, 6 ] array.insert(-1, 9) print(array) 결과) [1, 2, 3, 4, 5, 9, 6] 인덱스 -1은 마지막 인덱스를 나타내는데 인덱스 -1의 앞에 원소 9를 삽입해줬습니다. 마지막 인덱스에 넣는 방법) array = [ 1, 2, 3, 4..

[Math] 음수 모듈러 연산 파이썬과 C언어 방식 - 정리(feat.윈도우 계산기)

프로그래밍 언어에 따라 음수 모듈러 연산을 처리하는 방식이 다릅니다. 언어마다 방식이 다르기 때문에 혼동이 생기므로 혼란을 피하기 위해 차이를 알아야 합니다. 자주 사용하는 언어는 c언어의 방식과 파이썬의 방식이 있으므로 두 언어의 따라 차이점을 설명하고 예제를 통해 간단한 계산하는 방식을 알아보겠습니다.  1. 파이썬 기준  프로그래밍 언어는 파이썬 기준입니다.(설명을 위한 계산기는 윈도우 공학용 계산기입니다)  파이썬은 나머지 연산 시 몫에 대해 내림 처리(Floored)를 하기 때문에 아래와 같은 결과가 나오게 됩니다.  나머지는 두 정수의 나눗셈 이후 딱 떨어지지 않은 남은 값입니다.a = q X d + r0   -5를 3으로 나머지 연산을 하면 값이 얼마일까요?    1이 됩니다.   -5 = ..