Leta Learns

문제 https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 모각코에서도 얘기했듯이 이번 문제는 m, n을 구별하는 게 어려웠다.. 선형대수학 공부해야되나봐... row, col 왜 이리 헷갈리지.. 어제 스터디 할 때 관련 얘기 해서 row랑 col에 대해서 10분 동안 토의했는데 꼭 잘 기억해야지.. 이 문제는 모각코 Today I Learned에서 이미 리뷰를 했기 때문에 조금만 더 덧대려고 한다. 2021.07.22 - [HUF..

https://www.acmicpc.net/problem/7576 요새 dfs, bfs를 공부 중이었는데 익숙치 않아서 한 문제 푸는데 2-3일 걸리고 그랬다. 이 문제도 일요일에 처음 풀었는데 못 풀어서 모각코 때 다시 풀어야지. 하고 다른 공부했다. bfs는 그냥도 어려운데 이번 문제는 다른 문제들과 달리 n, m 으로 입력받는 게 아니라 m, n으로 입력 받아서 헷갈렸다. 그거 뭐 얼마나 바뀌었다고 헷갈리냐고 하면.. 할 말이 없다. 저는 코딩 바보예요. 종이에 계속 쓰면서 n이 row고, m이 col이다 라는 걸 계속 상기시켜주었다. 1. 기본 틀은 다른 bfs 문제들이랑 거의 비슷했는데 이 문제에서 좀 특별한? 점은 q.popleft()하기 전에 range(len(q))로 for문을 돌려준 것이..

문제 https://www.acmicpc.net/problem/5014 5014번: 스타트링크 첫째 줄에 F, S, G, U, D가 주어진다. (1 ≤ S, G ≤ F ≤ 1000000, 0 ≤ U, D ≤ 1000000) 건물은 1층부터 시작하고, 가장 높은 층은 F층이다. www.acmicpc.net 1697번 숨바꼭질 문제랑 알고리즘이 거의 같았다. 2021.07.12 - [Coding/백준] - [Python] 백준 1697번 - 숨바꼭질 비슷한 구조의 bfs문제를 한 번 더 풀 수 있어서 bfs 이해하는데 더 도움이 됐다. count를 처음에는 그냥 변수로 만들어서 갱신해줬는데 그렇게 하다보니 갈라지는 부분이라고 해야하나... 쨌든 그런 곳에서 count가 여러 개로 나뉘어져야 하는데 변수 하나..

문제 https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 미로 탐색 학교 수업 때 과제로 풀었었는데 그래서.. 그냥 그때 푼 코드 거의 참고했다.. bfs 너무 어렵다.. 풀어놓은 코드 조금만 수정해서 풀면 되는데 인덱스 잘못 생각해서 자꾸 틀렸었다. 왜 틀린지 몰랐을 땐 풀기 싫어져서 잠시 내팽겨치고 있었다. bfs함수 if v_row == n-1 and v_col == m-1: 이 부분에서 n-1, m-1이 아니라 n, m으로 해놨어서 입력한 값 다 돌았는데 또 돌게된 것이었..

문제 https://www.acmicpc.net/problem/1697 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net bfs......... 나 bfs 진짜 싫어....... 과제할 때 결국 못 풀고 그냥 제출한 경험이 있음.... 번아웃까지 야기했던 그 문제.... bfs....... 사실 이 문제 접근하면서 bfs를 코드로 짜는 방법을 드디어 이해한 것 같다. 큐에 넣고 빼고 하면서 이걸 어떻게 한다는 건지 학기 중에는 이해하지 못했다. 그래서 실버1이어도 긴장하면서 풀었는데...

BFS (너비 우선 탐색) : 현재 정점과 인접한 정점들에 대해 우선적으로 탐색하는 방식 => 넓게(wide) 탐색. 큐(Queue)를 이용해서 구현. 방문한 정점에 대해 표시하지 않는 경우, 무한루프에 빠질 가능성 有 => 각 정점의 기 방문 여부 저장 (visited) 아래로 깊은 그래프에 대해 좋은 성능을 기대할 수 있다. ( -> 아래로 깊은 그래프에서 해가 중간에 있는 경우) BFS의 과정 BFS 시간 복잡도 (DFS와 동일) 시간 복잡도 (N: 노드 수, E: 에지 수) 인접 행렬로 표현된 그래프 => O(N^2) 인접 리스트로 표현된 그래프 => O(N+E) 희소 그래프 (Sparse Graph)의 경우, 인접리스트 사용이 유리 -> 그래프 내에 적은 숫자의 간선만을 가지는 그래프 DFS v..