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

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://school.programmers.co.kr/learn/courses/30/lessons/77486 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr이 문제의 enroll의 길이가 1만개가 전부라 단순하게 재귀함수를 호출하면 O(N^2) 졍도로 시간복잡도가 나오지 않을까? 라는 생각에 재귀함수 호출로 문제를 풀이하려고 시도했다. def to_parents(parents, moneys, name, earn_money): if parents[name] == "": moneys[name] += earn_money ..