Nine1ll_RE:code

유클리드 호제법은 최대 공약수를 구할 때 사용하는 방식이다. 유클리드 호제법은 2개의 자연수 또는 정식의 최대 공약수를 구하는 알고리즘의 하나이다. 호제법이란 말은 두 수가 서로 상대방 수를 나누어서 결국 원하는 수를 얻는 알고리즘을 나타낸다. 작동 원리는 두 개의 자연수 a,b가 (a>b) 있다고 하고, a를 b로 나눈 나머지를 r라고 하면 a와 b의 최대 공약수는 b와 r의 최대 공약수와 같다. 이 성질에 따라, b를 r로 나눈 나머지 r2를 구하고 r을 r2로 나눈 나머지 r3...를 구하는 과정을 반복해서 나머지가 0이 되었을 때 나누는 수가 a와 b의 최대 공약수이다.간단하게 코드로 표현하면 이런 식이다.def greatest_common_divisor(n1, n2): while n2 !=..

https://www.acmicpc.net/problem/81110과 1문제를 살펴보면, 간단한 BFS문제처럼 보인다. 예전에도 비슷한 문제를 푼 적이 있습니다. https://writedown-remain.tistory.com/63백준 16953: A -> B.간단한 BFS 문제입니다.만들 수 있는 모든 경우의 수를 BFS로 탐색해 연산의 횟수를 출력하면 됩니다.크게 다르지 않은 문제 형태입니다.조건이 조금 다르긴 하지만요.1로 시작해야 하고, 그 이후에 0과 1이 계속 붙어서 약간의 이진수처럼 숫자를 구성해야 합니다.그리고 그 숫자는 입력받은 n으로 나눠저야 합니다.따라서 밑의 코드처럼 매우 간단하게 풀 수 있을 줄 알았습니다. (간단했으면 플레티넘 문제가 아니겠지요?)import sysfrom co..

https://www.acmicpc.net/problem/16953뭐 사실 재미있는 문제인가? 라고 했을 때재미있다고 하기는 어렵구 이런 것도 그래프로 풀 수 있다는 걸 깨달아서,문제가 안풀리면 사실 문제 분류를 보는데 이 문제는 문제 분류를 보고 '이게 왜 이렇게 분류되어있지? 라는 생각이 들었다. 예전 생각은 '거꾸로 계산해서 넘어오면 되는거 아닌가?'라는 생각을 했었다.그러니까 예시로 보여주면'''입력값1 : 2 162 162 : 끝이 1이 아니기 때문에 무조건 // 281 : 끝이 1이니까 1을 때버림8 : 끝이 1이 아니기 때문에 무조건 // 24 : 끝이 1이 아니기 때문에 무조건 // 22 : 완성 => 만들 수 있음 입력값2 : 4 4242 : 끝이 1이 아니기 때문에 무조건 // 221 ..

https://www.acmicpc.net/problem/14502발상은 쉽지만, 간단하다고 말하기는 어려운 문제입니다.dfs로 풀었는데 python 시간 초과, pypy3 3043ms그래서 조금 정리를 하려고 가져왔습니다.첫 발상은 모든 빈 공간에 벽을 차례차례 세워보고바이러스가 퍼질 공간을 dfs로 확인 한 다음0의 개수를 count해서 max를 출력하면 되지않을까? 입니다.그래서 밑의 코드처럼 구현했습니다.import sysn, m = map(int, sys.stdin.readline().split())data = []temp = [[0] * m for _ in range(n)]for _ in range(n): data.append(list(map(int, sys.stdin.readline()..

https://www.acmicpc.net/problem/24479맨날 dfs, bfs 이해하기도 어렵고 복잡해서 싫었는데뭐 이것도 코딩테스트 진짜 자주 나오니까, 그리디보다 자주 나오니까 해야 한다.일단 문제부터 봅시다.보면 간단한 dfs + "방문 순서"를 출력하는 문제입니다.✱참고✱dfs는 구현 방법이 인접 리스트와 인접 행렬 이렇게 2가지가 있습니다. 인접 리스트인접 행렬장점연결 된 관계만 저장하기 때문에 메모리의 낭비를 줄인다모든 관계를 다 저장하기 때문에 연결을 확인하는 속도가 빠르다단점연결을 확인하는 속도가 느리다메모리 낭비가 심하다저는 처음에 간단하게 인접 리스트 방식을 사용해서 구현했습니다.import sysdef dfs(graph, v, visited, answer, rank): ..

https://www.acmicpc.net/problem/2346아니 이거 푸는데 너무 오래 걸려서 옛날에 푼 거를 봤는데리스트 크기가 바뀔 때, 인덱스를 출력해야 하는 문제를 맨날 못 풀었던 거 같아서 정리를 하려고 가져왔습니다.이건 발상도 오래걸렸고, 코드 구현도 마지막에 가서 헤매었어요..발상부터 다 갈아엎고 나서 다시 풀었습니다.코테에 이런 문제 나오면.. 어휴 정말 끔찍하네당하기 전에 정리해야지문제는 간단합니다. 풍선 속에 숫자가 있고 터트린 풍선에 있는 숫자만큼 이동하는 상황입니다.터뜨린 풍선은 제외하고 움직입니다.제 발상은 딕셔너리로 위치를 처리하고큐로 풍선 움직임을 구현하자였습니다.import sysfrom collections import dequen = int(sys.stdin.read..

https://www.acmicpc.net/problem/24511 오래간만에 재미있는 문제를 발견해서 블로그를 적습니다.시간복잡도 + stack과 queue에 대해 생각해 볼 만한 문제입니다.위에서 문제 설명을 보자면 queuestack 안에는 k개의 queue, n-k개의 stack이 들어있습니다.그리고 그 자료구조에는 각각 원소가 하나씩 들어있고 원소를 넣었다 뺐다가 해서 마지막에 나오는 Xn을 구하라는 이야기인 것 같습니다.문제 이해가 조금 어렵습니다.예제를 가져와서 설명해드리겠습니다.여기서 queuestack에 있는 자료구조는 queue stack stack queue입니다.자료구조큐스택스택큐원소1234이제 2를 queuestack에 집어넣어 보겠습니다.자료구조큐스택스택큐원소1, 2234자료구조..

https://www.acmicpc.net/problem/11478 set의 경우 해시맵으로 구현이 되어 있으며, 해시 충돌이 일어날 경우 선형 탐색을 하기 때문에 worst case의 시간복잡도가 O(N)입니다.위쪽 코드는 모든 길이의 substring을 하나의 해시맵에 넣어 해시 충돌이 일어날 가능성이 높고, 아래 코드는 길이별로 substring을 따로 세기 때문에 해시 충돌이 일어날 가능성이 더 낮습니다. # (속도:약 500ms)s = input()subset = set()for i in range(1, len(s)+1): for j in range(len(s)-i+1): subset.add(s[j:j+i])print(len(subset))# (속도: 약 200ms)def su..

https://www.acmicpc.net/problem/1715코딩 테스트를 준비하면 필수로 알아야하는 문법을 가져왔습니다.아이디어는 매우 간단한 문제입니다.누가 봐도 중복으로 계산되는 값이 최대한 작게 만드는 문제고따라서 작은 것들부터 계속 더해가는 그리디로 풀어야하는 것을 알 수 있습니다.그런데! 여기서 문제가 생겨요."작은 것부터 더해? 그러면 정렬을 계속 해야하나?"계속 더해줘야 해서 무조건 반복문이 들어갑니다. 그래서 O(N)은 강제 할당이고O(N)을 반복문 안에서 한 번 더 써버리면 무조건 시간초과가 납니다.문제는 List의 min(), sort() 모두 시간이 O(N)이라는 겁니다.import sysn = int(sys.stdin.readline())cards = []for _ in ran..

https://www.acmicpc.net/problem/1789문제가 재미있어서 가지고 왔습니다.엄청 간단한 문제인데, 정작 아이디어를 떠올리는데 오래 걸렸어요.여기서 아이디어가 간단하게 나온 분들도 있을 것 같은데 저는 그냥 i부터 i+N개까지 다 더한게 200이 되면 되는거 아닌가? 라는 단순한 생각을 했습니다.그런데, 코드를 짜고 200을 넣고 해보니, N = 16이 최대 값이더라구요?거기에 i를 증가시켜야하고 덧셈의 결과도 계산해야하니, 시간복잡도가 O(N^2)이 나올 것 같아서 문제의 S의 범위를 보면 절대 불가능한 코드였습니다.고민을 조금 하다보니, 1 ~ N까지의 자연수의 합 공식이 떠올랐고, 1 ~ N까지의 자연수의 합 = n(n+1)/2​n(n+1)/2 ≤ S^2 을 만족하면 무조건 정..