1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 핵심요소 DFS와 BFS의 정지 요건을 어떤식으로 지정해야 하는가? 인접행렬을 어떠한 방식으로 구현해야 하는가? 문제풀이 그래프를 표현하는 대표적인 방법인 인접 행렬을 구성하여 문제를 풀어야할 것 같다. 각 간선간의 이동 방향이 지정되지 않은 무방향 그래프 이므로 인접 행렬이 대칭으로 구현된다. 이제는 문제를 구현해보자. DFS > BFS 순으로 정답을 도출해내야 하기 때문에 DFS에서는 방문한 List를 저장하고 BFS에서..
1021번: 회전하는 큐 첫째 줄에 큐의 크기 N과 뽑아내려고 하는 수의 개수 M이 주어진다. N은 50보다 작거나 같은 자연수이고, M은 N보다 작거나 같은 자연수이다. 둘째 줄에는 지민이가 뽑아내려고 하는 수의 위치가 www.acmicpc.net 핵심요소 큐를 어떻게 회전시킬 수 있을까? 큐를 언제 좌,우로 회전시켜야 할까? 문제풀이 큐를 좌측으로 회전시킬 때는 List에서 첫 번째 인자를 뺀 후 뒤에 삽입하고, 큐를 우측으로 회전시킬 때는 List에서 마지막 인자를 뺀 후 맨 앞에 삽입하면 된다. 이러한 형태로 큐 회전 함수를 구현해보았다. 그러면 큐를 언제 회전시켜야 할까? 큐를 회전시킬 때 가운데를 기준으로 왼쪽으로 가까울수록 좌측회전이 이동 경로가 짧고 가운데를 기준으로 오른쪽으로 갈수록 우측..
2805번: 나무 자르기 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보 www.acmicpc.net 핵심요소 잘린 나무의 총 길이를 어떠한 방식으로 계산할 수 있을까? 절단기의 높이 조절의 기준을 무엇으로 해야 할까? 문제풀이 잘린 나무의 총 길이는 현재의 높이에서 잘릴 수 있는 모든 나무를 비교하면서 값을 하나씩 추가하도록 하자. 절단기의 높이는 잘린 나무의 길이가 원하는 값보다 클 경우 높이고, 잘린 나무의 길이가 원하는 값보다 낮을 경우 낮추도록 한다. 일반적인 브루트 포스로 문제를 풀이하기에는 1초라는 시간이 부족..
2869번: 달팽이는 올라가고 싶다 첫째 줄에 세 정수 A, B, V가 공백으로 구분되어서 주어진다. (1 ≤ B < A ≤ V ≤ 1,000,000,000) www.acmicpc.net 핵심요소 매일마다 올라가는 총 높이는 몇인가? 문제풀이 하루에 올라갈 수 있는 높이에서 미끄러지는 높이를 빼면 매일 올라갈 수 있는 총 높이가 나온다 그러면 매일 마다 올라갈 수 있는 높이를 막대의 총 길이에서 나누면 해결되지 않을까? 어? 뭔가 이상하다 도착한 후에는 더는 미끄러지지 않는데 미끄러지는 것까지 계산해버린 것 같다. 그러면 총 높이에서 1번 미끄러지는 것을 빼고 계산을 하면 될 것 같다. 첫 번째 예시에 있는 결과가 나왔지만, 뭔가 하나 빠트린 게 있는 것 같다. 다른 예시를 사용해서 테스트해 보도록 하자..
백준 1436번 문제입니다. 1436번: 영화감독 숌 666은 종말을 나타내는 숫자라고 한다. 따라서, 많은 블록버스터 영화에서는 666이 들어간 제목을 많이 사용한다. 영화감독 숌은 세상의 종말 이라는 시리즈 영화의 감독이다. 조지 루카스는 스타 www.acmicpc.net 핵심요소 처음 시작되는 숫자 666 ~ 임의의 숫자까지 Loop를 돌면서 666이 포함된 수를 찾는 것 666을 찾을 때 쓰는 방법은 어떻게 확인해야 하는가? 문제풀이 1. 요소처럼 문제의 첫 시작은 for 문을 돌면서 666 ~ 임의의 숫자까지 Loop를하면서 해당하는 요소가 발견되었을 경우 카운트를 추가 시켜 몇 번째 해당하는 수 인지 확인하도록 설정합니다. 임의의 숫자는 10,000,000으로 지정합니다. 2. 파이썬에는 in..
백준 1011문제 입니다. 1011번: Fly me to the Alpha Centauri 우현이는 어린 시절, 지구 외의 다른 행성에서도 인류들이 살아갈 수 있는 미래가 오리라 믿었다. 그리고 그가 지구라는 세상에 발을 내려 놓은 지 23년이 지난 지금, 세계 최연소 ASNA 우주 비행 www.acmicpc.net 문제의 핵심은 속도의 곡선이 좌상향 우하향을 그리면서 그래프가 그려져야한다고 생각합니다. Speed값을 루프마다 1씩 증가를 시키고, [Speed + Speed-1 + Speed-2 .... 1 ] 까지의 값을 계산해 다음에 오는 값을 미리 확인합니다. 이것을 now_length라고 정의 하였습니다. 만약 다음에 올 Speed의 값이 현재의 남은 거리 보다 크다면 그때부터는 Speed를 1씩..
