지난 알고리즘 3주 차를 마치고 이번엔 4주 차와 5월을 동시에 맞이했다. 알고리즘 3주차에서는 그래프 탐색과 DFS, BFS에 대해서 다양한 문제들을 풀어보기도 했고 백준 그룹을 통해 연습 셋을 풀어보는 모의 테스트를 진행하면서 시간이 제한되어 있는 환경을 경험해 볼 수 있었다. DFS와 BFS를 풀면서 느낀점은 실버문제는 전형적인 DFS, BFS방식으로 풀 수 있는 것 같다. 하지만 골드이상이 되는 순간 추가 조건이 하나씩 더 붙고 보통 그 추가조건은 배열을 떨어트려놓고 카운트를 한다던가 한 번씩만 진행을 시키고 카운트를 하는 종류들이 있는 것 같다. 나중에 풀이할 때에도 까먹지 않게 종종 연습해야겠다. 이번 4주차에는 다이나믹 프로그래밍(DP)과 그리디 알고리즘을 공부하고 있는데 DP부분이 생각보다..

💡그리디 알고리즘이란? 그리디 알고리즘은 현재 상황에서 지금 당장 좋은 것만 고르는 방법을 의미합니다. 일반적인 그리디 알고리즘은 문제를 풀기 위한 최소한의 아이디어를 떠올릴 수 있는 능력을 요구합니다. 그리디 해법은 단순히 가장 좋아 보이는 것을 반복적으로 선택해도 최적의 해를 구할 수 있는지를 검토합니다. 그리디 알고리즘 예시 문제 - 문제 : 카운터에는 거스름돈으로 사용할 500원, 100원, 50원, 10원짜리 동전이 무한히 존재한다고 가정합니다. 손님에게 거슬러 주어야 할 돈이 N원일 때 거슬러 주어야 할 동전의 최소 개수를 구하세요. 단, 거슬러 줘야 할 돈 N은 항상 10의 배수입니다. - 입력 : N = 1260 - 풀이 : 가장 큰 화폐 단위부터 돈을 거슬러 주는 식으로 풀이합니다. 먼저..

💡다이나믹 프로그래밍(DP)란? - 다이나믹 프로그래밍은 메모리를 적절히 사용하여 수행 시간 효율성을 비약적으로 향상하는 방법입니다. - 이미 계산된 결과는 별도의 메모리 영역에 저장하여 다시 계산하지 않도록 합니다. - 다이나믹 프로그맹의 구현은 일반적으로 두 가지 방식(Top Down, Bottom Up)으로 구성됩니다. 다이나믹 프로그래밍의 조건 1. 최적 부분 구조 (Optimal Substructure) 큰 문제를 작은 문제로 나눌 수 있으며 작은 문제의 답을 모아서 큰 문제를 해결할 수 있습니다. 2. 중복되는 부분 문제 (Overlapping Subproblem) 동일한 작은 문제를 반복적으로 해결해야 합니다. 다이나믹 프로그래밍 예시 - 피보나치 수열 n번째 피보나치 수를 f(n)라고 할 ..

이 문제는 기본적은 bfs문제에서 살짝 꼬아서 낸 문제입니다. 저는 처음 문제를 읽고 풀 때 N*N 배열을 N*K 배열로 글을 잘 못 읽고 풀어서 indexerror가 많이 발생했었는데 다시 제대로 읽어보니 N*N배열이고 K는 바이러스의 종류라는 것을 깨달았습니다.. bfs,dfs 문제를 풀 때에는 각 행,열의 변수와 문제에서 주어지는 조건 변수들을 잘 정리하고 문제를 풀기 시작하면 도움이 될 것 같습니다. #N,K의 입력을 받음 N,K = map(int,s.readline().split()) #각 행을 graph 이중배열에 저장 graph=[list(map(int,s.readline().split()))for _ in range(N)] # S,X,Y의 값 입력 받음 S,X,Y = map(int,s.re..

위상 정렬💡 - 위상 정렬(Topological sort)는 비순환 방향 그래프에서 정점을 선형으로 정렬하는 것입니다. - 모든 간선(u,v)에 대해 정점 u가 정점v보다 먼저 오는 순서로 정렬이 됩니다. 비순환 방향 그래프(DAG) - 비순환 방향 그래프는 사이클이 없는 방향 그래프입니다. - 왼쪽 그림과 오른쪽 그림의 차이는 정점2에서의 간선차이입니다. 정점끼리 사이클이 생기면 비순환 방향 그래프가 아니게 됩니다. 위상 정렬 동작 과정 진입차수(in_degree)가 0인 노드를 큐에 넣는다. 큐가 빌 때까지 다음의 과정을 반복한다. 1) 큐에서 원소를 꺼내 해당 노드에서 나가는 간선을 그래프에서 제거 2) 새롭게 진입차수가 0이 된 노드를 큐에 삽입 1) 모든 정점의 in_degree를 표시합니다...

이번 주차는 알고리즘 3주 차로 범위는 그래프 탐색, BFS, DFS, 위상 정렬 등을 배우고 있다. BFS, DFS는 1주 차 때 잠깐 경험해 봤는데 2주 차 때 안 썼다가 다시 쓰려고 하니 정확한 풀이가 기억이 나지 않았다.. 아직 한 번씩 배우고 있는 중이라 새로운 지식이 들어왔을 때 기존에 배웠던 내용들을 까먹지 않아야 하는데 배운 내용들을 복습하면서 상기하는 시간을 가져야겠다. 이번 주차 처음에는 BFS와 DFS 가 이해가 안 돼서 헤맸었는데 마음을 가라앉히고 기초 강의를 보고 개념의 틀을 익히고 나서 푸니까 이해가 가기 시작했다. 매 주차 느끼는 거지만 새로운 알고리즘을 처음보고나서 익히는 기간까지 많은 반복과 정확히 이해하고 넘어가는 게 중요하다고 느낀다. 앞으로 더 많은 내용들을 배우면서 ..

위의 문제는 bfs를 활용해서 고슴도치가 비버의 집을 찾아가는 시간을 출력하는 문제입니다. 이 문제를 풀 때 고슴도치를 먼저 이동할지 물을 이동할지 고민을 하다가 저는 고슴도치를 먼저 이동하고 물을 이동하는 방식으로 풀어봤습니다. 이렇게 하면 물이 다음에 이동할 거리를 생각안해도되므로 고슴도치의 조건이 하나 줄어듭니다. R,C = map(int,s.readline().split()) graph = [list(map(str,s.readline().strip())) for _ in range(R)] v = [[0]*C for _ in range(R)] q = deque() 우선 진행에 필요한 데이터들을 미리 생성해두고 bfs함수와 조건들을 생성합니다. #비버 집 위치 저장 for i in range(R): ..

위의 문제는 최소 비용을 구하는 문제로 다익스트라 알고리즘을 활용해서 푸는 대표적인 문제입니다. 먼저 다익스트라 알고리즘의 동작 과정을 간단하게 소개하면 다음과 같습니다. 출발 노드와, 도착 노드를 설정 알고 있는 모든 거리 값을 부여 (모를 경우 무한(아주 큰 값)으로 설정) 출발 노드부터 시작하여, 방문하지 않은 인접 노드를 방문, 거리르 계산한 다음, 현재 알고있는 거리보다 짧으면 해당 값으로 갱신한다. 현재 노드에 인접한 모든 미방문 노드까지의 거리를 계산했다면, 현재 노드는 방문한 것이므로, 미방문 집합에서 제거한다. 도착 노드가 미방문 노드 집합에서 벗어나면, 알고리즘을 종료한다. 우선 순위 큐를 사용하여 지금까지 발견된 가장 짧은 거리의 노드에 대해서 먼저 계산할 수 있으며, 더 긴 거리고 ..