반응형 Coding Test/프로그래머스11 [ 프로그래머스 ] 정수 삼각형 파이썬python 풀이 //문제 요약 정수로 된 삼각형이 주어지면 아래로 이웃한 두 정수와 만 더해질 수 있다고 할때 가장 큰 합은 얼마인지 구하여라 //풀이 나는 이거 처음에 무조건 dfs 라고 생각했다. 그리고 완전 틀려먹고나서 그냥 그리디로 풀면 되는 문제라는걸 깨달았다. 코테를 준비하면서 점점 더 많이 느껴지는 것은 이 문제는 그리디다! DFS다! DP다! 이런게 처음에 배울땐 의미가 있지만 나중에 문제를 마주하면 크게 의미가 없다. 솔직히 그래프로 풀어서 정말 효율적인 문재들은 굉장히 소수의 문제이고 대부분의 경우에서 그리디 / 동적프로그래밍 으로 풀게 되는데 이것도 구분이 점점 모호하고.. 그냥 자신만의 어떤 스타일이 굳어지면 더 이상 구분하는 것도 의미가 없어진다. 다른 사람들과 소통하고 공식적인 자리에서 꼭 써야.. 2021. 6. 4. [ 프로그래머스 ] 2 x N 타일 파이썬python 풀이 //문제요약 1x2 짜리 타일을 이용해서 2xn 짜리 바닥을 모두 채우는 모든 경우의 수를 구해라. 단, 경우의 수가 매우 클 수 있으므로 1000000007 로 나눈 나머지를 반환해라. //풀이 한 시간 반을 씨름했는데 다른 사람 풀이 보고 너무 어이가 없게 풀려 버려서 기운이 쭉 빠지는 문제였다. 코드부터 보면 def solution(n): a, b = 1, 1 for _ in range(n - 1): a, b = (a + b) % 1000000007, a return a 끝이다. 나는 처음에 주어진n에대해서2로나눈몫과나머지를구한다음2의수와1의수를더한값의팩토리얼을2의수의팩토리얼과1의수의팩토리얼로나눈다음이걸2의수가0이될때까지줄이면서2의수가하나줄때마다1의수를2개늘려가면서구했는데이게너무숫자가크고오래걸리니까.. 2021. 6. 2. [ 프로그래머스 ] 자물쇠와 열쇠 파이썬python 풀이 // 문제 요약 돌려서 끼워 넣을 수 있는 M x M 열쇠가 있을때 돌릴 수 없는 N x N 의 자물쇠가 열리는지 안열리는지 확인해라. 단, 자물쇠의 열림 조건은 모든 값이 1 이되는가 이다. // 풀이 전형적인 브루투스 포스 (전체 탐색) 문제. 특히 N과 M 이 3 이상이면서 20을 넘지 않는 수로 주어지므로 충분히 for문을 여러번 사용해도 되는 문제라고 할 수 있다. 고고학자 튜브가 나와서 유치원생 문제처럼 그림을 그려놓았지만 사실은 복잡한 여러겹의 루프를 적절한 단위의 테스크로 나누고 각각 모듈화하여 조합할 수 있는가를 묻는 문제이고 최근 딥러닝 프레임워크들이 지향하는 바를 이해하고 구현할 수 있는가 물어보는 느낌도 받았다. 특히 Convolution생각이 많이 났다. 열쇠를 돌리는 과정에서는 .. 2021. 6. 2. [ 프로그래머스 ] 야근 지수 파이썬python 풀이 // 문제 요약 야근을 하면 남은 일의 업무량을 제곱한 만큼 피로도가 쌓인다고 할때 남은 근무시간과 업무량이 리스트로 주어지면 최소의 야근 피로도는 얼마인가 // 풀이 효율성까지 따지는 이번 문제는 알고리즘으로는 힙 문제라고 할 수 있는데 단순히 힙 문제라고 하기엔 거의 모든 알고리즘 문제가 그러하듯 수학적 사고력 문제라고 할 수 있다. 우선 수학적 접근으로 이 문제를 보면 합이 일정한 수들의 제곱의 합이 최소가 되도록 하는 방법은 무엇인가? 라고 할 수 있다. 이런 간단한 문제들은 조금만 생각해 봐도 엄청 어렵다는 것을 알 수 있는데 제한 조건이 1개인 상황이어서 수가 3개 이상만 되어도 일반적인 제곱의 합을 단 하나의 매개변수에 대하여 알아내기가 불가능하기 때문이다. 그래도 감을 잡기 위해서 그림으로.. 2021. 6. 1. [ 프로그래머스 ] 정렬 > 가장 큰 수 파이썬python 풀이 프로그래머스 문제는 풀기만 하고 정리를 안해서 아직 깃헙에도 못 올리고 있는데 이 문제는 쓰임이 많을것 같아 기억을 위해 정리를 해 두고 넘어가고자 한다. // 문제요약 0 또는 양의 정수가 주어졌을때, 정수들을 이어서 만들 수 있는 가장 큰 정수를 구해라. // 풀이 굉장히 쉬워보여서 금방 끝낼 줄 알았지만 완벽히 이해하는데 시간을 많이 들인 의외의 문제다. 코드를 먼저 보자. def solution(numbers): def sort_key(x: str) -> str: return (x*4)[:4] numbers = sorted([str(n) for n in numbers], reverse = True, key = sort_key) return str(int(''.join(numbers))) 내가 시도.. 2021. 5. 1. 이전 1 2 다음 반응형
