본문 바로가기

알고리즘/백준160

[BAEKJOON]9935 문자열 폭발 - Python 문제 요약 알고리즘 분류: 스택, 문자열 난이도: Gold4 문제내용: 문자열 주고 위에 조건에 맞게 폭발 문자열을 제거한후 문자열을 출력해라 폭발 문자열 제거후 문자열이 없으면 "FRULA"를 출력해라 사이트: https://www.acmicpc.net/problem/9935 9935번: 문자열 폭발 첫째 줄에 문자열이 주어진다. 문자열의 길이는 1보다 크거나 같고, 1,000,000보다 작거나 같다. 둘째 줄에 폭발 문자열이 주어진다. 길이는 1보다 크거나 같고, 36보다 작거나 같다. 두 문자열은 모 www.acmicpc.net 문제풀이 string = input() explore_string = input() lenth = len(explore_string) while string.count(ex.. 2023. 1. 19.
[BAEKJOON]1504 특정한 최단 경로 문제 요약알고리즘 분류: 다익스트라난이도: Gold4문제내용:1 부터 N까지 v1, v2 거쳐서 최단 경로를 구해라사이트: https://www.acmicpc.net/problem/1504 1504번: 특정한 최단 경로첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존www.acmicpc.net문제풀이   이번에는 문제 유형은 그래프 탐색중에 다익스트라 알고리즘 문제이다. 다익스트라 알고리즘 기본적인것을 묻기 때문에 자세한 설명은 여기서 참조하면된다. 문제 접근 방법 이번문제는 1 → N까지 최단 경로를 구하는 알고리즘인데 조.. 2023. 1. 17.
[BAEKJOON]1238 파티 - Python 문제 요약 알고리즘 분류: 다익스트라 난이도: Gold5 문제내용: 각 노드에서 X까지 시작점 부터 도착점 왕복하는데 걸리는 최대 시간을 구해라 사이트: https://www.acmicpc.net/problem/1238 1238번: 파티 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어 www.acmicpc.net 문제풀이 이번에는 문제 유형은 그래프 탐색중에 다익스트라 알고리즘 문제이다. 다익스트라 알고리즘 기본적인것을 묻기 때문에 자세한 설명은 여기서 참조하면된다. 풀이에 대한 설명은 각 노드에서 X까지 출발점 부터 도착점.. 2023. 1. 16.
[BAEKJOON]1916 최소비용 구하기 - Python 문제 요약 알고리즘 분류: 다익스트라 난이도: Gold5 문제내용: 시작점 부터 도착점까지의 최단거리를 구해라 사이트: https://www.acmicpc.net/problem/1916 1916번: 최소비용 구하기 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 www.acmicpc.net 문제풀이 이번에는 문제 유형은 그래프 탐색중에 다익스트라 알고리즘 문제이다. 다익스트라 알고리즘 기본적인것을 묻기 때문에 자세한 설명은 여기서 참조하면된다. 풀이에 대한 설명은 다익스트라 알고리즘알면 풀수 있기때문에 따로 설명은 하지 않겠다. C.. 2023. 1. 13.
[BAEKJOON]15686 치킨 배달- Python 문제 요약 알고리즘 분류:백트레킹 난이도: 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 문제풀이 이번에는 문제 유형은 백트레킹 알고리즘이다. 조합으로 백트레킹 문제를 풀면 되면 .. 2023. 1. 12.
[BAEKJOON]14502 연구소 - Python 문제 요약 알고리즘 분류:BFS, 시뮬레이션 난이도: Gold4 문제내용: 0은 길 1은 벽이다. 벽은 한번 부수고 이동가능하다. (0, 0) ~ (N, M)까지의 거리를 구해라 사이트: https://www.acmicpc.net/problem/14502 문제풀이 이번에는 문제 유형은 그래프 탐색중에 BFS탐색 알고리즘이다. BFS 탐색 알고리즘에 대한 설명은 여기에서 확인 해보면된다. 이번 문제는 가로세로 최대 길이가 8이라서 시간 복잡도에 제한은 없지만 구현난이도가 있어서 구현 하는 방법만 알면 쉽게 풀수 있다고 생각한다. 문제 접근방법 처음에 재귀 호출을 하는데 벽을 3개 만든다고 (0, 0)부터 시작해서 4가지 방향 탐색한후 백트레킹 방식으로 돌아올때 벽을 빼고 하면 안된다. 그 이유는 보면 (0.. 2023. 1. 11.

티스토리툴바