Algorithm272 [ 파이썬(python) ] 백준 11659 - 구간 합 구하기4 📍 백준 11659 - 구간 합 구하기 4 백준 11659 - 구간 합 구하기4 ⚡️ 나의 풀이 이 문제를 그냥 구현한다면 시간 초과에서 벗어나지 못할 것이다. 바로 시간 복잡도가 높기 때문인데, 이럴 때 시간 복잡도를 낮출 적절한 알고리즘이 바로 prefix_sum이다. prefix_sum의 난이도는 어렵지 않다. 서두에서 말했듯이 이 문제를 prefix_sum을 사용하지 않고 구현할 때 M, N의 입력 범위가 100,000이 넘어간다면 시간 복잡도는 O(MN)이 되므로 1초 내에 구현할 수가 없다. 알고리즘을 설계할 때마다 고려해야 하는 점은 여러 번 사용될 만한 정보는 미리 구해서 저장해 놓을수록 유리하다. 구현 방법은 간단한데, 각각의 합들을 새로운 배열에 저장해뒀다가 나중에 입력에 구간이 들어오.. 2021. 4. 23. [ 파이썬(python) ] 이것이 코딩 테스트다 - 구간 합 계산(Prefix_sum) 📍 백준 11659 - 구간 합 구하기 4 백준 11659 - 구간 합 구하기4 ⚡️ 나의 풀이 이 문제를 그냥 구현한다면 시간 초과에서 벗어나지 못할 것이다. 바로 시간 복잡도가 높기 때문인데, 이럴 때 시간 복잡도를 낮출 적절한 알고리즘이 바로 prefix_sum이다. prefix_sum의 난이도는 어렵지 않다. 서두에서 말했듯이 이 문제를 prefix_sum을 사용하지 않고 구현할 때 N, M의 입력 범위가 100,000이 넘어간다면 시간 복잡도는 O(NM)이 되므로 1초 내에 구현할 수가 없다. 알고리즘을 설계할 때마다 고려해야 하는 점은 여러 번 사용될 만한 정보는 미리 구해서 저장해 놓을수록 유리하다. 구현 방법은 간단한데, 각각의 합들을 새로운 배열에 저장해뒀다가 나중에 입력에 구간이 들어오.. 2021. 4. 23. [ 파이썬(python) ] 이것이 코딩 테스트다 - 개미전사(DP) 📍 이것이 코딩 테스트다 DP - 개미 전사 유튜브 - 동빈나(27:48) ⚡️ 나의 풀이 3개월 전에 풀었던 문제이지만, 어떻게 풀었는지 기억이 잘 안 나서 다시 풀어봤다. 문제를 풀어보면 알겠지만 boj_2579 - 계단 오르기와 비슷한 유형이다. 입력 부분에서 맨 앞에 0을 주고 싶었는데 그렇게 되면 입력받는 부분이 까다로워질 수 있어 처음부터 입력값을 주었다. 그러면 출력으로 n-1을 줘야 된다는 점을 잊지 말자! 풀이 영상을 보면서 동빈 나가 DP를 써야 하는 경우를 알려주셨는데 기억해야 하는 내용이다. 최적 부분: 특정 i번째까지 최적의 해를 구할 때 이전 값을 사용한다. 여기에서 제일 중요한 포인트는 개미가 식량창고를 털 때 두 가지의 케이스가 있다. 관점을 달리해서 뒤에서부터 살펴보자. 제.. 2021. 4. 23. [ 파이썬(python) ] 백준 4179 - 불! (BFS) 📌 백준 4179 - 불! 문제 설명 💡 나의 풀이 나에겐 끔찍한 문제였다.. 이 문제에 오전, 오후를 완전히 쏟아버렸다. 😇 😇 수 없이 코드를 제출했다. 하지만, 돌아오는 대답은 인덱스 에러 혹은 틀렸습니다. 채점 중간에 71%에서 자꾸 오답 판정을 받았다. 틀린 이유를 단계별로 작성하면 인덱스 에러(Index Error): 변수 정의 단계에서 행과 열을 반대로 입력했다. 잘못된 변수 입력: 네이밍을 비슷하게 해서 그런지 중간에 다른 변수를 작성해서 제출했다. 잘못된 코드: 여기서 시간이 제일많이 걸렸는데 마지막 단계인 f_visited > j_visited 조건을 잘못 추가했다. 처음에는 f_visited[nx][ny] > j_visited[nx][ny]로 생각했는데 아니었다. 왜 그런가 하면 우리.. 2021. 4. 22. [ 파이썬(python) ] 백준 1743 - 음식물피하기 (BFS) 📌 백준 1743 - 음식물 피하기 문제 설명 💡 나의 풀이 전형적인 BFS 혹은 DFS 문제이고, 입력에 음식물의 좌표를 입력받아 BFS, DFS를 돌려 단순 개수를 파악하고 기존 개수와 현재 개수를 비교하여 더 큰 값으로 갱신해주면 되는 방향으로 문제를 풀면 된다. 여기서 약간 까다로운 부분은 좌표를 직접 입력받는 부분일 텐데, 우리가 사용하는 graph는 0부터 시작하므로 입력을 받을 때 -1처리를 해주면 오류없이 그래프에 입력할 수 있다. 풀이 흐름을 직접 그려봤다. import sys from collections import deque input = sys.stdin.readline def bfs(x, y): cnt = 0 queue = deque() queue.append((x, y)) vi.. 2021. 4. 22. 이전 1 ··· 40 41 42 43 44 45 46 ··· 55 다음
