알고리즘

프로그래밍/자료구조 & 알고리즘
백트랙킹 기법 정리
백트랙킹(backtracking)이 무엇인가? 뭐 탐색을 하면서 그냥 필요없는 경로는 손절치고 가지치기하는 알고리즘이다. DFS랑 유사하다 이정도로 대충 알고있었다. 따라서 이번에 공부하면서 정리해보려한다. ✏️ Backtracking 정의는 이렇다. '해를 찾는 도중에 해가 아니어서 막히면 다시 되돌아가서 다시 해를 찾는 기법.' 이걸 가지치기(pruning)이라고 하는데 가지치기를 얼마나 잘하느냐에 따라 효율성이 결정된다. 구현방식? DFS등으로 모든 경우의수를 탐색하는 과정에서 조건문등으로 답이 절대 될 수 없는 상황을 정의하고 그런 상황에서는 탐색을 중지시키고 다시 처음으로 가서 다른 경우를 탐색하게끔 구현할 수 있다. 트리에 대해서 DFS 실시 각 노드가 유망한지(promising) 점검 해당 ..
→2022.02.19
프로그래밍/백준
백준 1915: 가장 큰 정사각형 해설- python
✏️ 문제 https://www.acmicpc.net/problem/1915 1915번: 가장 큰 정사각형 첫째 줄에 n, m(1 ≤ n, m ≤ 1,000)이 주어진다. 다음 n개의 줄에는 m개의 숫자로 배열이 주어진다. www.acmicpc.net ✏️ 풀이 시작점에서 대각선(n,m)방향으로 뻗어나가면서 사각형이 만들어지는지를 확인한다. [i][j]를 기준으로 [i-1][j], [i][j-1], [i-1][j-1]이 모두 0이 아니라면 최소사각형(2x2)가 만들어졌다는 뜻이다. 아래 코드대로 인풋 매트릭스에 값을 더해가다 보면, 이런식으로 매트릭스가 채워질거다. 가장 큰 값이 정사각형의 한변의 길이가 되고 크기는 그 길이의 제곱이된다. n,m=map(int,input().split()) matrix=..
→2022.02.19
프로그래밍/자료구조 & 알고리즘
[Python & Algorithm] Dynamic Programming(동적프로그래밍)
✏️ Dynamic Programming 큰 문제를 작은 문제로 나누어 푸는 문제를 이야기한다. 이름에 의미는 없다. 그냥 말이 멋있어서 이렇게 지었다고 한다. 1) 분할정복과의 차이 '작은 문제가 중복이 일어나는지 아닌지' 에 차이가 있다. 분할정복은 큰 문제를 해결하기 어려워서 단지 작은 문제로 나누어서 푸는 방법이다. 특징은 작은 문제에서 반복이 일어나는 부분이 없다는 점이다. 하지만 동적프로그래밍은 작은 부분문제들이 반복되는 것을 이용해 문제를 풀어낸다. 2) 다이나믹 프로그래밍의 방법 모든 작은 문제들은 한번만 풀어낸다. 따라서 정답을 구한 작은 문제를 어딘가에 메모해둔다. 다시 그보다 큰 문제를 풀어나갈 때 똑같은 작은 문제가 나타나면 앞서 메모한 작은 문제의 결과값을 이용한다. 3) 다이나믹..
→2022.01.22

• 이전
• 1
• 다음