![]()
0. 문제 설명 우체국 2285번: 우체국 첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 X[1], A[1], X[2], A[2], …, X[N], A[N]이 주어진다. 범위는 |X[i]| ≤ 1,000,000,000, 0 ≤ A[i] ≤ 1,000,000,000 이며 모든 입력은 정수이다. 모든 A[i]를 www.acmicpc.net 1. 문제 생각 처음에는 맨허튼 거리와 같은 알고리즘을 생각했다. 각 마을에 포함되는 사람들의 수를 가중치처럼 여긴 후 ∑각 마을의 index * 사람들의 수/ ∑사람들의 수 로 해결하려고 했는데 한 번 틀렸다 😥 아래 데이터를 조금 더 생각해보면 이 아이디어가 통하지 않음을 알 수 있는데 아래 데이터로 한번 생각해보면 좋다! 6 1 8 8 ..
![]()
0. 문제 우수 마을 1949번: 우수 마을 N개의 마을로 이루어진 나라가 있다. 편의상 마을에는 1부터 N까지 번호가 붙어 있다고 하자. 이 나라는 트리(Tree) 구조로 이루어져 있다. 즉 마을과 마을 사이를 직접 잇는 N-1개의 길이 있으며, www.acmicpc.net 1. 문제 생각 트리에서의 DP 문제이다. 트리란 사이클이 없이 모든 정점이 연결되어있는 그래프로, 사이클이 없는 그래프이므로 정점의 개수가 V개이면 간선의 개수는 V-1개라는 특징을 갖는다. DFS+DP 로 트리에서의 DP를 해결할 수 있고 아래처럼 DP 테이블을 채우기 위해 계속해서 인접한 노드를 탐색하는 점에서 DFS가 강력하다! 2. 문제 구현 import sys sys.setrecursionlimit(10**6) def d..
![]()
제 3회 한국항공대학교 프로그래밍 경진대회 제3회 한국항공대학교 프로그래밍 경진대회프로그래밍에 관심이 있다면, 지금 바로 도전해보세요.kaupc2023.netlify.app대회 개최우리 학교는 경인지역 6개 대학 소속으로 매년 SHAKE! 대회에 참여하고 있으며 이 대회에 참여하기 위한 10명의 인원을 교내에서 자체적으로 선발하고 있다. 자체 선발 대회인 KAUPC는 매년 KOALA 동아리에서 주최하고 있으며 이번 년도는 내가 동아리를 운영하고 있어 책임감을 가지고 대회를 주최하게 되었다. 문제 출제를 위해 급하게 500문제를 3달동안 풀었다.대회는 3월부터 미리미리 준비했고 출제진은 gojib2022, hello70825, soo7652, 20wjsdudtj(나) 로 진행되었다. 다들 학교를 떠나 있음..
0. 문제 같이 눈사람 만들래? 20366번: 같이 눈사람 만들래? 높이가 (2, 5), (3, 5)로 구성된 눈사람 둘을 만드는 것이 최적의 경우 중 하나이다. |7-8| = 1 다른 경우로는 (2, 9), (5, 5)로 두 눈사람을 만드는 경우가 있다. |11-10| = 1 www.acmicpc.net 1. 문제 생각 4개를 뽑아서 대조하는 것으로 먼저 생각해볼 수 있다. 하지만 600C4(5억)는 2초 안에 못 들어오기 때문에 X 일단 N은 600이기 때문에 2초 안에 들어오려면 적어도 N^3까지는 가능하다. 우리가 4개를 뽑아 한 세트를 만든다고 하면 예를 들어 2 3 5 5 일 때 세트는 (1️⃣4️⃣, 2️⃣3️⃣)으로 1번째와 4번째 것이 하나의 세트가 되고 2번째와 3번째 것이 하나의 세트..
0. 문제 양팔저울 2629번: 양팔저울 첫째 줄에는 추의 개수가 자연수로 주어진다. 추의 개수는 30 이하이다. 둘째 줄에는 추의 무게들이 자연수로 가벼운 것부터 차례로 주어진다. 같은 무게의 추가 여러 개 있을 수도 있다. 추의 무 www.acmicpc.net 1. 문제 해석 추의 종류와 구슬의 종류가 주어졌을 때 추들로 구슬들의 무게를 판단할 수 있는가 없는가를 물어보는 문제이다. 예를 들어 예제 2를 보면 추 1,4kg으로 알 수 있는 구슬의 무게는 1,4,3,5 kg에 해당한다. 양팔 저울의 양쪽에 놓을 수 있다는 것을 주의하자! 따라서 Knapsack으로 DP를 채워나간다. DP[추의 종류][구슬 무게] = 가능?불가능? 으로 나타낼 수 있고 DP table을 채우는 것은 for문 추의 무게로..
![]()
0. 문제 K번째 수 1300번: K번째 수 세준이는 크기가 N×N인 배열 A를 만들었다. 배열에 들어있는 수 A[i][j] = i×j 이다. 이 수를 일차원 배열 B에 넣으면 B의 크기는 N×N이 된다. B를 오름차순 정렬했을 때, B[k]를 구해보자. 배열 A와 B www.acmicpc.net 1. 문제 생각 일단 "정렬"에 대한 직접적인 언급이 있으나 정렬할 수 없다. N이 최대 10**5인데 NlogN을 수행할 수 없으므로! 그리고 나서는 A에 대한 B를 직접 만들어보았다. B=[1, 2, 2, 3, 3, 4, 4, 4, 5, 5, 6, 6, 6, 6, 7, 7, 8, 8, 8, 8, 9, 9, 9, 10, 10, 10, 10, ...] 여기에서 규칙을 찾을 수 있다! 바로 각 숫자가 자신의 "약..
![]()
0. 문제 데이터 체커 22942번: 데이터 체커 데이터가 조건에 맞는다면 YES, 조건에 만족하지 않는다면 NO를 출력한다. www.acmicpc.net 1. 문제 생각 기하 골드 문제로, 처음부터 괄호 문제랑 연관해서 떠올리지는 못했다..🤦 힌트도 오히려 수학 문제처럼 줘서 더 헷갈릴 수 밖에 없었는데, 역시 백준에서 수학 문제가 나오면 자료구조나 알고리즘적 접근을 더 의심해보는 게 좋은 방향인 것 같다. 이 문제는 괄호 문제와 비슷하게 해결할 수 있다. ( ( ) ) 괄호들이 색깔들로 주어진다고 응용해서 생각하면 되고, 주어지는 상황 속에서 같은 모양의 '('이 들어갔다면 같은 모양의 ')'가 들어가 '('를 상쇄시켜주면 된다는 점에서 stack이라는 구조를 사용한다는 걸 떠올릴 수 있다. 2. 문..
![]()
0. 문제 공항 10775번: 공항 예제 1 : [2][?][?][1] 형태로 도킹시킬 수 있다. 3번째 비행기는 도킹시킬 수 없다. 예제 2 : [1][2][3][?] 형태로 도킹 시킬 수 있고, 4번째 비행기는 절대 도킹 시킬 수 없어서 이후 추가적인 도킹은 불 www.acmicpc.net 1. 문제 생각 공항 도킹에 대한 한국어 풀이가 생각보다 이해가 잘 되지 않아 예제를 계속 읽고서야 이해가 되었다. 차라리 밑에 예제를 예제 2 : [2][1][3][?] 로 풀이 방법을 줬으면 더 이해가 잘 되었을텐데 😥 아무튼 이 문제의 핵심은 "i번째 비행기를 1번부터 gi (1 ≤ gi ≤ G) 번째 게이트중 하나에 영구적으로 도킹하려 한다. 비행기가 어느 게이트에도 도킹할 수 없다면 공항이 폐쇄되고, 이후..
0. 문제 문자열 화폐 17828번: 문자열 화폐 첫 번째 줄에 문자열의 길이 N(1 ≤ N ≤ 5,000,000)과, 문자열의 가치를 나타내는 정수 X(1 ≤ X ≤ 500,000,000)가 공백으로 구분되어 주어진다. www.acmicpc.net 1. 문제 생각 어떤 문자열을 채워나가는 과정이다. 간단하게 증명하여 AAA 특정 문자열 ZZZ로 그리디 과정을 거친다는 것을 알 수 있다. 아래 테스트케이스를 생각하면서 풀면 도움이 되었다. 6 50 AAAAZZ 6 55 AAAAYZ 6 156 ZZZZZZ 2. 문제 구현 import sys input=sys.stdin.readline N,X=map(int,input().split()) if N*26X: print("!") else: List=['A' fo..
![]()
0. 문제 두 로봇 15971번: 두 로봇 2018년 강원도에서 새로운 동굴이 발견되었다. 이 동굴에는 총 N개의 넓은 방이 존재하며 좁은 통로로 서로 연결되어 있는 것으로 밝혀졌다. N개의 방은 1번부터 N번까지의 번호를 붙여 1번 방, 2번 www.acmicpc.net 1. 문제 생각 한점 -> 여러 점의 최단거리를 구현할 수 있는 다익스트라를 사용했다. 다만 다익스트라 q에 넣을 때 (cost, 노드, 지금까지 나온 경로 중 최댓값)으로 가져가면서 풀었다. 입력값으로 받은 start부터 -> 모든 다른 점까지의 최단거리를 구한 후 이렇게 진행하면서 거쳐가게 되는 간선 중 가장 큰 가중치를 가지는 것들을 함께 가져갔다. 이후 start로부터 end까지의 거리인 distance[end]에서 max_di..
![]()
0. 문제 트리 4256번: 트리 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 노드의 개수 n이 주어진다. (1 ≤ n ≤ 1,000) BT의 모든 노드에는 1부터 n까지 서로 다른 번호가 매겨져 있다. 다음 www.acmicpc.net 1. 문제 생각 전위순회, 중위순회, 후위순회의 핵심은 규칙과 재귀이다. 재귀에서도 사실상 어디에서 재귀로 진입하는가(반환하는가) 가 가장 중요하다. -> 기초 설명 위 문제에서도 전위, 중위 순회일 떄 규칙적으로 왼쪽/오른쪽으로 빠지는 것이 규칙적으로 진행됨을 알 수 있다. 따라서 recursion을 전위, 중위 순회에 따라 root 노드 -> left 노드 -> right 노드로 들어가도록 구현하고 if (currentNode){ ..
0. 문제 후보 추천하기 1713번: 후보 추천하기 첫째 줄에는 사진틀의 개수 N이 주어진다. (1 ≤ N ≤ 20) 둘째 줄에는 전체 학생의 총 추천 횟수가 주어지고, 셋째 줄에는 추천받은 학생을 나타내는 번호가 빈 칸을 사이에 두고 추천받은 순서대 www.acmicpc.net 1. 문제 생각 1
![]()
0. 문제 별 찍기 - 11 2448번: 별 찍기 - 11 첫째 줄에 N이 주어진다. N은 항상 3×2k 수이다. (3, 6, 12, 24, 48, ...) (0 ≤ k ≤ 10, k는 정수) www.acmicpc.net 1. 문제 생각 규칙을 유추해보는 과정, 패턴을 파악하는 것이 그리 어렵지는 않았으나 마음처럼 뭉탱이로 구현할 수 없어 생각을 좀 더 했던 것 같다! 재귀적으로 패턴이 반복되는 것이 보여서 아래 종이에서 보이는 것처럼 12를 채우기 위해 6으로 쪼개서 나아가고 다시 6을 채우기 위해 3으로 쪼개서 나아가는 방법으로 분할정복 재귀를 써야겠다고 생각했다. 평소 그리는 분할정복의 로직은 아래와 같다. def div_conquer(): #가장 밑 분할 노드 도착했을 때 return #분할해서 ..
![]()
0. 문제 캠프 준비 16938번: 캠프 준비 난이도가 10, 30인 문제를 고르거나, 20, 30인 문제를 고르면 된다. www.acmicpc.net 1. 문제 생각 처음에는 투포인터일까? 싶었다. 하지만 투포인터는 각 요소가 모두 다를 때 효율적인데 입력값에서 배열이 [10, 10, 20, 10, 40] 으로 들어온다면 이는 별 효율이 없을 것 같았다. 이후 입력값이 고작 N= L and sum(List) = X: # print(List) ans+=1 #return하면 안됨 . => 한 번 더 가야할 수도 있으니까 for i in range(node+1, N): # 1 ~ N 까지 if not visited[i]: # 중복 확인 visited[i]=1 backtracking(i, visited,Lis..
![]()
0. 문제 스카이라인 쉬운거 1863번: 스카이라인 쉬운거 첫째 줄에 n이 주어진다. (1 ≤ n ≤ 50,000) 다음 n개의 줄에는 왼쪽부터 스카이라인을 보아 갈 때 스카이라인의 고도가 바뀌는 지점의 좌표 x와 y가 주어진다. (1 ≤ x ≤ 1,000,000. 0 ≤ y ≤ 500,000) 첫 www.acmicpc.net 1. 문제 생각 처음에는 스카이라인이라고 해서 라인스위핑이겠거니 하고 달려들었다! 하지만 예제를 보면 처참히 깨질 수 있는데.. 하나씩 순차적으로 파악하는 형태의 로직이 아니다. 즉, 앞에서의 상황이 뒤에 의존될 수 있다. 입력값에서 주어지는 것은 '스카이라인의 고도가 바뀌는 지점의 좌표 x와 y' 이다. 즉, 이 곳에서는 무조건! 고도가 바뀌어야 한다. 그렇다면 위 그림의 상황을..
![]()
1. 문제 개미 3048번: 개미 T초가 지난 후에 개미의 순서를 출력한다. 첫 번째 개미 그룹은 왼쪽에서 오른쪽으로 움직이고, 두 번째 그룹은 반대 방향으로 움직인다. www.acmicpc.net 2. 문제 생각 처음에는 규칙을 찾으려고 했다. T가 몇 번일 때 바뀌는 것과 바뀌지 않는 것들이 몇 번인지를 기준으로 찾아서 구현하려고 하였다. 이후 다시 보니 아래의 두 힌트가 명시적으로 N1과 N2가 굉장히 작고 T도 50밖에 되지 않아 빡구현이겠구나 하고 생각하였다. 3. 문제 풀이 N,M=map(int,input().split()) A=list(input()) B=list(input()) T=int(input()) start=A[::-1]+B for _ in range(T): flag=False; #..
![]()
0. 에필로그 원래 백준 문제는 블로그에 안 쓰고 개인적으로 정리했는데 코알라 면접 보다가 큰 영감을 얻어 열심히 기록해볼 생각이다! 👻 일주일에 적어도 5개는 풀어야징 1. 문제 https://www.acmicpc.net/problem/21278 21278번: 호석이 두 마리 치킨위의 그림과 같이 1번과 2번 건물에 치킨집을 짓게 되면 1번부터 5번 건물에 대해 치킨집까지의 왕복 시간이 0, 0, 2, 2, 2 로 최소가 된다. 2번과 3번 건물에 지어도 동일한 왕복 시간이 나오지만 더 www.acmicpc.net2. 생각 "모든 건물에서 가장 가까운 치킨집까지 왕복하는 최단 시간의 총합"을 최소화할 수 있는 건물 두 개를 고르는 문제이다. 우선 이 문제에서 요구하는 현상을 2차원 그래프로 표현할 수 ..
![]()
OpenAI 와 open API OpenAI에서 chatGPT와 관련한 open API를 배포하였기 때문에 이제 누구나 손쉽고 편리하게 ChatGPT API를 이용해서 애플리케이션을 제작할 수 있게 되었다. ChatGPT API와 Whisper API 연동 방법 API 사용법에 관련하여 공식 문서로 제공이 되어 있어 이를 공부해 구현해볼 수 있었다. 내가 지금껏 썼던 OPEN API는 보통 라이브러리 형식이라 다운로드하여 import해서 쓰는 형식이 많았는데, OpenAI에서 제공해주는 API는 HTTP 통신 형태로 CURL 명령어를 보며 이해해야 하는 과정이 있었다. CURL 명령어 curl(client url) 명령어는 프로토콜들을 이용해 URL 로 데이터를 전송하여 서버에 데이터를 보내거나 가져올때..
![]()
2023년 SO-HOT 해커톤 (공동해커톤 예선전) SW중심대학 공동 해커톤 본선 진출 학생을 선발하는 해커톤 예선전으로, 항공대학교 항공우주박물관 2층 비전홀에서 2박 3일동안 실시되었다. 2명~5명으로 이루어진 팀으로 출전 가능하다. 해커톤 참여 계기 지난 5월 5일 18시부터 부터 5월 7일 9시까지 진행하는 KAU SOHOT 해커톤에 아주 좋은 기회로 참여하게 되었다🤗 2022에 이어 2023에도 참여하게 되어 감회가 새로웠다..! 작년에는 1박 2일로 진행했는데 이번에는 2박 3일로 개발할 수 있는 시간이 길어져 좀 더 다양한 걸 시도해보고 싶다는 생각으로 임하게 되었다. 해커톤 주제와 아이디어 선정 과정 주제는 자유주제라 봐도 무방한 느낌의 '불가능을 가능하게' 였다. 팀을 짜고 나오는 거라,..
![]()
시간이 없는 관계로 문제 풀이로 대체한다..!!!! 😭😭 1. 라우터와 스위치의 유사점과 차이점을 설명하시오. 라우터 스위치 유사점 포워딩 테이블이 존재한다. 차이점 IP 주소로 포워딩하는 네트워크 계층 MAC 주소로 포워딩하는 링크 계층 IP와 MAC 주소를 가진다. 주소 없이 투명하다. 네트워크 관리자의 관리가 필요하다. self-learning으로 이루어진다. 계층구조 평면 구조 2. 스위치의 4가지 기능을 나열하고 각각에 대해 설명하시오. self-learning 1. 스위치 테이블은 초기에 비어있다. 2. 인터페이스로 수신(A->A')한 각 프레임에 대해 스위치는 프레임의 출발지 주소 필드에 있는 MAC 주소 / 프레임이 도착한 인터페이스 / 현재 시간 을 저장한다. 3. 일정시간(aging t..
