Yejin Buljumeok 's 개발 스토리

-최대공약수 구하기 유클리드 호제법으로 a,b : 최대공약수를 구하고자 하는 두 수 r : a를 b로 나눈 나머지 = ( a%b ) = ( a mod b ) 식 : gcd(a,b) = gcd(b,r) 구할 수 있다. 이때 a와 b의 관계는 항상 a>b여야 하므로 if(am){ gcd_result=gcd(n,m); answer.push_back(gcd_result); answer.push_back(lcm(n,m,gcd_result)); } else{ gcd_result=gcd(m,n); answer.push_back(gcd_result); answer.push_back(lcm(m,n,gcd_result)); } cout

*이 포스팅은 백준 알고리즘 1260을 기준으로 코드를 설명하므로 입력/출력값에 대한건 백준으로 ㄱㄱ DFS -깊이 우선 탐색 루트노드(혹은 임의의 노드)에서 시작해 다음 branch로 넘어가기 전에 해당 branch를 완벽하게 탐색하는 방법 =>넓게(wide) 탐색하기 전에 깊게(deep) 탐색하는 것이다. =>사용하는 경우: 모든 노드를 방문 하고자 하는 경우에 이 방법을 선택한다. ->깊이 우선 탐색(DFS)이 너비 우선 탐색(BFS)보다 좀 더 간단하다. ->단순 검색 속도 자체는 너비 우선 탐색(BFS)에 비해서 느리다. 그래프 탐색의 경우 어떤 노드를 방문했었는지 여부를 반드시 검사 해야 한다는 것이다. 이를 검사하지 않을 경우 무한루프에 빠질 위험이 있다. 방문한 다음 다시 backtrack..

어떻게 풀어야할까 고민했지만 쉽게 떠오르지 않아 결국 검색.. 이분탐색을 이용해야 함 처음에 왼쪽 오른쪽을 어떻게 정해야하나 했는데 그냥 i와 i+1이 있으면 i가 왼쪽 i+1이 오른쪽 물체는 두개 중간에 있다고 생각하면 되는듯 그래서 이걸 두개씩 계속 호출하면 됨 -처음에는 float형을 썼었는데 이거보고 double 로 고침 오차범위가 줄어든다고 한다. https://www.acmicpc.net/blog/view/37 부동소숫점 오류 게시판에 올라오는 "이 코드는 왜 틀렸나요?" 류의 질문 중 부동소숫점 오류 때문에 틀리는 경우가 꽤 많이 보여서 간단하게 몇 가지 써봅니다. 0. 부동소숫점 오류 모든 실수를 8byte, 혹은 12~16byte의 변수에 모두 담을 수 있다고 생각하시는 분은 없겠죠. 변..

-반복과 재귀 재귀 -재귀는 주어진 문제의 해를 구하기 위해 동일하면서 더 작은문제의 해를 이용하는 방법 - 함수 호출은 메모리 구조에서 스택을 사용함 ->재귀 호출은 반복적인 스택 호출을 의미하므로 메모리와 속도에서 성능 저하 발생함 *재귀가 반복보다 추가적인 메모리와 연산을 발생시킴 -완전탐색 완전 탐색의 경우 모든 경우의 수를 다 확인해야함 Ex)Tsp 문제에서 N=12이상이면 시간 복잡도가 폭발적으로 증가함 ->재귀호출을 이용해서 tsp 완전탐색 -요소의 크기가 작을 때는 빠르게 답을 찾아낼 수 있음 -Greedy algorithm 문제 제시: 거스름돈을 줄때 지폐와 동전의 수를 최소화하기 -최적해를 구하는데 사용되는 방법 -여러 경우중 하나를 선택할 때마다 그 순간에 최적이라고 생각되는 것을 선..

-memoization 컴퓨터 프로그래밍을 실행할때 이전에 계산한 값을 메모리에 저장해서 매번 다시 계산하지 않도록 함 -동적계획 알고리즘 작은부분에서 큰부분의 해들을 모두 구하여 최종적으로 원래 주어진 문제를 해결하는 과정 여러개의 최적해중 임의의 최적해를 구하는것=> optimal - 문제를 더 작은 부분문제로 나눔 -함수의 호출을 줄이기 위함임!! 중복을 없애기 위해 저장된 결과를 배열에 저장해 다음에 사용할때는 저장된 값만 불러오는 방식으로 하는것 1.구하고자하는 문제를 여러 subproblem 으로 만든다 2.가장 작은 부분 문제(보통 0이나 1등의 종료조건)부터 푼 뒤 값을 저장한다. => 메모이제이션 3.메모이제이션된 부분 문제들의 해를 이용하여 차례로 더 큰 상위 문제의 답을 구한다. 4...