DOYLE DEVELOPMENT NODE

다이나믹을 사용하면 되는 문제 경우의 수가 오지게 많아서 long long 을 써줘야 한다. int 썻다가 피를 봤다.. 원리는 어렵지 않다. 점화식을 세우면 되는데

d[i번째 수를 사용][현재 수] 가 경우의 수를 나타낸다고 했을 때 입력받은 a배열에서 해당 만큼 빼주고 더해주면 된다. 

신기한 건 나는 답을 못찾겠을 때 구글에 백준 문제 번호를 검색하는데 내 코딩과 비슷한 사람이 보인다..

다이나믹 프로그램을 사용한다. 재귀적 방법을 사용했다. 연주가능하면 1 불가능하면 0 방식을 사용해 시작점부터 마치 분할 정복 하듯이 내려간다. 하지만 분할 정복은 아니다 왜냐하면 만약 같은 볼륨 값을 가르키는 지점에 여러 전 곡에서 도달했을 때 한 가지 경우만 세면 되기 때문이다. 

다이나믹 프로그래밍을 사용하는 문제 d를 0부터 끝까지 순회하므로 만약 d[i]번째에 도달하는 경로가 없을 경우 이를 계산하지 않도록 유의하면서 if문을 짜줘야한다. j원에서 동전 값을 뺀 것이 0보다 크고 동시에  d[j - coin[i]] 또한 -1 (배열을 -1로 값을 설정했다.)이 아니어야 이전에 값이 메모라이징 됬었다는 것이고 처음 j원에 방문하는 것인지 아닌지를 판단해 준 후 가장 최소 값을 입력해준다.

다이나믹 프로그래밍을 이용하는 문제 낮은 수의 동전부터 먼저 메모라이징해준 후 더 큰 수로 계속해서 메모링해 나아가서 

1원 2원 동전이 있을 경우 1 + 2, 2 + 1과 같이 반복되는 경우의 수를 없애 준다.

1 2 1 과 같이 대칭되는 숫자인지 판별하는 문제

다이나믹프로그램을 활용한다. d[i][j] 를 i번째 수 부터 j 번째가 팰린드롬인지 여부라고한다면 재귀로 d[i+ 1][j - 1]을 다이나믹으로 문제의 범위를 좁혀나가준다. 팰린드롬은 사실 n정도의 시간복잡도로 구해 줄 수 있지만 문제에서 엄청난 수의 문제를 구하라고 하기 때문에 문제의 정답을 기억해놓고 다시 써먹어야할 필요성이있다. 그래서 다이나믹을 활용하는 것이다.

다이니믹 프로그래밍을 이용하는 문제 n,n에는 0 값이 들어있느니 자기자신을 계산하는 것을 방지하기 위해 continue 코드를 넣어준다.

인덱스 때문에 고생한 문제 일단 문제를 봤을 때 벙찌게 된다.. 내가 작성하는 풀이들은 알고리즘 초보이거나, 나중에 내가 푼 문제를 되돌아 보기 위한 것이므로 이 문제를 볼 때 상당한 난해함을 느끼게 되지만 한 번 생각해보자.

먼저 포스터 오더와 인 오더에 대해 생각해보자. 결론부터 말하자면 포스트 오더가 마지막에 방문하는 노드는 루트이다. 왜 그럴까? 포스트오더는 시작하는 L R 노드 순으로 방문하기 때문이다. 그러면 포스트 오더로부터 루트를 알 수 있다. 그러면 루트를 알 수 있다면 인 오더에서 L트리와 R트리를 구분 할 수 있다. 인오더는 L 노드 R 순이기 때문이다. 자연스럽게 포스트오더에 맨 마지막에 있는 수를 기준으로 인오더의 왼쪽은 L 트리 오른쪽은 R트리이다. 그러면 이제 프리오더 순으로 방문하기 위해 재귀적인 방법을 사용하면 된다. divide and conquer다.  다시 L트리와 R트리에서 포스트오더 인오더의 범위를 지정해주고 계속해서 재귀해나가면 된다. 방법을 알고 있음에도 나는 한참 해맸는데 멍청하게  go 함수 return문 바로 뒤인 22,23라인에서 절대적 배열의 주소를 사용하려고 했었기 때문이다. 절대적 주소를 사용할 경우도 있겠지만.. 왠만하면 상대적인 주소를 사용하는게 오류를 범할 가능성이 적은 것 같다. 재귀함수를 코딩하면 그 내부에서 어떤 일이 일어나는지 알아야하겠지만 보이지 않으니 놓치는 부분이 있을 수도 있기 때문에 상대적인 주소를 사용하자!

그리디 알고리즘을 사용한 문제 증명은 없지만 직관적으로 보면 회의가 가장 빨리 끝나는 순으로 배정을 한다. 백준 입력이 정렬되어있는지 알수 없으므로 정렬도 해준다. 시간복잡도는 O(n) 보다 정렬해야하니깐 O(nlogn) 일수도

그리디 알고리즘을 사용하는 문제.. 이게 그리디 알고리즘으로 된다는 것만 알면 쉽다.

시간복잡도 O(n)