오늘의 문제 | 2631. 줄세우기오늘 문제는 오랜만에 골드가 나왔다. 순서대로 배치하기 위해서 드는 최소 비용을 구하라고 했다. 약간은 그리디적이긴 한데, 아이디어가 이전에 풀었던 알고리즘과 비슷하다는 생각이 든다.아이디어: 가장 긴 증가하는 부분 수열우선 우리가 옮기지 않아도 되는 친구들의 수를 최대화시키는 방법을 떠올릴 수 있다. 오름차순으로 정렬하기 위해서, 증가하는 수열을 제외한 나머지만 옮기는건 무조건 이득이라는 것을 알 수 있다. 다만 이게 무조건적으로 최소값인지는 약간은 의문이 들기는 한다.n=int(input())l=[int(input()) for i in range(n)]dp=[1]*(n+1)for i in range(n-1): for j in range(1,i): i..

오늘의 문제 | 9461. 파도반 수열DP라고 생각하고, 약간은 피보나치와 비슷하다는 생각이 들었다. 초기 5개까지는 그대로 반영되지만, 그 이후부터는 이전 5개 전의 사이즈와 바로 전 사이즈의 합만큼이 추가된다는 것이다. 물론 N이 작아서 크게 문제될 건 없겠지만 전처리로 100까지의 모든 값을 구하고 접근하려 한다.dp=[0,1,1,1,2]for i in range(4,101): dp.append(dp[i-4]+dp[i])for i in range(int(input())): print(dp[int(input())])솔직히 너무 쉬워서 아쉽긴했다. 단순한 피보나치를 구현하는 정도의 난이도였다.오늘의 회고DP 문제가 어제에 비해 너무 쉬워졌다. 물론 이거보다 어려운 DP 문제였다면 조금 골치아..

오늘의 문제 | 11722. 가장 긴 감소하는 부분 수열이 문제가 DP라고 하니 약간 머리가 아파졌다. 처음에는 그냥 뒤집에서 작은 거까지 내려오도록 하면 될 줄 알았으나, 생각보다 찾기 어렵지 않을까 하는 생각이 들었다. 하지만 N이 작기 때문에, 전부다 검사해도 되지 않을까 라는 생각도 든다.뭔가를 저장해놔야 접근이 가능할 것으로 보인다. 각 숫자를 시작점으로 생각했을 때의 길이를 생각하면 되는 것일까?가장 긴 증가하는 부분 수열을 반대로 해결하는 문제이다. 그렇다면 가장 긴 건 어떻게 구해야할까?LIS (Longest Increasing Subsequence)결국 순회화며 각 원소가 포함된 수열 중 가장 긴 것을 찾아내는 것으로부터 시작한다는 걸 검색으로 부터 알아냈다… 예전에 가장 긴 증가하는 부..

오늘의 문제 | 2116. 주사위 쌓기import sysfrom collections import dequeinput=sys.stdin.readline# 0 1 2 3 4 5# 5 3 4 1 2 0n=int(input())l=deque([[*map(int,input().split())] for i in range(n)])connect=[5,3,4,1,2,0]# 시작 지점 6군데를 모두 돌리는 것으로 시작함.start=l.popleft() if n==1: print(6)# 1개면 그냥 가장 큰 수 출력함else: maxv=0 # 전체 최고 값 for st in range(6): # 각 시작점마다의 최고값을 구함 tnum=start[st] # ..

오늘의 문제 | 프로그래머스: 전력망을 둘로 나누기이번 문제는 그래프인가 했으나 읽어보니 완전 탐색 문제이긴 하다. 트리 형식이라길래 자식 노드가 2개만 있을까 했는데, 그림을 보니 개수에 제한은 없는 듯하다. 그래도 순환 형태는 없는 형태이기에 아래 아이디어로 해결하면 될듯하다.아이디어: 루트 노드에서 뻗어나가서 만들어지는 개수를 확인하자.각 노드를 루트라 생각하고, 뻗어나갈 수 있는 개수를 파악해보려 한다. 약간은 DFS를 써서 최대 깊이를 알아볼 필요가 있어보이긴 한다.from collections import dequedef bfs(start,graph,visit): d=deque([start]) visit[start]=1 idx=0 while d: node=d...

오늘의 문제 | 프로그래머스: 소수 찾기우선 소수 관련 문제이므로 소수 체크하는 함수가 필요하다. 또한 순서 상관없이 문자열을 만들어야 하므로 이번에도 itertools를 이용해야 하지 않을까하는 생각이 든다.아이디어: 길이 별로 permutations를 돌려서 모든 경우의 수를 만들어내자하지만 이 아이디어의 치명적인 문제는, 모든 문자열 기준으로 돌릴 경우 이미 검사한 숫자도 나올 수 있다는 것이다. 그래서 visit 배열을 따로 선언하여 답으로 나오지 않은 숫자만 확인했다.from itertools import permutationsdef isPrime(number): if number오늘의 회고오늘 문제도 초반에 약간 힘들었다. 어떻게 완전 탐색을 돌려야 시간 초과 안나면서 중복없이 확인할 수..

오늘의 문제 | 프로그래머스: 피로도어쩌다보니 오늘도 프로그래머스 문제이다. 이러면 백준 스트릭 채우려면 1문제를 더 풀어야하는데… 라는 생각이 들기도 하고 여태까지 풀었던 프로그래머스 문제들 중 크게 어려운 문제가 없어서 더 실망하는 듯하다. 특히 이번에도 브루트포스라 난이도가 그리 어렵지 않을 듯하다.아이디어: 결국은 완전탐색. 8!이면 수가 4만 정도밖에 되지 않음.말 그대로 전부다 한번씩 선택하여 돌려봐도 시간 초과가 날 일은 없다는 것이다. 그래서 무지성으로 코드를 짜보면 되겠다고 생각했다.def solution(k, dungeons): answer = 0 for dungeon in permutations(dungeons): for go in product([0,1..

오늘의 문제 | 프로그래머스: 카펫이게 왜 완전 탐색인지는 모르겠다. 사실 수학적으로도 충분히 풀만해보이지만 수학적으로 푸는 과정이 완전 탐색인듯 하다. 이번에도 거의 브론즈1에서 실버 하위 정도의 문제라 사실 어렵게 풀 거 같지는 않다.갈색의 모서리 부분을 제외하고, 나머지는 모두 노란색의 둘레를 뜻한다.노란색의 가로와 세로 길이를 변인으로 두고, 갈색을 통해 둘의 합을 알기에 구할 수 있다.def solution(brown, yellow): answer = [] b=(brown-4)//2 for i in range(1,b): if i*(b-i)==yellow: answer=[b-i+2,i+2] break return answer..