S E P H ' S

프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 풀이 주어진 n 과 tops로 인해 형성되는 모양을 4가지 모양의 도형으로 채울 수 있는 "경우의 수"를 구하는 문제이다. 문제를 보자마자 규칙을 찾아야 겠다는 생각이 들었다. 다행히 직관이 잘 얻어 걸렸던 것 같다. 우선 4가지 모양의 도형의 유형과 n과 tops로 형성되는 모양 간의 규칙에 집중했다. 채워야할 공간의 n번째 사다리꼴에서 가운데 뒤집어진 삼각형을 기준으로 아래 4가지 모양을 사용해서 채울 수 있다. 4가지 모양 1. 윗 정삼각형과 함께 덮여지는 마름모 2. 왼 정삼각형과 함께 덮여지는 ..

연쇄행렬 최소곱셈 알고리즘 (Matrix Chain Multiplication) 주어진 행렬들의 곱을 최소의 연산으로 수행하는 최소횟수를 구하는 알고리즘이다. 행렬의 곱셈에서 결합법칙은 성립하나 순서에 따라서 계산 횟수가 달라질 수 있다. 아래와 같은 행렬로 확인해보도록 하자. 그림을 확인해보면 순서에 따라 전체 연산횟수가 달라짐을 알 수 있다. 위와 같이 행렬의 개수가 5개일때 모든 결합의 마지막 결합 형태는 다음과 같이 네 가지로 분류가 가능하다. (행렬의 개수가 n 이면 n - 1 가지로 분류가 가능하다.) (AB)(C(DE)) 는 결국 (AB)(CDE) 와 같고 (A(B(CD)))E 는 결국 (ABCD)E 와 같다. 다시 말하자면 행렬의 개수가 n 이면 최소 연산 횟수는 n - 1 가지 경우 중의..

프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제풀이 처음 풀었던 풀이는 idx 값과 코어 작업시간을 필드로 갖는 Core 클래스를 만들었다. 그 뒤로 PQ를 사용하여 n 이 0이 될때까지 조건에 맞춰 n을 조작했다. 작업이 처리되는 경우는 현재 코어의 작업처리 시간과 현재시간이 같거나, 현재 코어 작업처리 시간이 현재 시간보다 큰 경우이다. 현재 코어 처리시간이 큰 경우는 현재 시간을 코어 시간으로 처리해준다. 그 다음 남은 작업이 없다면 반복문을 종료시키고 그때의 코어 인덱스를 반환하게하고 아직 작업이 남았다면 PQ에 새 코어를 만들고 그 코어의 작..

MST(Minimum Spanning Tree) 최소 신장 트리 그래프의 모든 정점을 사이클 없이 잇는 (신장 트리) 트리에서 간선의 가중치의 합이 최소가 되는 트리를 말한다. 크루스칼 알고리즘 간선 중심으로 최소 신장 트리를 구하는 알고리즘. 간선이 적을때 프림 알고리즘보다 유리하다. 내부적으로 union-find 알고리즘을 사용 간선들을 가중치의 오름차순 정렬하여 가장 작은 간선을 선택한다. 그 간선이 지금까지 만들어진 MST와 싸이클을 형성한다면 제외하고 아니라면 MST에 추가한다. 모든 간선에 대해 반복한다. 프림 알고리즘 정점 중심으로 최소 신장 트리를 구하는 알고리즘 정점이 적을때 크루스칼 알고리즘보다 유리 임의의 정점 선택 그 정점과 인접한 정점을 잇는 간선 중 가중치가 가장 낮은 간선 선택..