반응형 알고리즘6 [ 프로그래머스 ] 110 옮기기 파이썬python 풀이 // 문제요약 0과 1로 이루어진 문자열이 하나 이상 주어지면 각 문자열의 부분 문자열 중 110에 해당하는 부분을 추출하여 위치를 바꾸는 과정을 거친다고 할때 사전 순서에서 가장 앞서는 문자열들을 찾아 반환하여라 // 사고 '사전순서'라하면 dfs가 번뜩 떠올랐지만 주어지는 문자열의 길이가 어마어마해서 다른 방식으로 접근해야한다고 생각했다. 만약 다른 문제에서 '사전순서'를 미리 만나지 못했다면 문제를 이해 하는데만 엄청 오래 걸렸을 것이다. 그래도 조금씩 성장하는 모양이다. 110 의 경우는 이미 사전순서로 배열이 잘 이루어진 문자열이므로 0을 만나면 그 0의 뒤에 1을 만나면 그 1의 앞에 위치시켜 주면 해결될 일이었다. 문제는 111100 이런 문자열의 경우 11 [ 110 ] 0 이렇게 추출 후.. 2021. 6. 16. [ Baekjoon 백준 ] # 7569 번 Python 풀이 // 문제 요약 토마토를 3차원 격자에 배치한다. 익은 것, 안 익은 것, 빈 칸 이렇게 세 종류의 칸이 존재한다. 익은 토마토의 대각선 방향을 제외한 이웃한 칸에 안 익은 토마토가 있을 경우 하루가 지나면 익은 토마토로 바뀐다고 할때 토마토가 다 익는데 걸리는 최소 일자를 구해라 단 모든 토마토가 익을 수 없다면 -1을 처음부터 모두 익어있다면 0을 출력해라. // 사고 3차원에 덜컥 겁을 먹었는데 알고보니 원래 2차원 문제였던걸 확장한 문제여서 2차원 문제 풀었던 사람들은 쉽게 접근을 했던 문제였다. 역시 코테는 문제를 얼마나 풀어보느냐가 절반은 먹고 들어간다. 아무튼 시간이 많이 걸리겠다 생각이 들어서 백트래킹을 생각할 수 있는데 백트래킹은 DFS 이므로 하루에 이웃한 한 칸만 전염시키는 조건에 맞.. 2021. 6. 14. [ 프로그래머스 ] 셔틀버스 파이썬python 풀이 // 문제 요약 하루에 n번 t분 간격으로 오는 버스가 m 명을 태울 수 있다. 버스를 타는 사람들이 언제 줄을 서는지 알고 있을때 버스를 가장 늦게 탈 수 있는 시각을 구해라. // 문제 풀이 이 문제는 악랄한(?) 마음을 가지고 풀면 잘 풀린다. 잠을 줄이기는 싫으나 얌체가 되어서 한 놈을 탈락시키더라도 내가 꼭 타고 만다 이런 마인드 셋으로 접근해야 모든 경우의 수를 발견할 수 있다... 실재로 함수의 리턴부분을 생각할때 주요한 알고리즘을 설계하는 것 보다 더 섬세하게 조건을 찾아야하는 문제였다. 코드는 아래와 같다. source code github : https://url.kr/jblkau hyun06000/coding_test_study_with_python It is a coding test.. 2021. 6. 4. [ 프로그래머스 ] 정수 삼각형 파이썬python 풀이 //문제 요약 정수로 된 삼각형이 주어지면 아래로 이웃한 두 정수와 만 더해질 수 있다고 할때 가장 큰 합은 얼마인지 구하여라 //풀이 나는 이거 처음에 무조건 dfs 라고 생각했다. 그리고 완전 틀려먹고나서 그냥 그리디로 풀면 되는 문제라는걸 깨달았다. 코테를 준비하면서 점점 더 많이 느껴지는 것은 이 문제는 그리디다! DFS다! DP다! 이런게 처음에 배울땐 의미가 있지만 나중에 문제를 마주하면 크게 의미가 없다. 솔직히 그래프로 풀어서 정말 효율적인 문재들은 굉장히 소수의 문제이고 대부분의 경우에서 그리디 / 동적프로그래밍 으로 풀게 되는데 이것도 구분이 점점 모호하고.. 그냥 자신만의 어떤 스타일이 굳어지면 더 이상 구분하는 것도 의미가 없어진다. 다른 사람들과 소통하고 공식적인 자리에서 꼭 써야.. 2021. 6. 4. [ 프로그래머스 ] 야근 지수 파이썬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 다음 반응형