기록창고

Jürgen from Pixabay">Image by Jürgen from Pixabay  https://www.acmicpc.net/problem/3197 1. 개요 이 문제는 2차원 배열의 호수가 주어진다. 호수의 각 요소는 물('.'), 얼음('X'), 백조('L') 중 하나이고 백조는 총 2마리가 존재한다. 그리고 물과 상하좌우 중 한 곳이라도 접촉한 얼음은 하루가 지나면 녹아서 물이 된다. 이 때, 상하좌우로만 이동할 수 있는 백조는 며칠 후 서로 만날 수 있는지를 구하는 문제이다. 이 문제의 알고리즘 분류에서도 알 수 있듯, 너비 우선 탐색(BFS)을 이용하여 문제를 풀었다. 처음에는 두 백조가 서로 만날 수 있는지 구하는 코드는 항상 하던 것처럼 큐를 이용하면 될 것이라 생각했다. 그리고 얼..

HTML 삽입 미리보기할 수 없는 소스 https://school.programmers.co.kr/learn/courses/30/lessons/154540 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 이번 문제는 지도가 주어졌을 때, 'X'를 제외한 영역(섬)의 숫자 합들을 오름차순으로 정렬한 vector를 구하는 문제이다. 이 문제는 전형적인 BFS 문제라고 생각한다. BFS는 간단히 말해 특정 노드와 연결된 노드들을 모두 탐색해 나가는 방법이다. 자세한 설명은 구글링을 통해 쉽게 얻을 수 있으니 생략한다. 앞에서 말했듯, 전형적인 BFS 문제로 대략..

HTML 삽입 미리보기할 수 없는 소스 https://school.programmers.co.kr/learn/courses/30/lessons/49189 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 이번 문제는 그래프의 노드 사이의 연결 상태가 주어졌을 때, 1번 노드에서 가장 멀리 떨어져 있는 노드의 개수가 몇 개인지 알아내는 문제이다. 예를 들어, 예제에서는 1번 노드를 기준으로 2번 노드, 3번 노드는 거리가 1만큼 떨어져 있다. 그리고 4번 노드, 5번 노드, 6번 노드는 2만큼 떨어져 있다. 그렇기에 가장 멀리 떨어진 거리는 2이고 이에 해당하..

https://school.programmers.co.kr/learn/courses/30/lessons/86971# 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 이번 문제는 전력망들의 연결 상태가 주어졌을 때, 딱 하나의 연결만을 끊어서 나뉘는 두 집합의 노드 개수의 차이의 최대값을 구하는 문제이다. 이 문제의 카테고리가 완전탐색이라는 점에서 알 수 있듯, 모든 연결을 한 번 씩 끊어본 후, 두 구역의 노드 개수를 구하면 되는 간단한 문제라 할 수 있다. 그리고 노드의 개수는 BFS를 이용하여 구할 수 있다. 이것들을 고려하여 구상한 해결 절차는 다음과..

https://school.programmers.co.kr/learn/courses/30/lessons/1829 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 이번 문제는 그림의 각 구역의 색깔 정보가 주어졌을 때, 색칠할 수 있는 영역의 수와 가장 큰 영역의 넓이를 구하는 문제이다. 이 문제와 같이 어떤 2차원 배열같은 정보가 주어지고, 여기서 가장 큰 넓이나 영역의 개수를 구할 때는 BFS를 이용하여 풀 수 있다. BFS는 너비 우선 탐색으로, 어떤 지점에서 상, 하, 좌, 우로 맞닿은 부분으로 확장해나갈 수 있기 때문에 각 영역의 넓이를 구하기에 안..

https://school.programmers.co.kr/learn/courses/30/lessons/67259 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 이 문제는 경주로를 건설한다고 할 때, 최소 비용을 구하는 문제이다. 이 때, 직선 도로는 100원이 들며 두 개의 직선 도로가 직각으로 만나는 코너는 500원이 든다. 즉, 직진하면 100원이 필요하고 방향을 직각으로 꺾어서 나아가면 600원이 필요할 때의 최소값을 구하는 문제이다. 처음에는 단순한 BFS 문제라고 생각하였다. 그래서 각 지점에서의 최소 비용을 저장할 2차원 배열을 minCost..

https://school.programmers.co.kr/learn/courses/30/lessons/43163 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 이번 문제는 주어진 단어의 알파벳 하나만을 변경하면서 주어진 target을 만들 수 있는지, 만들 수 있다면 최소 몇 번 알파벳을 바꿔야 하는지를 구하는 문제이다. 이번 문제는 BFS를 이용하여 풀 수 있는 문제이다. BFS 문제는 미로 탈출 등과 같이 2차원 배열을 이용하여 푸는 경우가 많았는데, 이 문제는 그렇지 않고 주어진 단어만 검사하면 되기 때문에 다른 BFS 문제에 비하면 쉬운 편이라 ..

https://www.acmicpc.net/problem/17244 17244번: 아맞다우산 경재씨는 저녁 약속을 가기 전 챙기지 않은 물건들이 있는 지 확인하고 있다. 필요한 물건은 전부 챙긴 것 같았고 외출 후 돌아오는 길에 경재씨는 외쳤다. "아 맞다 우산!!!" 경재 씨는 매번 외출 www.acmicpc.net 이 문제는 전형적은 너비 우선 탐색 문제라 생각한다. 시작 지점을 알아낸 후, 너비 우선 탐색을 통해 도착 지점에 도달한다. 그리고 그 때까지 걸린 시간을 반환한다. 하지만, 이 문제에서 신경써야 할 부분이 하나 있다. 그것은 문제의 경재씨가 외출하기 전에 꼭 챙겨야 하는 물건들이다. 즉, 단순한 최단 시간이 아닌, 모든 물건을 다 챙겼을 때의 최단 시간을 구하는 문제이다. 챙겨야 하는 물..