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

오늘의 문제 | 9655. 돌 게임이번 문제는 DP 문제라고 한다. 이미 풀었던 문제라 어떤 풀이로 풀어야 할 지를 떠올려보고, 예전 풀이와 간단하게 비교해보려 한다.아이디어: 베스킨라빈스 31베스킨라빈스 게임에서 상대방이 어떤 수를 말하든 무조건적으로 둘의 합이 4가 되게 하는 방법처럼, 유리한 고점을 차지한 이후로는 상대방이 말하는 숫자와 다른 숫자를 말하여 원하는 대로 합을 이끌어나갈 수 있다.시작은 상근이가 먼저하고, N을 4로 나눈 나머지를 체크하여 남는 숫자에 따라서 이기는 사람이 달라진다는 것을 알수 있다. 즉, 1 2 3의 케이스만 확인하면 된다. (1) 4의 배수인 경우: 상근이가 뭘 말하든 창영이는 합이 4가 되게 하면 되므로 CY(2) 나머지가 1인 경우: 상근이는 1을 말하면 무조건..

오늘의 문제 | 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..

오늘의 문제 | 프로그래머스: 모의고사오늘의 알고리즘은 완전 탐색이라고 하고, 수도 그리 크지 않아서 정말 하나하나 돌아보면 될 듯하다. 각 수포자마다 패턴이 정해져 있어서 (1) 몇 번 째 문제이고, (2) 그걸 패턴 길이로 나눈 나머지를 패턴의 인덱스로 생각해서 풀면 될 것으로 보인다.def solution(answers): p1=[1,2,3,4,5] p2=[2,1,2,3,2,4,2,5] p3=[3,3,1,1,2,2,4,4,5,5] a1,a2,a3=0,0,0 l=len(answers) for i in range(l): if p1[i%5]==answers[i]: a1+=1 if p2[i%8]==answers[i]: a2+=1 ..