본문 바로가기

분류 전체보기521

[ 파이썬(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.
[ 파이썬(python) ] 백준 1303 - 전쟁 - 전투(BFS) 📌 백준 1303 - 전쟁 - 전투 문제 설명 💡 나의 풀이 (여담이지만 1303 하니까 국방 헬프콜이 생각났다.) 2차원 배열에서 각 색깔에 맞는 거리를 구하는 전형적인 BFS문제이지만, 헷갈린 부분들이 많았다. 한쪽 BFS만 구하는것이 아니고 양쪽 BFS를 모두 구현해야하다보니까 함수를 어떻게 선언하는지 굉장히 고민을 많이 했다. 결론적으로 BFS 함수에 color라는 파라미터를 작성해서 넘겨줬고 함수내에서 각 칸의 거리를 구하는 방법은 각 색깔별로 w_cnt, b_cnt를 따로따로 선언하지 않고 cnt 변수 하나만 선언해서 색깔 별로 조건문을 다르게 주어 현재 들어온 색을 기준으로 cnt를 세고 return하는 방법으로 진행했다. 이 방법까지 캐치하는데 상당히 오랜 시간이 걸렸다. 어제 첫 알고리즘.. 2021. 4. 21.
[ 파이썬(python) ] 백준 4963 - 섬의 개수(DFS) 📌 백준 4963 - 섬의 개수 문제 설명 💡 나의 풀이 BFS 혹은 DFS만 잘 구현할 수 있다면 어려운 문제는 아니다. 다만, 기존 문제에서는 상, 하, 좌, 우 패턴이 등장했다면 이번에는 대각선 패턴이 등장했다. 이왕 등장했으니 다음 세 가지 패턴을 알아보자. 상, 하, 좌, 우 패턴 dx = [1, 0, -1, 0] dy = [0, 1, 0, -1] 대각선 + 상, 하, 좌, 우 패턴 dx = [-1, -1, -1, 0, 0, 1, 1, 1] dy = [-1, 0, 1, -1, 1, -1, 0, 1] 대각선 패턴 dx = [-1, -1, 1, 1] dy = [-1, 1, -1, 1] 2번을 사용하면 쉽게 해결 할 수 있다. 그리고 while문 종료조건은 입력이 0, 0이어야 하는데, 이는 if n.. 2021. 4. 20.

티스토리툴바