컬쥐네 다락방

이제 알고리즘 공부 2주차도 끝이다.. 생각보다 공부한 시간에 비해 내가 배운건 별로 없는 느낌이라 속상하다 .. 이번주에 공부한 개념들에서 기억에 남는 개념은 분할 정복과 백트래킹 그리고 최단 경로다 . 분할 정복 분할 정복은 답을 구하는 과정에서 쪼개고 쪼개서 작은 픽셀에서 계산이 되도록 하는 문제였다 . DSF와 BFS를 공부할 때 풀었던 토마토 문제와 비슷한 느낌으로 시작점을 기준으로 쭉 검사를 진행하지만 조건이 더 추가되고 구간을 나눠서 문제를 푼다는 점이 달랐다. www.acmicpc.net/problem/2630 2630번: 색종이 만들기 첫째 줄에는 전체 종이의 한 변의 길이 N이 주어져 있다. N은 2, 4, 8, 16, 32, 64, 128 중 하나이다. 색종이의 각 가로줄의 정사각형칸..

- 동적 계획법 - 그리디 알고리즘 - 정수론 및 조합론 - 스택 동적 계획법 (Dynamic Programming) 최근에는 동적 계획법 (Dynamic Programming)에 빠져있었다. 전체 문제를 작은 문제로 나눠서 단순화 시키는 동적 계획법에서 여러번 수행될 수 있는 작은 문제들의 값을 메모이제이션을 통해 불러오면서 전체적인 시간 복잡도를 낮추고 효율적으로 만들어준다. 이때 메모이제이션 (Memoization)이라는 개념은 함수가 작동하면서 구해진 값들을 저장소에 넣어놓고 같은 함수를 작동시키면 그 값을 불러와 대체해주는 역할을 해주는 개념. 지난주에 예제를 풀며 익힌 개념을 이번주에 더 많은 문제를 풀어보면서 응용해봤다. www.acmicpc.net/problem/1149 1149번: RGB..

2021.03.10 배운 지식 -DFS (깊이 우선 탐색) -BFS (너비 우선 탐색) 어제 저녁부터 계속 붙잡고 있었던 DFS, BFS ! 9일 밤 늦게까지 꼭 한 문제를 완성시키고 자겠다는 마음으로 시도했지만 자기 전까지 완성하지 못했다.. 🤬 그런데 다음날 아침에 처음부터 다시 코딩했더니 한번에 완성됐다!! (왜.. ????!!) DFS 와 BFS는 한 노드를 시작으로 인접한 다른 노드로 재귀적 탐색을 거치는 방법을 말하는데, 대표적인 예시로 알파고가 있다. 알파고는 대국을 진행하면서 발생하는 모든 수를 계산하고 최적의 수를 찾아내기 때문! DFS는 한 방향으로 끝까지 파고들고 끝을 확인한 후에 가지 않은 길로 다시 가는 순서로 탐색을 진행. BFS는 갈라진 모든 경우의 수를 탐색하며 거미줄처럼 퍼..

2021.03.09에 배운 지식 -스택 -큐 스택은 한쪽 끝만 열려있는 자료 구조인데, 빨래바구니처럼 내가 차곡차곡 저장해놓고 마지막에 들어갔던 녀석부터 하나씩 빼서 쓸 수 있는 저장소다. 스택을 이용할 땐 주료 stack.append()를 이용해 스택의 맨 마지막에 push를 해주거나 stack.pop()을 이용해 마지막 녀석을 빼주는 식으로 이용한다. 내가 이해한 스택을 사용해보기 위해 백준 알고리즘 예제중 4949번과 1874번을 풀어봤다. https://www.acmicpc.net/problem/4949 4949번: 균형잡힌 세상 하나 또는 여러줄에 걸쳐서 문자열이 주어진다. 각 문자열은 영문 알파벳, 공백, 소괄호("( )") 대괄호("[ ]")등으로 이루어져 있으며, 길이는 100글자보다 작거..