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

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

• format_list_bulleted 컴퓨터 공학/A.I.
• · 2022. 12. 18.
• textsms

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

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

• format_list_bulleted 컴퓨터 공학/Algorithm
• · 2021. 6. 7.
• textsms

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

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

• format_list_bulleted 컴퓨터 공학/Algorithm
• · 2018. 9. 12.
• textsms

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가 참일 경우가 전제가 되어야 ..

• format_list_bulleted 컴퓨터 공학/Algorithm
• · 2018. 9. 12.
• textsms

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

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

• format_list_bulleted 컴퓨터 공학/Algorithm
• · 2018. 9. 12.
• textsms

강한 연결 요소 (Strongly Connected Component)

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

• format_list_bulleted 컴퓨터 공학/Algorithm
• · 2018. 9. 12.
• textsms