일지 & 개발

문제 요약 알고리즘 분류: 다익스트라 난이도: Gold5 문제내용: 시작점 부터 도착점까지의 최단거리를 구해라 사이트: https://www.acmicpc.net/problem/1916 1916번: 최소비용 구하기 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 www.acmicpc.net 문제풀이 이번에는 문제 유형은 그래프 탐색중에 다익스트라 알고리즘 문제이다. 다익스트라 알고리즘 기본적인것을 묻기 때문에 자세한 설명은 여기서 참조하면된다. 풀이에 대한 설명은 다익스트라 알고리즘알면 풀수 있기때문에 따로 설명은 하지 않겠다. C..

문제 요약 알고리즘 분류:백트레킹 난이도: Gold5 문제내용: 가로 세로 길이 N, 폐점 안할 치킨 집 M, 지도 2차원 배열 치킨 거리: (x1, y1) ~ (x2, y2) = |x1 - x2| + |y1 - y2| 도시의 각 집과 치킨 집의 치킨 거리의 최소 합 을 구해라 사이트: https://www.acmicpc.net/problem/15686 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net 문제풀이 이번에는 문제 유형은 백트레킹 알고리즘이다. 조합으로 백트레킹 문제를 풀면 되면 ..

문제 요약 알고리즘 분류:BFS, 시뮬레이션 난이도: Gold4 문제내용: 0은 길 1은 벽이다. 벽은 한번 부수고 이동가능하다. (0, 0) ~ (N, M)까지의 거리를 구해라 사이트: https://www.acmicpc.net/problem/14502 문제풀이 이번에는 문제 유형은 그래프 탐색중에 BFS탐색 알고리즘이다. BFS 탐색 알고리즘에 대한 설명은 여기에서 확인 해보면된다. 이번 문제는 가로세로 최대 길이가 8이라서 시간 복잡도에 제한은 없지만 구현난이도가 있어서 구현 하는 방법만 알면 쉽게 풀수 있다고 생각한다. 문제 접근방법 처음에 재귀 호출을 하는데 벽을 3개 만든다고 (0, 0)부터 시작해서 4가지 방향 탐색한후 백트레킹 방식으로 돌아올때 벽을 빼고 하면 안된다. 그 이유는 보면 (0..

문제 요약 알고리즘 분류: 그리디, 정렬, 힙 난이도:Gold5 문제내용: N개의 책과 최대 들고갈수 있는 책의 개수 M이 있다. 모든 책을 갔다 놓을수 있도록 최소 거리를 구해라(다시 돌아올 필요는 없다.) 사이트: https://www.acmicpc.net/problem/1461 문제풀이 이번 문제는 그리디와 힙을 응용해야 되는문제이다. 그리디 알고리즘 약간 아이디어 문제측에 속한다. 정답을 어떻게 구할지만 구현은 쉽다. 그리디와 힙에 대한 설명은 아래의 사이트에서 확인해보면된다. 그리디: https://jih3508.tistory.com/70 힙: https://jih3508.tistory.com/81 문제 접근 방법 이번 그리디 관련한 문제는 음수영역과 양수 영역을 따로 구분해서 책을 꽃아야 한다..

문제 요약 알고리즘 분류: 그리디, 정렬 난이도:Gold5 문제내용: N개의 센서와 K개 집중국이 있다. K개의 기지국을 설치해서 송신할수 있도록 최소 거리를 구해라. 사이트: https://www.acmicpc.net/problem/2212 2212번: 센서 첫째 줄에 센서의 개수 N(1 ≤ N ≤ 10,000), 둘째 줄에 집중국의 개수 K(1 ≤ K ≤ 1000)가 주어진다. 셋째 줄에는 N개의 센서의 좌표가 한 개의 정수로 N개 주어진다. 각 좌표 사이에는 빈 칸이 하나 있 www.acmicpc.net 문제풀이 이번 문제는 그리디문제인데, 약간 아이디어 문제측에 속한다. 정답을 어떻게 구할지만 구현은 쉽다. 그리디에 설명은 여기에서 확인 해보면된다. 문제 접근 방법 예제 1번을 그림으로 나타낸 것..

문제 요약 알고리즘 분류: 백트래킹 난이도: Silver3 문제내용: 같은 수를 여러 번 골라도 된다. 길이가 K인 수열 A가 A1 ≤ A2 ≤ ... ≤ AK-1 ≤ AK를 만족하고 M개의 수열을 예제와 같이 중복없이 사전순으로 출력해라. 사이트 주소: https://www.acmicpc.net/problem/15666 15663번: N과 M (9) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 문제풀이 이번 문제는 백트레킹 문제이다. 백트레킹 관련 자세한 내용은 아래의 사이트에 참조하면된다. https://jih3508.tistory..

문제 요약 알고리즘 분류: 백트래킹 난이도: Silver3 문제내용: 같은 수를 여러 번 골라도 된다. 길이가 M개의 수열을 예제와 같이 중복없이 사전순으로 출력해라. 사이트 주소: https://www.acmicpc.net/problem/15663 15663번: N과 M (9) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 문제풀이 이번 문제는 백트레킹 문제이다. 백트레킹 관련 자세한 내용은 아래의 사이트에 참조하면된다. https://jih3508.tistory.com/84 [알고리즘 이론] 백트래킹(Backtracking) 이론 이..

문제 요약 알고리즘 분류: 백트래킹 난이도: Silver3 문제내용: 같은 수를 여러 번 골라도 된다. 길이가 K인 수열 A가 A1 ≤ A2 ≤ ... ≤ AK-1 ≤ AK를 만족하고 M개의 수열을 사전순으로 출력해라. 사이트 주소: https://www.acmicpc.net/problem/15657 15657번: N과 M (8) N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다. N개의 자연수 중에서 M개를 고른 수열 www.acmicpc.net 문제풀이 이번 문제는 백트레킹 문제이다. 백트레킹 관련 자세한 내용은 아래의 사이트에 참조하면된다. https://jih3508.tistory.com/84 ..