무니화니

https://www.acmicpc.net/problem/1366 구현하기 굉장히 복잡한 문제였다. 조건들도 많고, 헷갈리거나 실수하기 쉬웠던 포인트들이 많았던 것 같다.우선적으로 제일 고민히 많이 되었던 포인트는 튜닝되어 있는 줄들을 코드로 만들기 위해서 각자 어떤 줄에 배치할지를 정하는 것이 고민이 많이 되었다.  itertools 라이브러리에 product라는 함수가 있다. 이를 통해 데카르트 곱을 구할 수 있었다.예시로 product('ABCD', repeat=2)를 이용하면, AA AB AC AD BA BB BC BD CA CB CC CD DA DB DC DD와 같은 output을 얻을 수 있다. 1번 입력을 예시로 들어보자. E A D G B E라는 음정을 E G# B로 만들어야 한다. 그래서..

https://www.acmicpc.net/problem/31864오늘 해설할 문제는 눈송이 탕후루 만들기라는 문제이다.먼저, 문제를 보았을 때, 제일 먼저 든 생각은 30만개의 눈송이와 30만개의 끝점들을 모두 brute force로 연산하면, 최소 30만의 제곱, 즉 900억개의 연산을 해야될 것으로 예상이 되었다. 이는 무조건적으로 시간 초과가 날 것임이 당연했다.그래서, 먼저 시작점인 (0,0)과 눈송이 사이의 기울기를 통해, 기울기를 key로, 좌표의 x값을 value로 갖는 dictionary를 만들어서, 끝점을 보고 몇 개의 눈송이를 가지는지 확인할 때 (0,0)부터 끝점까지의 기울기와 같은 기울기를 가진 눈송이들만 확인하는 방식을 채택하였다.하지만, 또 다른 문제점들이 있었다.(3,4)와 ..

https://www.acmicpc.net/problem/20955해당 문제를 바라보면, 뉴런들로 뇌가 이루어져 있고, 뉴런들은 시냅스를 통하여 연결된다. 하지만 뉴런들끼리 연결이 끊어졌고, 끊어진 시냅스들을 다시 연결하여 모두 뉴런들을 연결하려고 한다. 하지만, 뉴런들을 트리 형태로 연결하려고자 한다. 즉, 뉴런들끼리의 사이클이 존재하지 않아야한다. 하지만 여기서 중요한 점은, "연결되지 않은 두 뉴런을 연결하거나, 이미 연결된 두 뉴런의 연결을 끊는다"이다. 이미 연결된 뉴런들, 즉 시냅스들을 사이클이 발생될 경우 끊어내야 한다.이번 문제는 분리 집합을 이용한 문제였다.분리 집합을 형성해서, 뉴런들끼리의 연결 관계들을 검토한다. 연결 관계의 두 노드가 이미 같은 부모 뉴런을 가지고 있는 경우, 이 연..

저번 2023 SPC에서 나왔던 문제인데, 당시에는 마땅한 풀이법을 찾지 못했었다.이후 한 해가 지나고 다시 문제를 풀어보았다.https://www.acmicpc.net/problem/30627우선적으로, BFS를 이용한 완전탐색을 이용하여 풀이하였다. 먼저 문제 상황을 어떻게 정의할 지 많은 고민을 하였는데,리스트를 이용하여[1번 물의 위치, 1번 물의 온도], [2번 물의 위치, 2번 물의 온도],[진행 로그]]와 같은 방식으로 저장하였다. 즉, 시작할 때 1번, 2번 숙우에 온도 100인 물이 있으므로,[[1,100],[2,100],[]]처럼 초기에 정의할 수 있는 것이다.처음에 풀 때는, 단순히 빈 숙우로 물을 옮기면 된다고 생각하였다.그러므로 물이 들어있는 숙우에서 물이 없는 숙우로 옮기고, 반..

오늘 풀어볼 문제는 '내 집 마련하기' 이다.예전에 서강대학교 프로그래밍 대회에서 1번 문제로 나왔었던 문제인데, 조금 복잡했던 구현 문제이다. 우선적으로 조금 어려운 부분은, '문제를 정확하게 읽어야 된다'는 점이다.문제에 주어진 표현은 i번째 집에 A_i번 사람이 배정되어있다고 하는데, 즉 문제에 표현된 방식은 1번과 같은, 집 기준이다.하지만 문제에서 sorting 해야하는 것은 L번 사람부터 R번 사람, 즉 사람 기준이다.그렇기 때문에, 기준을 사람으로 변경해주어야 한다.먼저 이후 정렬을 통해서, 작은 집의 번호를 가진 사람이 작은 집에 살고, 큰 집의 번호를 가진 사람이 높은 번호의 집에 살아야 최적의 세금 감면 효과가 이루어지기 때문에, 오름차순으로 L번 사람부터 R번 사람의 집들을 정렬한다...

https://www.acmicpc.net/problem/25419이번 문제는 Nim Game의 일종인 '정수를 끝까지 외치자' 문제를 풀어보았다.처음에 가졌던 생각은, '돌 게임 https://www.acmicpc.net/problem/9655' 문제와 술 게임인 '배스킨라빈스 31'과 유사하다는 생각을 했었다.모두 님 게임과 같은 메커니즘을 가진 문제이다.먼저, 학생 1이 우선권을 가져서 먼저 정수를 부를 수 있다.부를 수 있는 수는 1부터 K까지이다.이후 학생 2는 학생 1이 부른 숫자에 + 1 부터 +k까지의 정수를 불러야 한다.그리고, 마지막 정수를 부르는 학생이 승리하는 문제이다.문제에 조금 애매한 표현이 있는데, '두 학생이 규칙에 맞게 플레이했을 때'이다. 각 학생이 부를 수 있는 정수들..

https://www.acmicpc.net/problem/30205 [30205번: 전역 임무김 병장이 소속된 특수부대는 전역을 하려면 특이하게 대대장으로부터 주어진 임무를 달성해야 한다. 김 병장이 받은 임무는 적군의 $1$번 기지부터 $N$번 기지까지 모두 순서대로 격파하는 것이www.acmicpc.net](https://www.acmicpc.net/problem/30205)이번 문제는 그리디 알고리즘을 이용하여 풀었다.n,m,p=map(int,input().split())for i in range(n): data=list(map(int,input().split())) data.sort() minusone=data.count(-1) temp=minusone for j in ..

한국말로 번역하자면, "당신은 정수로 이루어진 배열인 nums와 양의 정수 k 가 주어진다. 부분 수열 중 nums의 제일 큰 값이 최소 k번 이상 위치한 부분 수열의 개수를 return하라 여기서 부분 수열이란 배열 내 연속적인 원소들의 나열이다." 여기서 슬라이딩 윈도우 알고리즘을 사용하여 문제를 해결하였다. 슬라이딩 윈도우 알고리즘이란, 투 포인터 알고리즘의 일부이다. 슬라이딩 원도우는 연속되어있는 두개의 포인터가 사용되어 특정 조건을 해결하는 알고리즘이다. 여기서 정확히 말하면 슬라이딩 윈도우의 약간의 변형이다. 만약 해당 배열에서 제일 큰 원소의 값을 M이라고 하였을 때, 오른쪽 포인터가 M인 경우에는 슬라이딩 윈도우가 적용되어 왼쪽에 있는 포인터가 오른쪽으로 이동하지만, 만약 M이 아닌 경우에..

https://www.acmicpc.net/problem/15989 15989번: 1, 2, 3 더하기 4 정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 4가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다. 합을 이루고 있는 수의 순서만 다른 것은 같은 것으로 친다. 1+1+1+1 2+1+1 (1+1+2, 1+2+1) 2+2 www.acmicpc.net 전형적인 다이내믹 프로그래밍 문제이다. t=int(input()) for _ in range(t): n=int(input()) dp=[[1e10,0,0,0] for _ in range(10001)] dp[1][1]=1 dp[2][1]=1 dp[2][2]=1 dp[3][1]=2 dp[3][3]=1 if n

https://www.acmicpc.net/problem/2818 2818번: 숙제하기 싫을 때 상근이는 숙제가 너무 하기 싫어서, 숙제 한 달치를 걸고 창영이와 게임을 하기로 했다. 진 사람은 한 달동안 숙제 두 명분을 해야 한다. 상근이는 영리하게 자신이 어렸을 때, 하던 게임을 하자 www.acmicpc.net 구현 문제이다. 처음에는, 4개의 행 마다 같은 패턴이 반복된다고 생각했었다. 1번행 2번행 3번행 4번행 1번행 ... 하지만 이는 오답이다. 꼭 4행마다 패턴이 반복되는 것은 아니였다. 하지만, 한 행에서 4개 이상의 열이 존재하면, 이는 반복된다. 예를 들어, 1,4,6,3,1,4,6,3,.... 이런 식으로 말이다. dice=[4,5,1,2,6,3] dx=[0,0,1] dy=[1,-1..