초보 개발자

백트래킹 - DFS와 유사하게 진행되나, 해당 노드의 유망성을 보고 진행을 결정한다. [BOJ 15649] N과 M (1) 문제 1부터 N까지의 수로 수열을 만드는 문제이다. 이때 수열은 M개의 수로 이루어져 있으며 순서는 상관이 없다. C++ 풀이 백트래킹 코드를 짤 때는, 방문 여부를 표시해둘 visited 배열을 만드는 것이 중요하다 만약 이미 visited한 인덱스라면 건너뛰거나 / 다시 되돌아가는 일이 필요하다. 다시 되돌아왔다면 visited 배열을 다시 0으로 표시해주어야 다음 수열에서도 해당 인덱스를 사용할 수 있다. 아래 코드에서 방문여부는 visited 배열에, 수열의 정보는 arr 배열에 저장하였다. cnt 변수는 arr 배열의 인덱스로 사용하였고, cnt가 M이 될 경우 arr에 저..

현재 SW마에스트로 코딩테스트 준비를 위해 백준 문제를 풀고 있다. 이전에 배웠던 최대공약수, 최소공배수 구하는 알고리즘을 까먹어 다시 기억하기 위해 작성하는 글이다. 최대공약수: 두 수가 공통으로 가지는 가장 큰 약수 ex) 16, 24가 있다면 두 수의 최대공약수는 8이다. 1. 쉽게 생각할 수 있는 알고리즘: 반복문을 통해 1부터 min(a,b)까지 모두 나눠보고 가장 큰 값을 최대공약수로 설정한다. - 장점: 간단하게 생각해낼 수 있고, 구현이 쉽다. - 단점: min(a,b)가 클 경우 시간이 매우 오래 걸린다. 시간복잡도: O(N) 2. 유클리드 호제법: a를 b로 나눈 나머지가 r일 때, GCD(a,b)=GCD(b,r)이다. r이 0이 된다면 그때의 b가 최대공약수이다. - 예시: GCD(2..