honey_pot

https://school.programmers.co.kr/learn/courses/30/lessons/12952 백트래킹 기본 문제라는데 전혀 기본같지 않은 난이도 왜 n-queen, n-queen 하는지 이해가 가는 알고리즘이다 유튜브 강의도 참고하고 그림도 그려보면서 이해했다 2차원 배열로 풀 것 같았는데 그냥 1차원 배열로 행은 인덱스로 생략하고 열만 보자고~~ 이런 풀이법이 있을 줄은... 그리고 풀었지만 시간 초과가 떠서 다른 사람들은 왜 시간 초과가 안 뜨나 찾아보느라 푼게 아니게 된 그런 문제 마지막 테케 시간초과 뜬 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 def n_queen(graph,x,n): result = 0 if x == n: ..

https://school.programmers.co.kr/learn/courses/30/lessons/12946 https://shoark7.github.io/programming/algorithm/tower-of-hanoi 위 링크에 알고리즘이 잘 설명되어 있다 첫번째 코드는 위 링크의 설명대로 작성했다 두번째 코드는 move 함수를 쓰지 않고 hanoi 함수 하나로 해결하는 코드다 hanoi 함수로만 풀이할 경우 move 함수 대신 hanoi 함수에 n==1 파라미터를 주고 answer에 이동과정을 저장하는 조건문으로 변경한다 1 2 3 4 5 6 7 8 9 10 11 12 13 14 def solution(n): answer = [] def hanoi(n,start,via,to): if n == ..

https://school.programmers.co.kr/learn/courses/30/lessons/12905 board의 0행, 0열일 경우, 해당 값이 0일 경우는 answer만 갱신한다 나머지 경우는 현재 위치의 대각선 위 [i-1][j-1], 위 [i-1][j] , 왼쪽 [i][j-1] 값을 비교하여 가장 작은 수에 +1을 한다 결론적으로 가능한 정사각형의 한 변의 길이를 board[i][j]에 저장하게 되므로 answer와 비교해서 가장 큰 값을 뽑는다 1 2 3 4 5 6 7 8 9 10 11 12 13 14 def solution(board): answer = float('-inf') row = len(board) col = len(board[0]) for i in range(row): ..

https://school.programmers.co.kr/learn/courses/30/lessons/12936 항상 찾아보고 감탄만 하는 규칙 찾는 문제다 다들 초등학교 때 문제 푸는 방법 찾기 단원 고수였나봄 k 처리하는 부분에서 k = k % factorial(n-1) 로 처리하면 시간 초과가 나지 않지만 k %= factorial(n-1)로 처리하면 효율성 테스트에서 시간 초과가 나온다 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 from math import factorial def solution(n, k): num = [i for i in range(1,n+1)] answer = [] k = k-1 while num: # k / (n-1)! 을 했을 때의 몫이 맨 ..

https://school.programmers.co.kr/learn/courses/30/lessons/68936 압축을 하는 quad 함수를 외부에 선언할 경우 answer를 global로 선언해서 quad 함수에서도 쓸 수 있게 해야하고 arr를 파라미터로 줘야한다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 def solution(arr): global answer answer = [0,0] # 0의 개수, 1의 개수 quad(arr, answer, len(arr)) return answer def quad(arr, s, n): x, y, target = s[0],s[1], arr[s[0]][s[1]] for i in range(n): for j in range..

https://school.programmers.co.kr/learn/courses/30/lessons/77885 2진법답게 2의 배수는 규칙이 있다 이진법으로 변경한 후에 맨 뒷자리를 1로 바꿔도 되고 그냥 10진수 숫자에 1을 더해도 같은 원리다 홀수인 경우 11 정도까지 직접 써보면 오른쪽에서 맨 처음 0이 나오는 위치를 1로 바꾸고 뒤의 숫자를 0으로 바꿔주면 조건에 맞는 숫자가 된다. 개인적으로 형변환을 반복하거나 형변환한 걸 다른 클래스형의 함수를 쓰려고 처리해주는 걸 안 좋아하는데 고쳐야겠다... 그렇게 하기 싫어서 삽질하다가 우주로 갈뻔함 find 함수를 쓰려다가 rfind 함수를 발견해서 역시 파이썬은 일단 함수가 있구나..를 새삼 느끼게 됨 1 2 3 4 5 6 7 8 9 10 11 1..

https://school.programmers.co.kr/learn/courses/30/lessons/92342 itertools의 combinations_with_replacement를 알게 된 문제 combinations_with_replacement는 combinations와 다르게 튜플이 AB인 경우 AA, AB, BB 처럼 요소의 반복을 허용하고 정렬된 순서로 나오기 때문에 문제가 원하는 대로 가장 작은 점수부터 채워져서 나온다 2단계 시작 때는 문제부터 이해 안 갔는데 이번엔 그래도 시도는 해봤다 다음에 다시 풀어봐야지 찾아보니 dfs로도 풀던데 n이 클때는 조합을 만들때 시간 초과가 뜰테니 dfs 방식이 유용할 것 같다 어피치와 라이언의 점수를 비교하는 부분에서 더 복잡하게 짰었는데 zip..

https://school.programmers.co.kr/learn/courses/30/lessons/12980?language=python3 짝수와 홀수의 규칙만 찾으면 풀리는 문제였다 1 2 3 4 5 6 7 8 9 def solution(n): ans = 0 while n > 0: if n %2 == 0: n /= 2 else: n -= 1 ans += 1 return ans cs 근데 문제 질문게시판에 https://school.programmers.co.kr/questions/13871 이 풀이 진짜 대단하다 어떻게 이런 생각을??? n이 1이 될때까지 2로 나누면서 안 나눠질때 1을 더하는 방식이니까 2진수로 계산해서 점프를 하는 순간 == 1 이라고 표현할 수 있음 1 2 def solut..