백트래킹
-
문제 길이가 인 문자열 가 주어진다. 플레이어는 문자열 를 서로 겹치지 않는 개의 부분문자열로 나누려고 한다. 부분문자열은 모두 길이가 이상이어야 하며, 원래 문자열에서 연속해야 한다. 문자열을 나누는 방법에 따라 플레이어는 점수를 얻을 수 있다. 점수는 다음 과정에 따라 계산된다. 문자열 를 위 조건에 따라 나눴을 때, 등장하는 모든 부분문자열을 중복 제거하고 사전순으로 정렬한 결과를 라고 한다. 나누어진 개의 문자열이 각각 에서 번째로 등장하는 문자열이라면, 얻을 수 있는 점수는 이다. 예를 들어, abcd라는 문자열을 개의 부분문자열로 나누는 방법은 {a, b, cd}, {a, bc, d}, {ab, c, d}의 세 가지가 있다. 여기서 부분문자열을 중복 제거하고 사전 순서로 정렬한 결과는 a, a..
구름톤 챌린지 2주 차 학습 일기(Day 01)문제 길이가 인 문자열 가 주어진다. 플레이어는 문자열 를 서로 겹치지 않는 개의 부분문자열로 나누려고 한다. 부분문자열은 모두 길이가 이상이어야 하며, 원래 문자열에서 연속해야 한다. 문자열을 나누는 방법에 따라 플레이어는 점수를 얻을 수 있다. 점수는 다음 과정에 따라 계산된다. 문자열 를 위 조건에 따라 나눴을 때, 등장하는 모든 부분문자열을 중복 제거하고 사전순으로 정렬한 결과를 라고 한다. 나누어진 개의 문자열이 각각 에서 번째로 등장하는 문자열이라면, 얻을 수 있는 점수는 이다. 예를 들어, abcd라는 문자열을 개의 부분문자열로 나누는 방법은 {a, b, cd}, {a, bc, d}, {ab, c, d}의 세 가지가 있다. 여기서 부분문자열을 중복 제거하고 사전 순서로 정렬한 결과는 a, a..
2023.08.21 -
문제 풀이 1️⃣ 치킨집의 위치와 집의 위치를 미리 찾아서 리스트에 저장합니다. 2️⃣ 치킨집과의 최솟값을 찾아야하므로 변수를 max사이즈로 지정해줍니다. 3️⃣ M개수만큼의 치킨집을 골랐을 때 최솟값을 찾아야하므로 M개의 치킨집을 고르는 조합의 수를 구합니다. 4️⃣ 조합의 수를 구하기위해 브루트포스와 백트래킹 알고리즘을 사용합니다. 5️⃣ dfs 재귀를 반복하면서 조건에 충족됐을 때 집과 치킨집과의 거리를 저장합니다. 6️⃣ 저장한 치킨집과의 거리를 min함수로 저장해서 최솟값을 출력합니다. 전체 코드 from sys import stdin as s s=open('input.txt','rt') def dfs(cur,arr): global answer # arr의 길이가 M과 같으면 아래 조건문 진입 ..
[백준] 15686 치킨 배달 [python]문제 풀이 1️⃣ 치킨집의 위치와 집의 위치를 미리 찾아서 리스트에 저장합니다. 2️⃣ 치킨집과의 최솟값을 찾아야하므로 변수를 max사이즈로 지정해줍니다. 3️⃣ M개수만큼의 치킨집을 골랐을 때 최솟값을 찾아야하므로 M개의 치킨집을 고르는 조합의 수를 구합니다. 4️⃣ 조합의 수를 구하기위해 브루트포스와 백트래킹 알고리즘을 사용합니다. 5️⃣ dfs 재귀를 반복하면서 조건에 충족됐을 때 집과 치킨집과의 거리를 저장합니다. 6️⃣ 저장한 치킨집과의 거리를 min함수로 저장해서 최솟값을 출력합니다. 전체 코드 from sys import stdin as s s=open('input.txt','rt') def dfs(cur,arr): global answer # arr의 길이가 M과 같으면 아래 조건문 진입 ..
2023.06.01 -
문제 링크 : https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 풀이과정 이 문제는 그래프 탐색, bfs, 브루트 포스 알고리즘, 백트래킹 등 여러개의 알고리즘이 섞여있는 문제이다. 우선 어느 경우의 수에서 최대 안전 영역의 개수가 나오는지 모르기 때문에 모든 경우를 탐색하는 수 밖에 없다. 배열의 첫번째부터 벽을 세워나가서 벽의 개수가 3개가 됐을 때 bfs를 실행하고 바이러스를 전염 시키고 나서 안전 영역의 개수를 카운터해서 저장해놓고 제일 큰 값을 나중..
[백준] 14502 연구소 [Python]문제 링크 : https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 풀이과정 이 문제는 그래프 탐색, bfs, 브루트 포스 알고리즘, 백트래킹 등 여러개의 알고리즘이 섞여있는 문제이다. 우선 어느 경우의 수에서 최대 안전 영역의 개수가 나오는지 모르기 때문에 모든 경우를 탐색하는 수 밖에 없다. 배열의 첫번째부터 벽을 세워나가서 벽의 개수가 3개가 됐을 때 bfs를 실행하고 바이러스를 전염 시키고 나서 안전 영역의 개수를 카운터해서 저장해놓고 제일 큰 값을 나중..
2023.05.11