전체 글

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

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

[백준] 3085: 사탕 게임

https://www.acmicpc.net/problem/3085 3085번: 사탕 게임예제 3의 경우 4번 행의 Y와 C를 바꾸면 사탕 네 개를 먹을 수 있다.www.acmicpc.net import sysdef solution(): n = int(sys.stdin.readline()) board = [ list(sys.stdin.readline().strip()) for _ in range(n) ] max_length = 1 def max_candy_count(board, n): max_count = 1 for i in range(n): row_count, col_count = 1, 1 for j in range(n..

[백준] 2309: 일곱 난쟁이

https://www.acmicpc.net/problem/2309 2309번: 일곱 난쟁이아홉 개의 줄에 걸쳐 난쟁이들의 키가 주어진다. 주어지는 키는 100을 넘지 않는 자연수이며, 아홉 난쟁이의 키는 모두 다르며, 가능한 정답이 여러 가지인 경우에는 아무거나 출력한다.www.acmicpc.net  import sysfrom itertools import combinationsdef solution(): arr = [] for i in range(9): arr.append(int(sys.stdin.readline())) for com in combinations(arr, 7): if sum(com) == 100: for height in so..

[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..