반응형

알고리즘 19

ChatGPT로 알고리즘 문제 프리패스하기

발단 최근에 ChatGPT와 관련된 글들이 뉴스와 트위터 등에서 많이 보이고 있어서 무료기도 해서 직접 채팅을 해보았습니다. 처음에는 어떤 질문을 해야할지 몰라서 간단한 대화 정도만 하다가 최근에는 생각보다 괜찮아서 모르는 용어가 있을 때 구글 대신 ChatGPT에 먼저 물어보는 편입니다. 구글은 여러 게시물들을 사용자가 직접 방문하면서 내가 원하는 답이 있는지 찾는 반면, ChatGPT는 마치 전문가에게 직접 물어보는 것처럼 맞춤형 답변을 해주기 때문에 제가 원하는 대답일 확률이 높은 것 같기도 합니다. (물론 오답을 그럴듯하게 답변하기도 합니다) ※ ChatGPT 웹사이트 링크 : https://openai.com/blog/chatgpt/ 그러던 중 최근에 백준, 알고스팟, 프로그래머스 등의 웹사이트..

백준 알고리즘 21738 얼음깨기 펭귄 C++ 코드

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

알고스팟 - 수강철회 (WITHDRAWAL)

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

2-SAT (2-Satisfiability)

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

알고스팟 - 변화하는 중간값 (RUNNINGMEDIAN) 설명

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

강한 연결 요소 (Strongly Connected Component)

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

알고스팟 - 어린이날 (CHILDRENDAY) 문제 설명

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

알고리즘: 웨브바짐 문제 분해 - 4 (완)

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

알고리즘: 웨브바짐 문제 분해 - 3

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

알고리즘: 웨브바짐 문제 분해 - 2

주어진 알고리즘을 직관적으로 생각하기 어렵다고 생각하여 문제를 4개의 작은 문제들로 분리해보았습니다. 먼저, 원본 문제의 링크입니다: https://algospot.com/judge/problem/read/ZIMBABWE 입력받은 양의 정수형 숫자 num에 대하여 각 자릿수의 숫자의 순서를 바꾸어 나타낼 수 있는 모든 경우의 수를 출력하라. 단, num의 각 자릿수의 숫자는 중복될 수 있다. (예: 123, 385,9285, 2738, 2288, 1233)1234567891011for (int i = 0; i

반응형