이제 문제를 풀어보자. https://school.programmers.co.kr/learn/courses/30/lessons/92344 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 앞선 글에서 언급했듯이 brute force로 풀어서는 효율성 테스트를 통과하지 못한다. 이 문제를 푸는데 핵심이 되는 아이디어는 크게 2가지로, 1. 공격/회복을 전부 적용한 최종 결과를 한 번에 board에 적용한다. (공격/회복 하나씩 처리하면 안된다.) 2. 공격/회복 계산 시에는 역 누적합 배열을 이용한다. 1번은 쉽게 수긍이 되지만 2번은 저게 뭔 소린가 싶다. ..
https://school.programmers.co.kr/learn/courses/30/lessons/92344 위 문제를 풀어보려다 보니 brute force로 풀면 정확도까지는 쉽게 통과가 되나 1,000 x 1,000 2차원 배열에 250,000개의 배열 업데이트를 해야 하니 효율성 테스트를 통과할 여지가 없다. 해설을 찾아보니 누적 합을 사용해서 풀어야 한다는데, 이번 기회에 해당 내용을 정리하고 문제 풀이를 해보려 한다. # 1차원 누적 합 1차원 배열에서의 누적 합을 구하는 함수를 'f(x)'라 할 때 다음과 같이 정의된다. (구현 시 편의 상 i = 0부터 시작하는 것으로 하였다.) 이 때 x = a에서 x = b까지의 부분합을 구하고 싶다면, 다음과 같이 나타낼 수 있다. 이를 JavaS..
# 위상 정렬 (Topology Sort) 위상 정렬은 순서가 정해져 있는 작업을 차례대로 수행해야 할 때 사용할 수 있는 알고리즘이다. 비순환 유향 그래프에서 사용할 수 있다. 진입 차수(indegree), 즉 자신으로 들어오는 간선의 수가 0인 노드부터 차례대로 제거해나가며 순서를 정한다. # Process 진입 차수가 0인 노드를 큐에 담는다. 큐가 빌 때까지 큐에서 원소를 꺼내고 해당 노드에 연결된 간선을 제거한다. 새롭게 진입 차수가 0이 된 노드를 큐에 담는다. Ex. 대표적인 예시로 선수과목 있는 수강 계획 순서를 정할 때 사용할 수 있다. 0 ~ 5번의 과목이 있고 각 과목은 자신을 가리키는 선수 과목을 모두 들은 후에야 수강할 수 있다고 하자. 예를 들어 4번 과목은 1, 2번 과목을 모..
# 크루스칼 알고리즘(Kruskal Algorithm) 크루스칼 알고리즘은 최소 신장 트리 (Minimum Spanning Tree)를 만드는데 사용하는 알고리즘으로 그리디 알고리즘으로 분류된다. 비용이 작은 간선을 선택하며 서로소 집합 자료구조를 이용해 사이클이 발생하지 않도록 처리하는 방법이다. 이를 통해 불필요한 간선(사이클이 발생하는 간선)이 선택되지 않으면서도 간선 비용의 합이 가장 작은 신장 트리를 만들 수 있다. 모든 간선을 정렬하고 순회하기 때문에 간선의 수가 적은 그래프에서 활용하기에 적합하다. 간선의 수가 노드에 비해 훨씬 많다면 프림 알고리즘의 사용을 고려하자. 서로소 집합을 이용한 사이클 판별 서로소 집합을 통해 사이클인지 확인하는 방법은 간선 양쪽 노드의 find 연산 결과가 같은..
# 서로소 집합 (Disjoint sets) 서로소 집합이란 공통 원소가 없는 두 집합을 의미한다. 아래 그림의 왼쪽 두 집합은 서로소 관계이며, 오른쪽은 아니다. 서로소 집합은 여러 개의 서로소 관계로 이루어진 데이터를 처리하기 위한 자료구조로 사용되며 몇몇 그래프 알고리즘에서 주요하게 사용된다. 서로소 집합은 union / find 두 가지 연산으로 구현할 수 있으며, 이 때문에 union-find 자료구조로 불리기도 한다. Union 연산은 2개의 집합을 하나로 묶는 연산이며, find 연산은 특정 원소가 어느 집합에 속해있는지 찾는 연산이다. 서로소 관계인지 확인 시에는 find 연산의 결과가 다른지 확인하면 된다. # Process 모든 연결 관계에 대하여 union 연산을 이용해 서로 연결된 ..
포트폴리오 페이지 제작의 막바지에 다다랐다. 글로는 쓰진 않았지만 그간 contact 페이지에 canvas로 애니메이션을 추가하고 resume 페이지도 추가하고 임시로 해놨던 내용도 작성하여 다시 채워넣었다. 이제 마지막으로 localhost 주소에서 벗어날 차례이다. 배포 방법 선정 배포 방법으로는 몇 가지 선택지가 있다. 가장 원초적인 방법으론 집에서 남는 PC로 서버를 돌리는 방법이 있고, 많이들 사용하는 github page를 사용할 수 있지만, 나는 vercel을 사용하기로 하였다. 가장 큰 이유는 개인 프로젝트 수준에서 무료로 이용할 수 있으며 github repo를 그대로 가져와 사용할 수 있다는 점이다. 부차적인 이유로는 Next.js를 사용해 제작하다보니 시작부터 끝까지 vercel을 사..
