반응형 프로그래머스7 [ 프로그래머스 ] LV.2 짝지어 제거하기 // 문제요약 문자열 s 가 주어지면 짝이 맞는 문자 한 쌍을 제거하고 앞뒤로 남은 문자들을 다시 붙이는 작업을 반복할때 모든 문자를 없앨 수 있다면 1 그렇지 않다면 0을 반환하는 함수를 완성해라. // 사고 특정한 페턴을 추출/제거하는 방식중에서 stack의 선입후출 LIFO의 특성을 이용하는 전형적인 문제다. 보여지는 대로... 선입선출은 먼저 들어간 것이 먼저 나오는 것이고 선입후출은 먼저 들어간 것이 나중에 나오는 것이다. 편의점 알바를 해보면 저 둘의 차이를 확실히 알것이다. 사장님은 선입선출로 정리하라고 하고 손님들은 선입후출로 사가려고 한다... 아무튼 문제를 많이 풀어보면 어느 순간 자동으로 스택이라는 것을 직감하게 되는 전형적인 문제다. 페턴을 외워두는 것도 나쁘지 않다. // 풀이 원.. 2021. 7. 22. [ 프로그래머스 ] 110 옮기기 파이썬python 풀이 // 문제요약 0과 1로 이루어진 문자열이 하나 이상 주어지면 각 문자열의 부분 문자열 중 110에 해당하는 부분을 추출하여 위치를 바꾸는 과정을 거친다고 할때 사전 순서에서 가장 앞서는 문자열들을 찾아 반환하여라 // 사고 '사전순서'라하면 dfs가 번뜩 떠올랐지만 주어지는 문자열의 길이가 어마어마해서 다른 방식으로 접근해야한다고 생각했다. 만약 다른 문제에서 '사전순서'를 미리 만나지 못했다면 문제를 이해 하는데만 엄청 오래 걸렸을 것이다. 그래도 조금씩 성장하는 모양이다. 110 의 경우는 이미 사전순서로 배열이 잘 이루어진 문자열이므로 0을 만나면 그 0의 뒤에 1을 만나면 그 1의 앞에 위치시켜 주면 해결될 일이었다. 문제는 111100 이런 문자열의 경우 11 [ 110 ] 0 이렇게 추출 후.. 2021. 6. 16. [ 프로그래머스 ] N-Queen 파이썬python 풀이 // 문제 요약 자연수 n 이 주어질때 n x n 의 채스판에서 n개의 퀸이 서로를 공격할 수 없도록 위치시킬 수 있는 경우의 수를 모두 구해라. // 풀이 dfs 중에서도 백트래킹 문제다. 사실은 "모든 경우의 수" 문제이므로 브루트 포스이긴 한데 이후의 사건이 이전의 사건에 종속적이므로 조건문을 통해 가지를 치는 것이 가능하다. 이런 문제가 가장 어려운 부분은 여러 겹의 for문으로 브루트 포스로 설계할 것인가? 수학적 접근으로 n에 대한 규칙을 찾을 것인가? 재귀 함수를 통해 백트래킹을 할 것인가? 이 선택을 순간적으로 하기 어렵다는 것이다. n이 작으니 브루트 포스도 그럴싸해 보이고 그림을 그려보면 묘하게 페턴도 있어 보이며 백트래킹을 잘 쓰면 굉장히 섹시한 답을 제출할 수도 있어 보인다. 이럴 .. 2021. 6. 7. [ 프로그래머스 ] 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. 이전 1 2 다음 반응형
