Nine1ll_RE:code

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/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 을 만족하면 무조건 정..

https://www.acmicpc.net/problem/10815 위의 문제를 풀다가 이것 저것 생각하다가 풀이를 2개를 작성했는데간단하게 정리하려고 작성합니다.두 가지 풀이를 했습니다.문제를 먼저 보면, max(N)은 50만개, max(M)은 50만개라O(N^2)으로 시간복잡도가 넘어가는 순간 2500억번의 계산을 해야합니다.그러면 우리의 갓갓 PyPy3도 2초는 넘길 것 같습니다. (여기서는 O(N * M)이죠)그래서 이 문제 풀이의 핵심은 이중 for문을 사용하지 말고리스트 안에 들어있는 걸 확인해라!! 입니다.그러면 다른 방법은 많지만 저는 보통 딕셔너리와 이중탐색을 떠올립니다. (정답이 아닐 수 있지만뭐 제가 떠올리는 것들입니다.)딕셔너리의 서치 속도는 O(1)이니, 없는 카드만 신경쓰면 될 ..

문제 출처: https://www.acmicpc.net/problem/2003 2003번: 수들의 합 2 첫째 줄에 N(1 ≤ N ≤ 10,000), M(1 ≤ M ≤ 300,000,000)이 주어진다. 다음 줄에는 A[1], A[2], …, A[N]이 공백으로 분리되어 주어진다. 각각의 A[x]는 30,000을 넘지 않는 자연수이다. www.acmicpc.net 오랜만에 알고리즘.. 빅리더 교육을 받은 9주 동안 못푼 문제들을 푸는 시간을 가졌다. 문제를 그냥 단순하게 이중 for문을 사용하면 끝날줄알았는데, 시간초과.. 이중 for문을 돌려도, index로 끊는다고 해도 시간초과가 났다.. 결론은 아이디어가 문제였는데, for문을 돌다가 숫자가 원하는 m보다 작으면 끝나는 index를 늘려야했고, m..