May 09, 2023
배낭 문제 배낭 문제(knapsack problem)는 조합 최적화 문제의 일종입니다. 간략하게 말하자면, 담을 수 있는 최대 무게가 정해진 배낭과 함께 각각의 무게와 가치가 주어진 아이템의 집합이 주어졌을 때, 배낭에 담은 아이템들의 가치의 합이 최대가 되도록 하는 아이템들의 부분집합을 찾는 문제입니다. 배낭 문제에는 분할 가능한 배낭 문제(fracti…
April 27, 2023
문제의 목적은 승률 를 1 증가시키기 위해 최소한 몇 번 이겨야 하는지를 구하는 것입니다. 처음 승률 승률을 1 증가시키기 위해 게임을 번 진행했을 때 승률 최소 게임 수를 구하기 위해 식을 에 대한 식으로 정리해줍니다. 를 대입시켜 를 구해줍니다. 여기서 의 값이 소수가 되는 경우에는 값을 올림해줘서 최소 게임 수를 구합니다. 단, 확률이 9…
April 27, 2023
풀이 먼저, 문제는 두 원의 중심 좌표와 반지름이 주어졌을 때, 겹치는 점의 개수를 찾는 것입니다. 겹치는 점의 개수는 다음과 같은 경우가 있습니다. 두 원이 서로 겹치지 않는 경우 (겹치는 점이 없음): 0 두 원이 서로 한 점에서 만나는 경우 (외접 또는 내접): 1 두 원이 서로 두 점에서 만나는 경우: 2 두 원이 완전히 겹쳐져 있는 경우 (겹치는…
April 22, 2023
풀이 문제의 목표는 두 개의 용액을 혼합했을 때, 혼합된 용액의 특성값이 0에 가장 가깝도록 하는 것입니다. 이 문제는 투 포인터 알고리즘을 사용하여 해결할 수 있습니다. 용액의 개수(n)와 각 용액의 값을 입력 받습니다. 이 때 값은 용액의 특성값을 말합니다. 두 포인터 와 를 초기화합니다. 는 처음 위치에, 는 마지막 위치에 두고 시작합니다. 현재 와…
April 22, 2023
Github Action이란 GitHub Actions는 GitHub에서 제공하는 개발 워크플로우 자동화 도구로, 코드의 빌드, 테스트, 배포, 그리고 프로젝트 관리와 관련된 다양한 작업을 자동화할 수 있습니다. 이를 통해 개발자들은 시간과 노력을 절약하고, 효율성을 높일 수 있습니다. 이벤트 기반 트리거 - GitHub Actions는 특정 이벤트에 기…
April 21, 2023
을 사용하여 중복 제거하기 은 파이썬의 내장 자료구조로, 중복된 값을 허용하지 않는 특징이 있습니다. 이 특징을 이용하여 리스트의 중복을 제거할 수 있습니다. 으로 변환하면 중복된 값들이 자동으로 제거되며, 이후 다시 로 변환하여 원하는 결과를 얻을 수 있습니다. 이 방법의 단점은 원래 리스트의 순서가 유지되지 않을 수 있다는 것입니다. 은 순서를 고려하…
April 20, 2023
백준 1058번 - 친구 풀이 1 친구 관계를 인접 리스트 형태로 저장했습니다. 예를 들어 보겠습니다. A의 친구 : B, C B의 친구 : A, D C의 친구 : A, D 의 관계가 있을 때, A의 2-친구를 구하기 위해 라는 리스트를 만듭니다. 이 리스트에는 두 종류의 원소들이 들어갑니다. A의 친구들 A의 친구들의 친구들 현재 테스트 케이스를 …
April 17, 2023
풀이 계단을 한 칸 오를 때 연속된 세 개의 계단을 오를 수 없으므로 한 칸을 올랐으면 이전에는 무조건 두 칸을 올랐어야 합니다. 계단을 두 칸 오를 때 다음에 한 칸을 오르든 두 칸을 오르든 상관없습니다. 이 문제는 n번째 계단까지의 최고 점수를 구하는 것이 목적입니다. 이를 위해서는 n-1번째 계단까지의 최고 점수와 n-2번째 계단까지의 최고 점수를…
November 22, 2022
개념 트리나 그래프에서 한 루트로 탐색하다가 특정 상황에서 최대한 깊숙이 들어가서 확인한 뒤 다시 돌아가 다른 루트로 탐색하는 방식이다. 일반적으로 자기자신을 호출하는 재귀함수의 형태이지만 단순한 스택 배열로 구현되기도 한다. 백트래킹에 자주 사용된다. 너비 우선 탐색에 비해 간단하다. 단순 검색 속도 자체는 너비 우선 탐색에 비해 느리다. 구현 위 …