Home

17420번 (깊콘이 넘쳐흘러) 난이도: 골드 1 풀이 보고 이해하는데만 정신 나가는 줄 알았다 ㅋㅋㅋ;; 본 문제에서 가장 중요하게 봐야할 점은 다음의 2가지라 생각한다. 기프티콘의 사용 기한이 가장 적은것을 선택한다는 제약조건 기프티콘 사용 기한보다 사용 예정일이 클 경우 갱신을 해줘야 한다는 것 (이 말은 사실 당연한 것이지만 풀이 코드를 보고 이해하는데 이 말을 곱씹는게 나한테 중요했다) 다음 그림에 내가 이해한 모든것을 담았다. 아래 정답 코드를 보면 알겠지만, 위 그림처럼 \(B_i\) (사용예정일)를 중심으로 나열하기 위해 오름차순 정렬을 진행한 부분이 있다. for i in ...

서로소 집합 자료구조 서로소: 여러 개 수들 사이에 1이외의 공약수가 없는 것 서로소 집합: 공통원소가 없는 두 집합 서로소 집합 자료구조(Union-find 자료구조라고도 함): 서로소 부분 집합들로 나누어진 원소들의 데이터를 처리하기 위한 자료구조 서로소 집합 자료구조라는 말의 정의가 애매해서 조금 더 구체화 해보자면, 여러 집합 정보가 있을 때 같은 집합인 것을 찾아서 최대한 단순화 시키는 자료구조로 보인다. 1, 2, 3, 4 노드의 루트 노드는 1 5,6 노드의 루트 노드는 5 루트노드가 1인 집합과, 루트노드가 5인 집합인 총 2종류의 집합으로 나눠진 것으로 볼 수 있다. ...

log는 수학의 여러분야에서 많이 쓰이고, 컴퓨터 공학에서 알고리즘의 시간복잡도를 구할 때 자주 사용된다. \(log_2 N\) 을 직관적으로 받아들이려면 어떻게 생각하면 좋을까? 나는 이렇게 생각한다. N을 2로 나눌 수 있는 횟수. 예를 들어 \(log_2 8 = 3\), \(log_2 24 = 4.xx\) 등 2로 몇번 나눌 수 있는가로 생각하면 수식이 조금은 더 직관적으로 다가온다.

중요한 것은 순서! 순열은 순서가 있고, 조합은 순서가 없다. 순열 경우의 수를 구할 때 순서가 있을 경우는 순열에 해당한다. A, B, C, D 중 2개를 뽑아서 나열한다고 했을 때 AB, AC, AD, BC, BD, CD 에다가 순서가 있으므로, 순서에 따라서 다른 경우의 수가 되는것이여서 BA, CA, DA, CB, DB, DC 까지가 경우의 수에 포함된다. 이것이 순열이다. 조합에 비해 고려해야 하는 경우의 수가 늘어나는 것이다. 아래 그림으로 좀더 구체적으로 보자. 공식 유도 \({}_n P_r = {n! \over (n-r)!}\) 조합 순열과 달리 순서가 없기 때문에 선...

다익스트라 알고리즘, 플루이드 워셜 알고리즘 모두 무방향 그래프, 양방향 그래프에 상관없이 최단 경로를 구할 수 있다. 다익스트라 최단 경로 알고리즘 지금부터 설명할 내용은 1번 노드를 기준으로 각 노드들에 도달할 수 있는 최단거리를 구하는 것이다. 항상 시작점이 1번 노드라는것을 인지하고 있으면 이해하기 좀더 편할 것이다. 다음의 로직이 반복되어 다익스트라 알고리즘이 작동된다. 출발 노드 설정 최단 거리 테이블 조회 방문하지 않은 노드 중 최단 거리가 가장 짧은 노드 선택 여기 3번에서 선택된 노드는 이미 1번 노드 기준으로 현재 선택된 노드가 최단거리인게 fix 된 상황...