Machineboy空

분할정복(Divide and Conquer)Divide : 큰 문제를 작은 문제로 분할한다.기저사례(base case)를 잘 설정하여 일정 기준 이상 분할되지 않도록 해야한다.Conquer: 작은 문제의 답을 모아 큰 문제의 답을 구한다.일반적으로 재귀로 구현한다.  백트래킹(backtracking)답이 될 수 없는 경우는 탐색 대상에서 제외하여 효율적으로 답을 구하는 알고리즘가지치기(pruning)를 통해 연산량의 유의미하게 줄여줌가지치기를 사용하기 위해서는 현재 상태에서 도달할 수 있는 상태가 모두 답이 될 수 없음을 보여야함.정확한 시간 복잡도를 구하기 어려움 분할 정복백트래킹주로 재귀적인 방식으로 해결하위 문제를 해결하고 결과를 결합하여 문제를 해결문제 해결을 위해 모든 가능한 선택을 시도한 후,..

1. 회문(Palindrome)ex) "소주만병만주소", "수박이박수", "Madam, I'm Adam", "1234321" 회문을 판단하는 방법? 2. 올바른 괄호 문자열(VPS = Valid Parenthesis String)ex) (()), (())()보통은 스택(Stack)을 사용해서 해결')'가 입력될 때마다, 스택에 있는 '('를 하나씩 지운다. 이때 스택(top)이 비어있거나 '('이 없으면 올바른 괄호 문자열이 아님모든 문자열을 순회한 뒤, 스택이 비어있으면 올바른 괄호 문자열이고 비어있지 않으면 올바르지 않은 괄호 문자열임

for this particular purpose라는 뜻의 라틴어 특정 상황에서만 정답이 되고 일반화될 수 없는 해답을 말한다.일반화할 수 없고 재사용이 거의 불가능하다!예시 문제https://machineboy0.tistory.com/223 1813: 논리학 교수 - Ad Hochttps://www.acmicpc.net/problem/1813machineboy0.tistory.com

백준 문제 리스트17466231226091929코딩테스트에서 나올 수 있는 마지막 수학 이론이라고 한다.유클리드 호제법 많이 들어는 봤는데 직접 빼면서 구하는 방법이 참 신기했다.최대공약수를 정석으로 구하지 않고 호제법으로 구하면 시간복잡도가 현저히 낮아짐.

비트연산 활용 idx번째 비트 끄기 S &= -(1

완전탐색은 모든 경우의 수를 탐색하는 것이고, 백트래킹은 완전 탐색을 기반으로 하되, 불필요한 연산을 좀 줄이는 것. 경우의 수는 순열과 조합 + 로직으로 풀린다. 이를 재귀 또는 반복문으로 구현할 수 있다. 원상복구 타이밍 잘 처리하기! 상태값이 그 다음 경우의 수에 영향미치지 않게 처리해주는 것 완전 탐색 (brute force, exhaustive key search) 모든 경우의 수를 탐색하는 알고리즘 순열or 조합 + 로직 보통 1억 미만까지는 컴퓨터를 믿고 넘겨라. 예제) https://machineboy0.tistory.com/183 14502 : 연구소 - DFS, deep copy https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바..

https://blog.naver.com/jhc9639/222289089015 [알고리즘 강의] 2주차. 그래프이론, 인접행렬, 인접리스트, DFS, BFS, 트리순회 이번주차는 그래프이론과 DFS(깊이우선탐색), BFS(너비우선탐색) 그리고 트리순회인 preorder, inord... blog.naver.com 트리 순회(Tree traversal)은 트리 구조에서 각각의 노드를 정확히 한 번만 체계적으로 방문하는 과정 노드를 방문하는 순서에 따라 후위 순회 (postorder traversal) 전위 순회 () 중위 순회 () 보통 설명할 때 이진트리 기반으로 설명하지만 다른 모든 트리에서 일반화시킬 수 있다. *이진트리(binary tree) : 각각의 노드와 자식 노드 수가 2개 이하로 구성되어 ..