반응형 파이썬14 [ 백준 ] 10451 번 순열 사이클 파이썬python 풀이 // 문제 요약 1부터 N 까지 정수로 만들 수 있는 순열의 한 가지 경우가 주어질 경우 1부터 N 까지 오름차순으로 정렬한 순열과 1대 1 대응 하여 만들 수 있는 그래프에서 순환 구조는 몇개가 생기는지 리턴하는 함수를 만들어라. //사고 문제를 이해하는게 어려운 문제다. 문제의 참고자료를 보면 그림이 아주 잘 나와있는데 이런 행렬이 주어지면 첫번째 행이 from 두번째 행이 to 가 되는 그래프를 그릴 수 있다. 그려본다면 이런식이다. 모두 같은 숫자로 이루어진 순열이므로 뻗어나가고 끝나는 가지는 존재하지 않게 되고 순환구조가 발생하게 된다. 파이썬에서는 dfs를 이용하면 순환구조를 간단하게 찾을 수 있는 테크닉이 존재하는데 바로 파이썬의 set() 를 이용한 진행경로 추적이다. dfs의 경우 깊이를.. 2021. 7. 29. [ 프로그래머스 ] LV.2 짝지어 제거하기 // 문제요약 문자열 s 가 주어지면 짝이 맞는 문자 한 쌍을 제거하고 앞뒤로 남은 문자들을 다시 붙이는 작업을 반복할때 모든 문자를 없앨 수 있다면 1 그렇지 않다면 0을 반환하는 함수를 완성해라. // 사고 특정한 페턴을 추출/제거하는 방식중에서 stack의 선입후출 LIFO의 특성을 이용하는 전형적인 문제다. 보여지는 대로... 선입선출은 먼저 들어간 것이 먼저 나오는 것이고 선입후출은 먼저 들어간 것이 나중에 나오는 것이다. 편의점 알바를 해보면 저 둘의 차이를 확실히 알것이다. 사장님은 선입선출로 정리하라고 하고 손님들은 선입후출로 사가려고 한다... 아무튼 문제를 많이 풀어보면 어느 순간 자동으로 스택이라는 것을 직감하게 되는 전형적인 문제다. 페턴을 외워두는 것도 나쁘지 않다. // 풀이 원.. 2021. 7. 22. [ 프로그래머스 ] N-Queen 파이썬python 풀이 // 문제 요약 자연수 n 이 주어질때 n x n 의 채스판에서 n개의 퀸이 서로를 공격할 수 없도록 위치시킬 수 있는 경우의 수를 모두 구해라. // 풀이 dfs 중에서도 백트래킹 문제다. 사실은 "모든 경우의 수" 문제이므로 브루트 포스이긴 한데 이후의 사건이 이전의 사건에 종속적이므로 조건문을 통해 가지를 치는 것이 가능하다. 이런 문제가 가장 어려운 부분은 여러 겹의 for문으로 브루트 포스로 설계할 것인가? 수학적 접근으로 n에 대한 규칙을 찾을 것인가? 재귀 함수를 통해 백트래킹을 할 것인가? 이 선택을 순간적으로 하기 어렵다는 것이다. n이 작으니 브루트 포스도 그럴싸해 보이고 그림을 그려보면 묘하게 페턴도 있어 보이며 백트래킹을 잘 쓰면 굉장히 섹시한 답을 제출할 수도 있어 보인다. 이럴 .. 2021. 6. 7. [ 프로그래머스 ] 셔틀버스 파이썬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. [ 프로그래머스 ] 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. 이전 1 2 3 다음 반응형
