문제 2667번: 단지번호붙이기 (acmicpc.net) 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net 문제를 먼저 풀고 오시는 것을 추천합니다. 이 문제의 풀이는 BFS 외에도 다양한 방법이 있을 수 있으며 제가 보여드리는 풀이는 그 중 하나입니다. 문제분석 1은 집이 있는 곳이며, 0은 집이 없는 곳을 나타냅니다. 상하좌우로 연결된 집들의 모임이 단지입니다. 각 단지에 속하는 집의 수를 센 다음 오름차순으로 정렬해야 합니다. 입력 첫번째 줄에 지도의 크기 N (5

문제 www.acmicpc.net/problem/1753 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1≤V≤20,000, 1≤E≤300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1≤K≤V)가 주어진다. www.acmicpc.net 문제를 먼저 풀고 오시는 것을 추천합니다. 이 문제의 풀이는 다익스트라(Dijkstra) 알고리즘 풀이 외에도 다양한 방법이 있을 수 있으며 제가 보여드리는 풀이는 그 중 하나입니다. 문제분석 시작점에서 갈 수 있는 모든 정점을 찾아야 합니다. 각 정점까지의 최단경로의 경로값을 구합니다. 즉, 각 정점까지의 가중치 합이 가장 최소로 되는 값을 구합니다. 그러므로 시작점에서 갈 수..

백준 온라인 저지에서 알고리즘 문제를 풀다보면 지금 풀고 있는 문제가 얼마나 어려운지 가늠하기 어려웠습니다. 그래서 맞은 사람, 제출, 정답비율을 보고 가늠하려고 하지만 쉽지 않았습니다. 백준 온라인 저지에 문제의 난이도를 등급으로 표시하는 기능이 있었습니다. 그리고 유저별 수준을 알 수 있는 유저의 티어(등급)를 확인할 수 있는 아주 유용한 사이트도 같이 소개시켜드리겠습니다. 백준온라인저지 알고리즘 문제 난이도 표시방법 백준 온라인 저지에서 문제 난이도를 표시하는 방법을 설명드리겠습니다. 백준 온라인 저지에서 로그인한 다음 우측 상단 "설정"을 클릭합니다. 좌측 메뉴에서 solved.ac를 클릭합니다. 처음에는 "사용하기" 버튼이 표시되는데 그 버튼을 클릭하시면 아래 이미지와 같이 사용중으로 바뀌게 됩..

문제 www.acmicpc.net/problem/1012 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net 문제를 먼저 풀고 오시는 것을 추천합니다. 이 문제의 풀이는 BFS 외에도 다양한 방법이 있을 수 있으며 제가 보여드리는 풀이는 그 중 하나입니다. 문제분석 배추흰지렁이는 인접한 다른 배추로 상하좌우 이동할 수 있습니다. 배추가 모여있는 곳은 배추흰지렁이가 한 마리만 있으면 됩니다. 배추가 군데군데 모여있어서 몇 군데에 퍼져있는지 조사하면 총 몇 마리의 지렁이가 필요한지 알 수 있습니다. 0은 배추가 없는 땅이고, 1..

문제: www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 문제를 먼저 풀고 오시는 것을 추천합니다. 이 문제는 제목에도 표현되어 있지만 DFS, BFS 알고리즘을 사용할 줄 아는지 물어보는 문제입니다. 문제분석 그래프를 DFS, BFS로 탐핵한 결과를 출력하라는 문제입니다. 단, 방문할 수 있는 정점이 여러 개인 경우 정점 번호가 작은 것부터 방문하시면 되고 더이상 방문할 수 있는 점이 없으면 종료하면 됩니다. 이번 그래프..

문제 www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 문제를 먼저 풀고 오시는 것을 추천합니다. 이 문제의 풀이는 DP(Dynamic Programming) 외에도 다양한 방법이 있을 수 있으며 제가 보여드리는 풀이는 그 중 하나입니다. 문제분석 정수 X에 사용할 수 있는 연산은 세가지입니다. ① 1을 뺀다. -> X가 어떤 수이든지 1을 뺄 수 있다. ② X가 2로 나누어 떨어지면, 2로 나눈다. ③ X가 3으로 나누어 떨어지면 3으로 나눈다. 실제 문제와 다르게 알아보기 쉽게 하기 위하여 1번은 1 빼기, 2번은 2로 나누기, 3번은 3으로 나누기로 재정리하였습니다. ..