Manduss life

[문제] [느낀점 / 깨달은점] Backtracking 문제이다. 방문체크 배열을 재귀함수의 내부 재귀함수로 들어갈 때마다 deep copy를 해주었는데, 이렇게 하면 Time Limit ! deep copy보다는 하나의 방문체크 배열을 사용하고, 내부 재귀함수 후 False(방문하지 않음)로 돌려주는 방법. feat. binue [코드] class Solution: result = False def exist(self, board: List[List[str]], word: str) -> bool: def print_2d( a): for i in a : for j in i: print(j, end=' ') print() def back_tracking(i, j, num, is_used): if num =..

ㅇ

[느낀점] 정답값을 바로 도출하는 방향으로 접근을 했기 때문에 못 풀었다. 세트 개수(정답)가 나올 수 있는 수의 범위 0~2*10 ^ 12 값까지 가능한지 여부를 따지며 search하는 문제이다. 이를 10^12까지 search 하면 시간복잡도가 넘어가기 때문에 O(log(n))인 binarysearch로 접근해야한다. 그리고 그 수(x)만큼 테스트 세트를 만들 수 있는의 여부를 판단하는 알고리즘이 중요하다. 0부터 N 까지 반복하며, curr 이라는 변수와 x와 비교한다. curr 변수는 이전값이 x보다 부족하다면, 그만큼 d값에서 채운 후의 남은 값과 c값과의 합이라고 보면 된다. 크 이런 알고리즘 막상 알면 쉬운데, 모른 채로 접근하려고 하면 어려운 것 같다. 그리고 Binary Search할 때..

[문제] [느낀점] 백준 제출할 때 처음엔 6%에서 recursion error 발생 setrecursionlimit을 10**6으로 설정 6%에서 메모리 초과 발생 setrecursionlimit을 10**4으로 설정 해결 62%? 에서 시간 초과 발생 "빙산이 전부 녹을 때까지 두덩어리로 나눠지지 않을 때 0을 출력" 처리를 못해줬음 --> 세번째 풀때도 ㅋㅋㅋ 처리하니 성공 !! 문제에서 말하는 사소한 것까지 다 챙기자 !! 23/01/26 다시 풀어보니 python3로 하면 시간 초과, pypy로 풀 경우, 성공.. --> 세번째도 동일 23/10/07 다시 풀어보니, visit matrix를 global로 선언해줘야 갔던 위치에서 다시 bfs 안도는데, bfs 함수 내에서만 선언해서 시간초과. ..

[문제] [느낀점] 우와 이걸 풀었다! 그런데 2시간 56분이 걸렸네 ? 최대값 찾는 방법은 Backtracking 방법을 사용하였다. 말 움직이는 함수에도 recursion을 활용하였다. [코드] import copy # import sys # sys.stdin = open("input.txt", "r") # T = int(input()) pan = [[2, 4, 6, 8], [10, 13, 16, 19], [10, 12, 14, 16, 18], [20, 22, 24], [20, 22, 24, 26, 28], [30, 28, 27, 26], [25, 30, 35], [30, 32, 34, 36, 38], [40]] def move_horse(start, num): if start[0] ==0 : ret..

[문제] [느낀 점] 내리는 곳에 가는 즉시 로봇을 내려야 한다. 여기서 시간을 많이 썼네 ^^ 어이없다~ [코드] # import sys from collections import deque # # sys.stdin = open("input.txt", "r") # T = int(input()) def rotate(): q2.append(q1.pop()) q1.appendleft(q2.popleft()) robots.pop() robots.appendleft(0) if robots[-1] == 1 : robots[-1] = 0 def move_robots(): for i in range(N-2, 0, -1): if robots[i] == 1 and robots[i+1] == 0 and q1[i+1] >=..

[느낀 점] 같은 거리인 승객이 여러명일 경우의 해결책으로 BFS 탐색시 위, 왼, 오, 아 순으로 탐색하는 것으로 풀면 안됨 ! 반례 : 왼왼왼 < 오오위 도착지에 승객이 있는 경우까지 확인해야 함 이때, 승객을 태운 후, 승객의 유무 행렬의 초기화를 못해줘서 시간이 오래 걸렸음 [코드] # import sys # # sys.stdin = open("input.txt", "r") # T = int(input()) import copy import sys def print_2d(a): for i in a: for j in i: print(j, end=' ') print() def find_min_person(y, x): from collections import deque global taxi_j, ta..

[문제] 출처 : https://programmers.co.kr/learn/courses/30/lessons/42579 스트리밍 사이트에서 장르 별로 가장 많이 재생된 노래를 두 개씩 모아 베스트 앨범을 출시하려 합니다. 노래는 고유 번호로 구분하며, 노래를 수록하는 기준은 다음과 같습니다. 속한 노래가 많이 재생된 장르를 먼저 수록합니다. 장르 내에서 많이 재생된 노래를 먼저 수록합니다. 장르 내에서 재생 횟수가 같은 노래 중에서는 고유 번호가 낮은 노래를 먼저 수록합니다. 노래의 장르를 나타내는 문자열 배열 genres와 노래별 재생 횟수를 나타내는 정수 배열 plays가 주어질 때, 베스트 앨범에 들어갈 노래의 고유 번호를 순서대로 return 하도록 solution 함수를 완성하세요. 제한사항 g..