백준 온라인 저지, 16953번: A → B 도입 어떤 그리디 문제는 명시적인 그래프 표현이 없더라도 그래프 탐색 전략을 사용하여 해결할 수 있다. 사실 이상한 이야기는 아니다. 그래프 탐색도 반복 과정을 사용하는 다른 알고리즘과 마찬가지로, 목표를 달성하기 위해 반복 과정을 어떻게 사용할지, 다음 반복과 이번 반복에서의 상태가 어떻게 변화해야하...

백준 온라인 저지, 14940번: 쉬운 최단거리 도입 쉬운 최단거리 문제는 전형적인 형태의 격자 그래프에서의 BFS/DFS 문제이다. 그래프 탐색이 익숙하다면 쉽게 구현 가능하지만, 충분히 경험하지 못했다면 상태 전이 방법을 고민해야할 수도 있다. *사실 모든 그래프 탐색 문제는 그래프를 탐색하면서 상태를 함께 전이해야 하므로 이 문제의 특징은 ...

도입 LDPC(low-density parity-check) 코드는 반복적 디코딩(iterative decoding)으로 섀넌 한계에 가까운 성능을 달성했다. LDPC 코드를 디코딩하는데에는 여러 알고리즘을 사용할 수 있다. 대표적으로 SP(sum-product; 합-곱, 혹은 BP; belif-propagation) 알고리즘이 최적의 성능을 보이...

도입 동적 계획법(DP; Dynamic Programming)은 계산한 값을 임시로 기록해두었다가, 이후에 다른 계산에 활용하는 최적화 전략이다. 동적 계획법을 적용하는 전형적인 방법이나 시나리오는 있지만 정해진 구현이 있는 것은 아니므로, 특정한 알고리즘보다는 문제해결에 사용할 수 있는 패러다임에 가깝다. 동적 계획법에서 사용하는 전략들은 분할 정...

백준 온라인 저지, 7576번: 토마토, 7569번: 토마토, 17114번: 하이퍼 토마토 도입 백준 온라인 저지의 토마토 문제는 격자 공간에서의 BFS, DFS 탐색을 다루는 대표적인 문제이다. 기본적으로는 <7576번: 토마토>, <7569번: 토마토>, 그리고 <17114번: 하이퍼 토마토> 문제는 처리할 격자...

도입 너비 우선 탐색(BFS; Breadth First Search)과 깊이 우선 탐색(DFS; Depth First Search)은 어떤 대상을 처리할 때, 대상을 여러 개로 분할하여 처리하기 위해 반복 과정을 도입할 때 사용한다. 단순히 분할 가능한 대상을 처리할 때는 특별한 반복 과정 전략은 필요하지 않다. 일반적으로는 분할된 각 부분이 서로 ...

백준 온라인 저지, 1946번: 신입 사원 도입 신입 사원의 선정에 고려되는 값은 두 가지이다. 다만 이 두 가지 값을 모두 고려하면서 신입 사원을 선정하는 것은 무리가 있다. 두 값 중 하나의 값을 기준으로 정렬한다면, 순서대로 각 신입 사원을 확인하는 반복 과정에서 두 값 중 하나의 값만을 고려하는 것으로 대응할 수 있다. 서류 심사 성...

도입 지난 두 학기에 걸쳐 프로젝트 수업 <IoT컴퓨팅>와 <임베디드소프트웨어>를 수강하면서, 소위 디맥콘, 사볼콘 등으로 불리는 리듬게임 컨트롤러를 제작했다. 첫회 째는 <임베디드소프트웨어>에서 아케이드 버튼을 사용하는 컨트롤러를 제작했고, 두번째에는 <IoT컴퓨팅>에서 키보드 스위치와 핫스왑 소켓을 사...

백준 온라인 저지, 1783번: 병든 나이트 도입 병든 나이트는 세로 축 상에서는 위 아래로 이동하여 이전의 좌표로 복귀할 수 있으나, 가로 축 상에서는 항상 오른쪽으로 이동하므로 이전의 좌표로 복귀할 수 없다. 따라서 최대한 많은 가로 축 상 이동 횟수를 획득하는 것으로, 병든 나이트가 여행에서 방문할 수 있는 칸의 최대 개수를 구할 수 있다. ...

백준 온라인 저지, 15903번: 카드 합체 놀이 도입 주어진 수에서 임의로 두 수 $x$, $y$를 선택하여 $x$, $y$ 둘 다 $x + y$로 덮어쓴다. 문제 풀이 이 과정을 반복한 결과가 가능한 경우 중에서 최소이려면 항상 수 집합에서 가장 작은 두 수를 선택해야 한다. 수 집합에서 반복해서 최솟값을 선택해야하므로 우선순위 큐를 사용...