문제 바다 위에 개의 섬이 있다. 섬은 1번부터 N번까지 차례대로 번호가 붙어 있다. 서로 다른 두 섬 사이를 연결하는 M개의 다리도 있다. 모든 다리는 단방향으로만 이동 가능하고, 어떤 두 섬 사이를 잇는 다리는 정방향 하나, 역방향 하나씩 해서 최대 두 개이다. 어느 날, 섬들 사이에 분쟁이 일어났다. 모든 섬들은 세력을 키우기 위해 다른 섬과 연합을 결성하려고 한다. 임의의 두 섬 와 에 대해, a번 섬에서 b번 섬으로 직접 이동할 수 있는 다리와 b번 섬에서 a번 섬으로 직접 이동할 수 있는 다리가 있으면, 두 섬은 연합을 결성한다. 이때, a와b 가 연합을 결성하고 b와 c가 연합을 결성했다면 와 역시 위 조건을 만족하지 않더라도 같은 연합에 속해있는 것으로 본다. 다른 섬과 연합을 결성하지 않..
알고리즘 풀이
문제 N개의 노드와 M개의 양방향 간선으로 이루어진 그래프가 있다. 이 그래프의 노드는 1번부터 N번까지 번호가 붙어 있다. 양끝 노드가 동일한 간선은 주어지지 않는다. 플레이어는 아래 규칙에 따라 그래프에서 이동하려고 한다. 플레이어는 처음에 K 번 노드에 있다. 한 번 방문한 노드는 다시 방문할 수 없다. 시작 노드도 방문한 것으로 간주한다. 현재 노드와 간선으로 직접 연결된 다른 노드 중, 방문할 수 있으면서 번호가 가장 작은 노드로 이동한다. 플레이어가 더 이상 이동할 수 있는 노드가 없을 때, 방문한 서로 다른 노드의 개수와 마지막 노드 번호를 구해보자. 풀이 from collections import defaultdict def solve(N, M, K, edges): # Initialize ..
구름톤 챌린지 3주차 중반 정리 3주차의 핵심 주제는 BFS이다. 오늘까지는 비교적 쉬운 문제가 나와서 BFS 개념만 알고 조금 생각하면 풀 수 있는 문제였습니다 기존에 Python으로 문제를 풀었었는데, Java로 언어를 바꿀 생각입니다 왜냐하면, 알고리즘 풀이가 언어 자체에 대한 이해를 높이는데도 효과적이기 때문입니다 지금까지 2일 정도 개인 사정으로 참여하지 못했는데, 남은 주차는 이제 변수랄게 없으니 꾸준히 해보자 돌아보는 구름톤의 장점 개인적으로 알고리즘도 독서처럼 습관을 들이면 꾸준히 하게 되는 것들 중 하나인거 같다 체감상 벌써 꽤 풀었네?싶다 구름톤 챌린지는 거기에 좀 더 동기부여를 해주는 보조제 같은거지 그리고 저번 주말에 2주차 문제 풀이 문서들을 봤는데, 설명이 정말 잘되어 있다 Ja..
문제 풀이 from collections import deque def bfs(n,k,grid): dic = {} directions = [(-1, 0), (1, 0), (0, -1), (0, 1)] m = [[False for _ in range(n)] for _ in range(n)] for i in range(n): for j in range(n): current = grid[i][j] if current not in dic: dic[current]=0 count=1 if not m[i][j]: m[i][j]=True queue = deque([(i, j)]) while queue: x, y = queue.popleft() for dx, dy in directions: nx, ny = x + dx,..
문제 풀이 from collections import deque # Python 코드로 문제 해결 알고리즘 구현 (BFS 사용) def min_generators(n, grid): # 발전기 개수 초기화 generator_count = 0 # 전력 공급 상태를 저장할 리스트 초기화 supplied = [[False for _ in range(n)] for _ in range(n)] # BFS를 위한 방향 벡터 directions = [(-1, 0), (1, 0), (0, -1), (0, 1)] # 모든 칸을 순회 for i in range(n): for j in range(n): # 집이 있는 칸을 찾음 if grid[i][j] == 1 and not supplied[i][j]: # 전력이 공급되지 않은..
폭탄 구현하기 2 N,K = map(int,input().split()) mp = [list(input().split()) for _ in range(N)] m = [[0 for _ in range(N)] for _ in range(N)] def check(y,x): y-=1 x-=1 global mp,m if y
구름 찾기 깃발 N,K = map(int,input().split()) mp = [list(map(int,input().split())) for _ in range(N)] m = [[0 for _ in range(N)] for _ in range(N)] def check(x, y): global m for i in range(x-1,x+2,1): for j in range(y-1,y+2,1): if i
문자열 나누기 n = int(input()) st = input() # 최적화된 코드 # 모든 부분 문자열 찾기 (중복 제외, 길이가 n-2 이하인 부분 문자열만 포함) all_substrings = set() for i in range(n): for j in range(i + 1, n + 1): if len(st[i:j]) > n - 2: continue all_substrings.add(st[i:j]) all_substrings = sorted(list(all_substrings)) # 부분 문자열 인덱스 캐싱 substring_index_mapping = {substring: idx for idx, substring in enumerate(all_substrings)} # 최대 점수를 저장할 변수 ..
문제 상근이는 나무 M미터가 필요하다. 근처에 나무를 구입할 곳이 모두 망해버렸기 때문에, 정부에 벌목 허가를 요청했다. 정부는 상근이네 집 근처의 나무 한 줄에 대한 벌목 허가를 내주었고, 상근이는 새로 구입한 목재절단기를 이용해서 나무를 구할것이다. 목재절단기는 다음과 같이 동작한다. 먼저, 상근이는 절단기에 높이 H를 지정해야 한다. 높이를 지정하면 톱날이 땅으로부터 H미터 위로 올라간다. 그 다음, 한 줄에 연속해있는 나무를 모두 절단해버린다. 따라서, 높이가 H보다 큰 나무는 H 위의 부분이 잘릴 것이고, 낮은 나무는 잘리지 않을 것이다. 예를 들어, 한 줄에 연속해있는 나무의 높이가 20, 15, 10, 17이라고 하자. 상근이가 높이를 15로 지정했다면, 나무를 자른 뒤의 높이는 15, 15..
문제 N개의 정수 A[1], A[2], …, A[N]이 주어져 있을 때, 이 안에 X라는 정수가 존재하는지 알아내는 프로그램을 작성하시오. 입력 첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들이 A안에 존재하는지 알아내면 된다. 모든 정수의 범위는 -231 보다 크거나 같고 231보다 작다. 출력 M개의 줄에 답을 출력한다. 존재하면 1을, 존재하지 않으면 0을 출력한다. 풀이 def binary_search(arr, target): left, right = 0, len(arr) - 1 while left
