Leta Learns

문제 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이어도 긴장하면서 풀었는데...

문제 https://www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어 www.acmicpc.net 학기 중 알고리즘 수업 들을 때 그래프 과제에서 절망했던 경험이 있다.. ㅎ 그래프는 조금하면 익숙해진다고 하는데 난 아직 아니라서 천천히 많이 풀어보려고 한다. 이번 문제는 어렵진 않았는데 count 세는 부분을 dfs 함수 내부에 넣지 않는 게 중요한 것 같다. dfs 함수 내부에 넣었더니 지 멋대로 먼저 print돼서 애 좀 먹었다 :( import sys def dfs(v): visited..

문제 https://www.acmicpc.net/problem/2616 2616번: 소형기관차 첫째 줄에 기관차가 끌고 가던 객차의 수가 입력된다. 그 수는 50,000 이하이다. 둘째 줄에는 기관차가 끌고 가던 객차에 타고 있는 손님의 수가 1번 객차부터 차례로 입력된다. 한 객차에 타고 있 www.acmicpc.net 문제 알고리즘 분류에 '누적합'이라고 나와있는데 누적합으로 안 푼 바보가 여기 있다.. 최대로 끌 수 있는 객차 수를 하나하나 계산해서 단순합으로 넣으려고 하니까 코드도 복잡해지고 안 풀린 거였다. 2021.07.10 - [HUFS/HUFS 모각코 캠프] - [모각코] 210710 Today I Learned (단순합으로 시도한 코드) 단순합으로 하면 예제는 풀리긴 하는데 최대로 끌 수..

문제 https://www.acmicpc.net/problem/18234 18234번: 당근 훔쳐 먹기 첫 번째 줄에 N(1 ≤ N ≤ 200,000)과 T(N ≤ T ≤ 100,000,000)가 공백으로 구분되어 주어진다. 오리는 당근의 맛을 충분히 높이기 위해 항상 N이상인 T일 동안 재배한다. 다음 N개의 줄에 걸쳐서 i+1번째 www.acmicpc.net 예제는 잘 돌아가는데 시간초과가 나서 며칠동안 고군분투했던 문제.. 그냥 문제가 귀여워서 재밌어 보이길래 시도한 건데 푼 사람도 많이 없어서 구글링해도 시간초과 해결하는 법을 찾을 수 없었다.. 같이 스터디하는 친구도 시간초과 났었는데 해결한 후 본인 알고리즘 설명해준 거 듣고 나도 비슷한 방식으로 접근해봤다. 우선, 당근 맛의 최댓값을 가지려면..

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

문제 https://www.acmicpc.net/problem/11047 11047번: 동전 0 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수) www.acmicpc.net 회의실 배정 문제를 제외하면 그리디는 처음 풀어본 것 같다. 정해진 틀이 있는 게 아니라 알고리즘 생각하고 구현하는 느낌이라서 풀면서 내가 지금 그리디로 잘 풀고 있는 게 맞나? 의문이 들었다. 가장 큰 동전부터 사용하기 위해서 입력받은 동전의 가치들을 역순으로 정렬한 후 for문을 사용하여 가능한 동전 수를 구하였다. 어쨌든 ..

문제 https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 냅색 분명히 학교 수업 때 배웠는데 .. 강의 자료 안 보고 하려니까.... 머리에 쥐날 뻔 했다... 어떤 식으로 풀어야 할 지 감이 안 잡혀서 DP테이블 직접 그렸다. 앞으로 DP 문제 풀 때는 테이블 구상하는 방법을 생각해서 접근해야지. else 부분 max 비교 대상을 찾는 게 관건이었고 그것만 하면 어렵지 않았다. n..

문제 https://www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 학교 수업에서 DP 배울 때 LCS 배웠어서 겁먹지 않고 풀 수 있었다. 수업 때 교수님이 코드까지 주신 줄 알았는데 찾아보니 코드 없이 이론만 있었어서 직접 코드 짜는데 시간이 좀 걸리긴 했다. 처음엔 아무 생각 없이 교수님이 주신 pseudo-code 보고 그냥 짜다가 DP 문제라는 걸 깨닫고 바로 노선 변경ㅋㅋ 자꾸 인덱스 에러가 나서 애 좀..