그래프에서 사이클을 판단하는 것은 매우 중요합니다. 여러 그래프 탐색 알고리즘에서도 제한시간 이내에 탐색을 완료할 수 있도록 사이클에 빠지지 않기 위해 방문을 기록하는 배열을 사용하기도 합니다. 사이클과 관련된 알고리즘 문제에서는 대표적으로 사이클의 존재 여부를 판별하는 문제와 사이클에 포함된 노드를 활용하는 문제가 있습니다. 탐색하고자 하는 그래...

이 포스트는 백준 사이트의 불 문제 풀이입니다. 문제 해결 과정 이 문제는 불이 상하좌우 퍼지는 과정에서 상근이가 탈출할 수 있는지 확인하는 문제입니다. 여기서 불은 상하좌루로 동시에 퍼지기 떄문에 주어진 지형에서 퍼지는 과정을 BFS로 확인할 수 있습니다. 문제에서 최종적으로 구하고자 하는 것은 상근이가 탈출하는 시간이기 때문에 불이...

람다 연산자 C#에서 람다 식은 익명의 함수를 만들 수 있는 기능입니다. 즉, 함수의 이름이 존재하는 일반 함수와 다르게 이름을 선언하지 않고 사용할 수 있습니다. 이러한 람다식은 람다 연산자 =>를 사용해서 짧은 코드를 작성할 수 있고 그로 인해서 코드의 가독성을 향상 시킬 수 있다는 효과가 있습니다. 아래는 간단한 예제로 함수를 호출하여...

이 포스트는 개인 프로젝트의 기록입니다. C# 을 사용해 보기 위해 무엇을 만들어볼까 고민 중 SFML처럼 Monogame이라는 오픈소스 프로젝트를 접하게 되었습니다. Monogame은 MS(MicroSoft)의 XBOX 360 게임 개발을 위해 배포하던 SDK를 오픈소스 커뮤니티에서 크로스 플랫폼으로 확장한 시킨 프로젝트입니다. 또한 가장 큰 ...

이 포스트는 프로그래머스 사이트의 징검다리 문제 풀이입니다. 문제 해결 과정 이 문제는 rocks 배열에 저장된 위치에 distance 거리 안에 돌이 배치되어 있을 때, n개를 제거한 뒤 인접한 돌의 최소 거리 중 최댓값을 구하는 문제입니다. 처음 문제를 시도할 때, 저는 (rocks.size() - n)개의 돌을 선택하는 조합을 사...

이 포스트는 백준 사이트의 스마트 택시 문제 풀이입니다. 문제 해결 과정 이 문제는 손님에게 방문하고 목적지까지 최단경로로 이동하는 것을 M번 반복하는 문제입니다. 이때, 현재 연료가 0이면 ‘-1’을 출력해야 하므로 중요한 것은 이동거리에 따른 연료의 소비입니다. 이 문제에서 사용할 최단 거리 알고리즘 후보와 가능 여부는 다음과 같습...

deque은 vector처럼 랜덤 액세스가 가능하고 list처럼 양방향 push, pop이 가능한 자료구조로 double ended queue의 약자입니다. 이번 포스트에서는 deque의 특징과 멤버 함수에 대해 알아보겠습니다. Deque 메모리 공간 확보 방법 deque은 벡터처럼 랜덤 액세스가 가능해 닮아보이지만, 원소 추가에 대한 메모리...

이 포스트는 백준 사이트의 사다리 조작 문제 풀이입니다. 문제 해결 과정 이 문제는 주어진 상황에서 N개의 사다리가 시작 번호와 도착 번호가 동일하도록 만들기 위한 최소의 사다리 추가 수를 구하는 문제입니다. 따라서 이 문제에서는 2가지 과정이 필요합니다. 현재 상태에서 N개가 각자 동일한 번호(시작 번호 = 도착 번호)인지 확...

이 포스트는 백준 사이트의 백조의 호수 문제 풀이입니다. 문제 해결 과정 이 문제에서 결과를 출력하기 위해서는 3가지 행동을 반복해서 진행해야 합니다. 두 마리의 백조가 만날 수 있는지 확인 물에 인접한 얼음 녹이기 출력할 날짜 증가 1번 과정의 경우, 탐색 알고리즘(BFS, DFS, … etc)를 사용하여 풀 수 있고...

이 포스트는 백준 사이트의 RGB거리 문제 풀이입니다. 문제 해결 과정 문제를 작은 문제들로 나누어 풀 수 있는 문제로 DP(다이나믹 프로그래밍)를 활용하여 해결하였습니다. 문제에서 주어진 3가지 조건을 지키며 집을 칠하는 최소 비용을 구해야하므로 먼저, 점화식을 찾고자 하였습니다. 문제의 3가지 조건이 말하는 의미는 결국 이웃한 집끼...