오구의코딩모험

문제 3줄 요약 1. 두 묶음(A,B)의 숫자 카드를 합치려면, A+B 만큼의 비교가 필요하다. 2. A(10), B(20), C(40) 세 묶음을 비교하는 최소는(A(10)+B(20)) + (A+B(30)+C(40)) = 100이다. 3. N개의 숫자 카드 묶음의 최소 비교 수는 몇 일까? 비교 횟수가 최소가 되는 경우는 묶음의 수가 작은 묶음끼리 비교하는 것이다. 왜냐하면! 더해진 묶음을 결국 다른 묶음과 비교를 해야하는데, 숫자가 많은 카드 묶음은 가장 나중에 비교를 하는만큼 그 숫자만큼 덜 더한다. 그렇다면, 카드 묶음을 오름차순으로 정렬하고 더해주는 것을 반복해주면 되지 않나? 매번 비교를 해준 결과를 반복문을 통해 자리를 찾아주거나, 리스트의 첫 번째 원소를 가져오는 pop(0)을 연산을 할 ..

문제 3줄 요약 1. 문자열에서 지워야할 '폭발 문자열'이 라는 것이 있다. 2. 위의 3 가지 과정으로 폭발이 진행된다. 3. 폭발이 끝난 후, 남은 문자열을 출력하되 남은 문자가 없을 경우엔 "FRULA"를 출력한다. Python에는 문자열에서 문자를 지울 수 있는 replace 함수가 존재하지만... replace를 사용하여 구현한다면? 펑 시간 초과가 터져버린다. 최대 길이가 100만인 문자열을 replace로 지워가며 새로운 문자열까지 검색하는 과정이 있다보니 100만 * 검색횟수 만큼 시간이 소요된다고 생각된다. 그래서 생각해낸 방법은 이해를 돕기위해 허접한 그림판에 써보았다. Input이 ACCBB고 폭발 문자열이 CB라면, 1차 폭발 후, ACB 2차 폭발 후, A가 될 것이다. 위 과정을..

문제 3줄 요약 1. 두 문자열이 주어진다. 2. 문제가 간단하구만? 3. 두 수열 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾아라 문제 이름처럼 최장 공통 부분 수열을 구하는 LCS 알고리즘 문제이다! LCS가 무엇인지 모른다면, 아래 링크를 참고하면 좋을 것 같다! https://m.blog.naver.com/PostView.naver?isHttpsRedirect=true&blogId=power2845&logNo=220677085876 [Python] LCS 알고리즘(Longest Common Subsequence) LCS 알고리즘(Longest Common Subsequence) 특징 LCS 알고리즘은 두 열(Sequence) S1과 S... blog.naver.com 짧게 설명 해본다면, ..

문제 3줄 요약 1. 새로운 언어인 AC에는 R(배열의 순서 뒤집기), D(첫 번째 값 버리기) 기능이 있다. 2. 배열이 비어있는데, D를 사용하면 ERROR 3. 최종 결과를 구해라 문제를 읽어가며.. 뒤집기는 reverse, 버리기는 pop.. 너무 쉬운데? 라고 생각하자마 배열의 개수 n이 최대 10만..! (0 ≤ n ≤ 100,000) 모든걸 고려하고 작성한 첫 제출은.. 런타임 에러? 질문 게시판을 보니, 필독 문서가 내 모든 궁금증을 해결 해주었다. https://www.acmicpc.net/board/view/25456 글 읽기 - ★☆★☆★ [필독] AC FAQ ★☆★☆★ 댓글을 작성하려면 로그인해야 합니다. www.acmicpc.net 출력에 띄어쓰기가 없다는 점, 비어있는 배열은 "..

문제 3줄 요약 1. 0은 익지 않은 토마토, 1은 익은 토마토, -1은 빈 칸 2. 익지 않은 토마토는 익은 토마토 옆(상하좌우)에서 하루 뒤에 익는다. ex [1 0] → 1 일 후 → [1 1] 3. 모든 토마토가 익을려면 몇 일이 걸릴까? 모두 익지 못하는 상황이라면 -1 출력 문제 자체는 BFS를 사용하면 크게 어렵지 않았다고 느꼈지만... BFS를 재귀를 이용하여 구현하여 막상 제출하니 런타임에러(Recursion Error)가 발생하였고, 재귀를 반복문으로 고쳐주니 시간 초과가 발생하였다.. ㅠㅠ 탐색할 자료구조를 처음엔 큐가 아닌 리스트를 큐를 대신하여 값을 빼주고 넣고 하였는데, 여기서 List의 pop(0)가 얼마나 무시무시한 시간 복잡도 인지를 알고 있지 못했다.. C++의 vecto..

문제 3줄 요약 1. 치킨 거리는 집과 가장 가까운 치킨집 사이의 거리이다. 2. 두 칸 (r1, c1)과 (r2, c2) 사이의 거리는 |r1-r2| + |c1-c2| 3. 치킨집을 최대 M개 골라 도시의 치킨 거리의 합이 가장 작을 때의 값을 구하라! 문제 풀다가 보니 치킨이 먹고싶다는 생각이 들기도 했다. 주변에 치킨 집이 참 많은데, 어쩌면 이 문제는 한 번쯤 생각해봤던 문제인 것 같다 ㅋㅋ 아무튼 문제로 돌아가서! 전에 풀었던 연구소 문제에서 벽을 미리 세워두듯이, 이번 문제에서도 최대 M개인 치킨집을 미리 골라두고 도시의 치킨 거리의 합을 작은 값으로 갱신해주는 방법을 생각하였다. 최대 M개의 치킨집은 combination을 이용하여 경우의 수를 모두 고려해주었다. from sys import..

문제 3줄 요약 1. 로봇 청소기가 청소를 한다. 2. 위의 3 가지 패턴을 반복하며 작동한다. 3. 로봇 청소기가 멈출 때까지 청소한 칸의 개수를 출력하라 내용이 길지만, 기능을 차근차근 하나씩 구현해보자! from sys import stdin ## 1번 기능 : 해당 칸 청소 def func_1(input_list,room): x = input_list[0] y = input_list[1] if room[x][y] == 0: room[x][y] = 2 return 1 return 0 ## 2번 기능 : 상하좌우가 청소된 경우 def func_2(input_list,room): x = input_list[0] y = input_list[1] direction = input_list[2] ## Righ..

문제 3줄 요약 1. 0은 빈칸, 1은 벽, 2는 바이러스 2. 벽이 세워지지 않는 빈칸에는 바이러스가 퍼진다. 3. 3개의 벽을 세워 바이러스 퍼지는 것을 최소화해라! 3개의 벽을 세울 수 있는 모든 경우의 수를 브루트포스 알고리즘을 이용하고 벽을 임의로 세우고 난 후, 바이러스를 BFS로 확산시켜 남아 있는 빈칸의 수를 최대가 나올 때까지 갱신시킨다. from sys import stdin # 좌표 넣을 구조체 class XY: def __init__(self, x, y): self.x = x self.y = y # 바이러스 확산 def BFS(copy_list, two): Q = [] for check in two: Q.append(check) ## 상하좌우로 확산 while(len(Q) != 0)..

문제 3줄 요약 1. A0 = 1 2. i 번째 값 = ⌊i/P⌋ 번째 값 + ⌊i/Q⌋ 번째 값 3. ⌊ x ⌋ = x를 넘지 않는 가장 큰 정수 ⌊ ⌋ 가 오타인가 싶었지만, 아래 힌트를 보니 위의 설명과 같은 기호였다. 위의 기호는 i/P 와 같은 나눗셈에서는 소수점을 지운 값 즉, 몫에 해당한다. 따라서 피보나치 함수에서 사용했던 상향식과 메모리얼을 이용하여 값을 구해주었다. from sys import stdin # 상향 접근 + 메모리얼 def func(num): if num == 0: return 1 else: if num//P not in num_dict: num_dict[num//P] = func(num//P) if num//Q not in num_dict: num_dict[num//Q]..

문제 설명 3줄 요약 1. 지민이는 과장해서 이야기하는 것을 좋아한다. 2. 그 이야기의 진실을 아는 사람을 최대한 피해서 과장되게 이야기 하고싶다. 3. 최대 몇개의 파티에서 과장되게 이야기할 수 있을까 처음엔 문제를 굉장히 쉽게 생각하여 set로 파티 인원과 진실을 아는 사람의 중복을 제거 하는 것으로 접근하려 했으나, 진실을 아는 인원과 파티를 즐긴 사람도 곧, 진실을 알게되는 인원인 것을 고려해주지 않았다는 것을 깨달았다. 때문에 진실을 아는 인원을 각 파티에 참여했던 인원을 반복해서 탐색하며 갱신해주고, 최종적으로 과장되게 이야기할 수 있는 파티의 수를 카운트 해주었다. from sys import stdin if __name__ == "__main__": ## 사람의 수 N, 파티의 수 M N..