혼새미로의 블로그

소개 서브웨이에 방문하면 손님은 빵 크기, 빵 종류, 추가토핑, 야채, 소스를 선택해야 하나의 샌드위치가 완성됩니다. 이와 같이 하나의 객체를 만드는 과정에서 옵션이 다양할 때 사용하는 패턴이 빌더 패턴 (Builder Pattern) 입니다. 이 포스팅에서 빌더 패턴을 설명하지는 않고, 빌더 패턴을 적용한 서브웨이 샌드위치를 생성하는 소스코드를 공유합니다. 소스코드는 타입스크립트를 기반으로 작성하였습니다. 열거체 const enum EBreadSize { SMALL = 1, LARGE = 2, } const enum EBreadType { WHITE = 1, WHEAT = 2, HONEY_OAT = 3, HEARTY_ITALIAN = 4, PARMESAN_OREGANO = 5, FLAT_BREAD = ..

문제 링크 [방법] 배열의 원소들을 순회하면서 가장 큰 자릿수를 구한다. 각 배열의 원소를 해당 크기의 자릿수만큼 늘리고, 자릿수가 변경되면서 생긴 자릿수 값은 해당 원소의 원본 값에서 가장 큰 자릿수의 값으로 할당한다. 예를 들어, 원소 41이 있고 가장 큰 자릿수가 3이라면 41을 414로 변경한다. 새로운 배열에 대해 내림차순으로 정렬하고, 같은 값을 가질 경우 원본 값에서 1의 자릿수 값을 비교하여 결정한다. 정렬된 배열의 원본 값을 순서대로 이어붙이면서 결과 값을 완성한다. [테스트 케이스] 41과 414가 주어졌을 때, 41441이 나와야 한다. 89와 898이 주어졌을 때, 89898이 나와야 한다. [소스코드] function solution(numbers) { let answer = ''..

백준 알고리즘 링크 남극에 펭귄 한 마리와 크기와 모양이 동일한 N 개의 얼음 블록이 있습니다. 펭귄은 N개의 얼음 블록 중 한 곳 위에 서 있습니다. 펭귄이 서있는 얼음 블록 (이하 블록)을 기준으로 다른 블록들이 연결되어 있으며, 각 블록으로 이동할 수 있는 경로는 한 가지만 존재합니다. N개의 얼음 블록 중 M 개의 블록은 지지대 블록으로, 일반 블록들이 무너지지 않도록 지탱해주는 역할을 합니다. 일반 블록들은 지지대 블록이 하나라도 연결되어 있으면 무너지지 않습니다. 또한, 지지대 블록들 사이에 이동을 위해서는 반드시 펭귄이 서있는 블록 (이하 루트 블록)을 거쳐야 합니다. 또한, 루트 블록이 무너지지 않기 위해서는 지지대 블록이 반드시 두개 이상 연결되어 있어야 합니다. 또한, 루트 블록이 무너..

문제 : https://algospot.com/judge/problem/read/WITHDRAWAL 이 문제에서 n개의 수강과목이 주어지고, 이 중에서 k개의 수강과목을 선택하여 누적등수를 높이고자 합니다. 이 문제를 해결하는 가장 단순 무식한 방법은 n개의 과목 중에서 모든 경우의 k개의 과목을 선택하여 가장 낮은 값을 가지는 누적 등수 값을 찾는 것입니다. 즉, n개 중에서 k개를 선택하는 경우의 수만큼 검사를 해야 합니다. 그 공식은 위와 같이 나타낼 수 있는데, 문제에서 n의 값이 1000까지 가능하다고 하기 때문에, 예를 들어, n=1000이고, k=10일 경우, 모든 가능한 경우의 수는 다음과 같이 상당한 값을 가지게 됩니다. 따라서, 단순 무식한 방법으로는 절대 결과를 얻을 수 없다는 것을 ..

2-SAT은 충족가능성 문제로, 위의 식과 같이 OR 연산으로 두 변수가 묶인 절들이 각각 AND 연산으로 연결되어 있는 형태에 대해 f가 참인 경우를 만들기 위해 각각의 변수를 참과 거짓 중 무엇으로 설정해야 하는지 계산해야 합니다. 위와 같이 AND 연산으로만 표현된 식의 형태를 CNF (Closure Normal Form)이라고 합니다. 두 불린 변수 p와 q가 있을 때, p→q는 “p가 참이면 q도 참이다”라는 명제를 의미합니다. 다음의 표는 두 불린 변수의 각 경우에는 p→q의 진리값을 나타냅니다. 만약 p가 참일 때 q가 거짓이라면 이 명제는 거짓인 명제가 됩니다. 그리고, p가 거짓이라면 q와 상관없이 이 명제는 항상 참이되는데요, 그 이유는 이 명제는 항상 p가 참일 경우가 전제가 되어야 ..

문제 : https://algospot.com/judge/problem/read/RUNNINGMEDIAN문제에서 설명한 바와 같이 수열에 새로운 값을 삽입할 때마다 해당 수열의 중간값을 출력하는 효율적인 방법은 두 개의 우선순위 큐를 이용하는 것입니다. 두 개의 우선순위 큐 중에서 하나는 오름차순 우선순위 큐, 다른 하나는 내림차순 우선순위 큐로 구성합니다. 새로운 데이터를 삽입할 때, Q1의 top보다 작으면 Q1에 삽입하고, Q2의 top보다 크면 Q2에 삽입하면서, 모든 경우에 대해 만약 Q1과 Q2의 데이터 개수를 동일하거나 전체 데이터 개수가 홀수 개이면서 Q1의 데이터 개수가 Q2보다 한 개 더 많을 때, Q1의 top이 중간값이라고 할 수 있습니다.예시를 위해 입력 데이터를 다음과 같이 구성..

이번에 제가 설명할 주제는 강한 연결 요소 (Strongly Connected Component)입니다. 유향그래프에서, 어느 한 정점에서 출발하여 다시 자신으로 돌아오는 경로를 사이클이라고 합니다. 위의 그림은 사이클이 존재하는 유향그래프를 나타냅니다. 유향그래프에서 하나의 사이클은 내부적으로 하나 이상의 서브사이클이 존재할 수 있습니다. 그림과 같이 유향그래프에서 A->B->D->C->A의 사이클 내에 A->B->C->A와 B->D->C->B와 같은 서브사이클이 존재하는 것을 알 수 있습니다. 여기서, 한 정점을 지나는 모든 사이클 중에서 가장 많은 정점을 포함하는 사이클의 정점들의 집합을 강한 연결 요소 (Strongly Connected Component)라고 합니다. 그림의 예시에서는 A->B-..

알고스팟의 어린이날 문제에 대해 설명해보겠습니다.문제 : https://algospot.com/judge/problem/read/CHILDRENDAY먼저, 어린이날 문제를 요약해보도록 하겠습니다. 모든 어린이들의 총합은 N 명이고, 우리는 N 명의 어린이들에게 균등한 개수의 선물을 나눠줘야 합니다. 예를 들어, 각 어린이들에게 한 개의 선물을 나눠준다고 하면, N개의 선물이 필요하게 됩니다. 단, M명의 욕심쟁이 어린이들에게는 한 개의 선물을 더 주어야 하기 때문에 최소한으로 주어야 하는 선물의 총 합은 N+M이 됩니다.N명의 어린이들에게 균등한 수의 선물을 나눠줘야 한다.N명 중 M 명의 욕심쟁이 어린이들에게 선물 하나를 더 줘야 한다.선물 개수 총합은 주어진 숫자 목록의 숫자들만 사용해야 한다.주어진..

주어진 알고리즘을 직관적으로 생각하기 어렵다고 생각하여 문제를 4개의 작은 문제들로 분리해보았습니다.먼저, 원본 문제의 링크입니다: https://algospot.com/judge/problem/read/ZIMBABWE입력받은 양의 정수형 숫자 num에 대하여 각 자릿수의 숫자 순서를 바꾸어 나타낼 수 있는 모든 값들 중에서 num보다 작은 값을 갖고, 또 다른 주어진 입력 값 M의 배수인 값들을 모두 출력하라. 단, 자릿수들의 값은 서로 같을 수 있으며, (예: 2031, 4401, 5550016, 10348 등이 num으로 가질 수 있다), 2

분해2에서 설명했듯이, 가장 큰 자릿수의 숫자부터 순서대로 선택할 때, 만약 i번째 까지 선택된 숫자들이 동일하다면, (예를들어, num=2030 일때, 앞에 20이 선택되었든 02가 선택되었든) 이후에 선택되어 나열될 수 있는 경우의 수는 동일합니다. (20->2003,2030...02->0203,0230) 따라서, 선택된 값 (예:02)들을 인덱스로 해서 가능한 나열의 수를 최초로 계산한 결과를 보관해두면, 나중에 같은 값(예:20)을 선택했을 때, 같은 인덱스를 참조하여 별도의 반복문 없이 빠르게 값을 얻을 수 있습니다. 같은 숫자들의 집합에 대하여 같은 인덱스를 가지도록 하기 위해 다음과 같은 방법을 사용할 수 있습니다. n자리 숫자에 대하여 i번째 자릿수의 숫자를 선택했다고 하면 i번째 비트 값..