안녕

0. 문제 링크 https://www.acmicpc.net/problem/5052 5052번: 전화번호 목록 첫째 줄에 테스트 케이스의 개수 t가 주어진다. (1 ≤ t ≤ 50) 각 테스트 케이스의 첫째 줄에는 전화번호의 수 n이 주어진다. (1 ≤ n ≤ 10000) 다음 n개의 줄에는 목록에 포함되어 있는 전화번호가 www.acmicpc.net 1. 풀이 방법 굉장히 찝찝하게 풀었다. 정렬을 이용해서 풀었는데, 파이썬은 문자열을 길이가 아닌 사전 순대로 나열해서 정렬을 해준다. 그래서 정렬을 해서 직전 문자열이 다음 문자열의 부분이 되는가만 파악하면 된다. 나는 좀 거창한 풀이를 생각했는데, 생각보다 간단해서 허무했다. 사실 숫자의 트리를 만들어서 풀려고 했다. 예를 들어 911 다음에 91112..

0. 문제 링크 https://www.acmicpc.net/problem/1715 1715번: 카드 정렬하기 정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장 www.acmicpc.net 1. 풀이 방법 이 문제는 감이 중요할 것 같은 문제이다. 행렬의 곱셈 연산에서 생각했을 때, DP로 풀어야 될 것 같지만 정답은 그리디로 풀어야 하는 문제이다. 아래의 코드에서 써놓았는데, i < j < k라고 가정했을 때, 최소 연산은 당연히도 (i + j) + (i + j + k) = 2 * (i + j) + k이다. i + k를 먼저 수행한다면, 2 * (i ..

0. 문제 링크 https://www.acmicpc.net/problem/1577 1577번: 도로의 개수 첫째 줄에 도로의 가로 크기 N과 세로 크기 M이 주어진다. N과 M은 100보다 작거나 같은 자연수이고, 둘째 줄에는 공사중인 도로의 개수 K가 주어진다. K는 0보다 크거나 같고, 50보다 작거나 같은 자 www.acmicpc.net 1. 풀이 방법 일단 맨 처음에는 BFS로 문제를 풀었는데, 시간 초과, 메모리 초과가 발생하였다. BFS가 아님을 깨달았고, 고등학교의 확통에서 비슷한 문제를 풀었던 경험이 생각났다. 현재 위치로 올 수 있는 애는 내 좌측과 위이므로, 좌측과 위로 갈 수 있는 경우의 수를 더하면 현재 위치에 도달할 수 있다.는 것이 확통에서 문제를 푼 방법이다. 물론 조합을 사용..

0. 문제 링크 https://www.acmicpc.net/problem/2110 2110번: 공유기 설치 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 www.acmicpc.net 1. 풀이 방법 내 기준 가장 신박했던 문제 문제 유형은 이분 탐색 + 매개 변수 탐색이다. 이 유형은 최적화 문제를 결정 문제로 바꿔서 푸는 문제이다. 그렇다면 어떤 부분이 최적화일까? 를 먼저 생각해야 하는데, 문제에 나와있듯이 가장 인접한 두 공유기 사이의 '최대 거리'이다. 그러면 이 부분을 결정 문제로 바꿔야 하는데, ..

0. 문제 링크 https://www.acmicpc.net/problem/21925 21925번: 짝수 팰린드롬 (1, 1), (5, 6, 7, 7, 6, 5), (5, 5) www.acmicpc.net 1. 풀이 방법 스택이 비어있다면, 매 숫자마다 스택에 넣는다. 그리고 다음 숫자로 이동한다. 만약에 스택에 숫자가 들어가 있다면, 스택의 길이를 측정한다 -> l 현재 숫자의 위치인 cur과 스택의 마지막 숫자를 비교하며 좌우로 넓혀가며 팰린드롬을 만족하는지 확인한다. 이때 스택의 길이가 남은 숫자의 길이보다 길다면 이 또한 팰린드롬을 만들 수 없다. 만약 스택에 들어있는 숫자 3개와 현재 숫자의 위치인 cur에서 cur + 2까지의 3개의 숫자가 팰린드롬을 만족한다면, 스택을 모두 비운다. 그리고 T..

.data equation : .space 256 equal : .string "=" error_msg : .string "incorrect operation !" comma : .string ", " # ------------------------------------------------------------------------------------ # [KNU COMP0411 Computer Architecture] Skeleton code for the 1st project (calculator) # ------------------------------------------------------------------------------------ .text # main main: jal x1..

0. 문제 링크 https://www.acmicpc.net/problem/1484 1484번: 다이어트 성원이는 다이어트를 시도중이다. 성원이는 정말 정말 무겁기 때문에, 저울이 부셔졌다. 성원이의 힘겨운 다이어트 시도를 보고만 있던 엔토피아는 성원이에게 새로운 저울을 선물해 주었다. www.acmicpc.net 1. 풀이 방법 투포인터 주석에도 적어놓았듯이, k^2 - (k-1)^2의 값이 n보다 크게 되는 순간 더 이상 해당 값은 볼 필요가 없음 따라서 n - 1까지만 투포인터로 보기로 했고, 이때 n이 1, 2인 순간은 오류가 발생하는데 해당 값은 아래의 while 문에서 해결함 아무튼 1 ~ n - 1까지의 값을 모두 제곱하여 리스트에 넣어놓았음 maps[right] - maps[left]를 했을..

0. 문제 링크 https://www.acmicpc.net/problem/2015 2015번: 수들의 합 4 첫째 줄에 정수 N과 K가 주어진다. (1 ≤ N ≤ 200,000, |K| ≤ 2,000,000,000) N과 K 사이에는 빈칸이 하나 있다. 둘째 줄에는 배열 A를 이루는 N개의 정수가 빈 칸을 사이에 두고 A[1], A[2], ..., A[N]의 순서로 www.acmicpc.net 1. 풀이 방법 현재까지의 누적합 값을 구함. 해당 누적합 값 - k의 값이 딕셔너리에 존재한다면 개수만큼 정답에 더하면 됨 0이 들어갈 수도 있으므로 누적합 값이 키로 있는 딕셔너리 값도 계속해서 업데이트해줘야 함 2. 코드 import sys input = sys.stdin.readline def bf(): c..

0. 문제 링크 https://www.acmicpc.net/problem/2665 2665번: 미로만들기 첫 줄에는 한 줄에 들어가는 방의 수 n(1 ≤ n ≤ 50)이 주어지고, 다음 n개의 줄의 각 줄마다 0과 1이 이루어진 길이가 n인 수열이 주어진다. 0은 검은 방, 1은 흰 방을 나타낸다. www.acmicpc.net 1. 풀이 방법 다익스트라 구글에 일요일 아침의 데이트 파이썬을 검색하면 나오는 풀이와 흡사하게 풀었음. 일단 검은 방은 전처리로 10,000으로 설정하였음. 최대 50 * 50이 맵 사이즈가 되기 때문에 2500 이상으로 설정하면 됨. 이후 힙을 이용한 다익스트라로 목적지까지 최소 거리를 구하면 됨 최종적으로 목적지에는 검은 방 * 10,000 + 흰 방 * 1의 값이 저장되는데..

0. 문제 링크 https://www.acmicpc.net/problem/1596115961번: 회전 초밥첫 번째 줄에는 회전 초밥 벨트에 놓인 접시의 수 N, 초밥의 가짓수 d, 연속해서 먹는 접시의 수 k, 쿠폰 번호 c가 각각 하나의 빈 칸을 사이에 두고 주어진다. 단, 2 ≤ N ≤ 3,000,000, 2 ≤ d ≤ 3,000, 2 www.acmicpc.net2023.05.15 - [Computer Science/알고리즘] - [백준 - Python] 2531 - 회전 초밥 [백준 - Python] 2531 - 회전 초밥0. 문제 링크 https://www.acmicpc.net/problem/2531 2531번: 회전 초밥 첫 번째 줄에는 회전 초밥 벨트에 놓인 접시의 수 N, 초밥의 가짓수 d,..