알루 코딩

오늘은 백준 2589번 '보물섬' 문제에 대해 가져와봤습니다. 해당 문제는 전형적인 bfs 문제인데, 우리가 이런 BFS 문제를 풀 때 놓치면 안될 점들을 상기하면서 문제를 설명드리겠습니다. "보물섬"문제는 주어진 지도에서 최단거리로 갈 수 있는 가장 먼 거리에 있는 두 지점을 찾는 문제입니다. 지도는 'L'(땅)과 'W'(바다)로 구성되어 있으며, 이동은 상하좌우로만 가능합니다. 이 문제의 핵심은 가장 긴 최단 거리를 찾는 것입니다. 해당 문제를 봤을 때, 뭔지 정확히는 모르셔도 '전형적인 그래프 탐색 알고리즘일 것이다' 라고 느끼셨을 겁니다. 맞습니다. 저는 이 문제를 보고 'bfs 알고리즘을 활용하면 뭔가 풀릴 것 같은데?' 라는 직감을 느꼈습니다. BFS 알고리즘을 이용하면 모든 가능한 경로를 탐..

문제를 먼저 해석해봅시다! 문제에서는 직사각형 모양의 판에 치즈가 표시되어 있습니다. 치즈는 1로 표시되며, 치즈가 없는 부분은 0으로 표시됩니다. 각 시간 단위마다 외부 공기와 접촉한 치즈가 녹아 없어지는데요, 이 때, 치즈의 내부에 있는 공기는 외부 공기로 간주되지 않는게 핵심입니다! 문제의 목표는 모든 치즈가 녹는 데 걸리는 시간과 마지막으로 녹기 전의 치즈 조각의 수를 찾는 것입니다. 이를 위해 BFS 알고리즘을 사용합니다. BFS는 주로 그래프의 최단 경로를 찾거나, 2차원 배열에서 특정 조건에 따라 요소를 탐색할 때 사용되는 알고리즘입니다. 이 문제에서는 BFS를 이용해 보드의 가장자리부터 시작하여 외부 공기를 탐색하고, 이를 통해 치즈의 녹는 경계를 식별합니다. 외부의 공기와 내부의 공기를 ..

이 문제는 DFS와 BFS를 결합한 흥미로운 접근 방식을 요구합니다. 이 문제의 핵심은 "가능한 한 많은 영역을 안전하게 보호하는 벽의 배치를 찾는 것" 입니다. 여기서 주목해야 할 점은 "모든 벽의 조합을 시도"해보고, "각 경우에 대해 바이러스가 얼마나 퍼지는지를 시뮬레이션"해야 한다는 것입니다. 이를 위해서 DFS를 사용해 벽을 세우고, BFS로 바이러스의 확산을 시뮬레이션합니다. 초기 접근 방법은 아래와 같습니다. from collections import deque import sys input = sys.stdin.readline # 벽을 3개를 세운다. -> 모든 경우의 수를 다 세어본다 : dfs # 바이러스를 퍼뜨려본다. # 0의 개수를 구한다. # 이 값을 max값과 계속 비교하면서 최..

해당 문제는 NBA 농구 경기에서 특정 팀이 얼마나 오랫동안 리드했는지를 계산하는 문제입니다. 이 문제를 풀 때는 득점 순서, 득점 시간, 현재 리드 상태를 정확히 추적하는 것이 중요합니다. 문제를 딱 봤을 때, 뭔가 "득점이 성공된 시간 순서"대로 "1팀과 2팀 중에 어떤 팀이 넣었는지" 알아야 할 것 같습니다. 그리고, 득점을 함으로써 앞서가는지 혹은 동점이 됐는지도 체크"해야 하는 것이 중요합니다. 동점이 된 순간부터는 어느 팀도 리드하지 않는 상태가 되기 때문입니다. 이렇게, 주의할 점은 아래와 같이 요약할 수 있겠습니다. 경기 시간 처리 : 경기 시간은 "시:분" 형식으로 주어지며, 이를 총 분으로 변환해야 합니다. 상태 관리 : 경기의 현재 상태(동점, 팀1 리드, 팀2 리드)를 추적해야 합니..

이 문제는 삼성sw 역량 테스트 기출 문제에 속하는데요. 삼성 코테 유형은 대체로 구현이 많이 나옵니다. 차근차근 문제를 이해하고 종이에 써가면서 풀어본다면, 끈기와 빨리 풀 수 있는 실력만 있다면 충분히 푸실 수 있는 문제입니다. 겉으로 봤을 땐, DFS나 BFS로 푸는 문제인 것 같지만, 단순 구현으로도 풀리는 문제입니다. 먼저 문제를 이해해보록할게요. 보드가 있구요. 보드 위에 주사위가 있습니다. 주사위는 보드 위 숫자가 0인 부분에 있고 명령에 따라서 굴리는 문제라고 보시면 됩니다. 그럼, 아래 문제의 내용이 이해가시나요? 주사위가 보드 위에서 굴려질 때마다 주사위 면에 적혀지는 숫자와 보드위에 적혀지는 숫자가 달라진다는 것을 알 수 있습니다. 즉, 주사위가 굴려짐에 따라 보드와 주사위의 숫자가 ..

이 문제는 유니온-파인드 집합 문제입니다. DFS나 BFS로 풀 때, 유의해야 할 점은 결국 자기자신으로 돌아오는 여행루트도 존재한다는 점입니다. 가장 직관적이게 풀 수 있는 알고리즘은 union-find 인데요, 여행계획이 어떻게 주어지더라도 결국 여행이 가능하려면, 각 도시는 같은 사이클에 존재해야 한다는 전제가 있어야 합니다. 하나의 사이클에 같이 존재하지 않는다면, 다시말해 어떠한 도시에서 어떤 도시로 갈 수 있는 방법이 존재하지 않는다면, 여행은 불가능하겠죠. 풀이는 코드를 토대로 설명드리겠습니다. import sys input = sys.stdin.readline def find_parent(parent,x): if parent[x] != x: return find_parent(parent,p..

단순한 그리디 문제였다. 맨 처음에는 그리디가 아니라 dp문제인가 싶었다. 이전에도 풀었던 기록이 있어서 단순한 그리디로도 풀릴 듯해서 바로 푼 문제였다. 코드는 아래와 같다. import sys input = sys.stdin.readline height = [] for _ in range(9): height.append(int(input())) diff = sum(height)-100 # 9명의 난쟁이 키의 합과 100의 차이를 구한다 find_two_false = False # find_two_false라는 초기변수를 False로 설정한다. for i in height: for j in height[1:]: if i + j == diff: # height를 돌면서 두 난쟁이의 합이 diff와 같으면..

비교적 쉬운 문제이지만, strip()을 안해서 처음에 index오류가 났고, 2 all check 20 했을 때, 1이 나와야 하는데 0이 나와서 계속 왜 안될까 고민하다가, number라는 입력받은 숫자를 int로 변환하지 않아서 check를 할 때 이상값이 나왔다. discard도 remove와는 다르게, 해당 값이 없으면 remove는 오류를 출력하지만, discard는 해당 값이 있을 때만 없애주고, 없으면 무시한다. 코드는 아래와 같다. import sys input = sys.stdin.readline M = int(input()) queue = set() for _ in range(M): in_put = input().rstrip() if in_put == "all": queue.updat..

처음에 문제 이해를 제대로 못해서 애먹었던 문제다. 처음에 이해한 로직은 이렇다. N개의 센서가 있을 때, K개의 집중국을 설치해야 한다. 각 집중국은 센서의 수신 가능역역을 조절하는데, 각 집중국의 수신 가능영역의 거리의 합의 최솟값을 구하면 됐다. 그러면, N개의 센서의 위치가 주어지면, 우선 그 위치를 오름차순으로 정렬한다음에, "하나의 집중국과 센서의 거리가 최소가 되려면" 평균거리로 접근하면 되는 줄 알았다. K개의 집중국을 설치해야 하므로, 평균적으로 N//K 마다 집중국을 설치하고자 했다. 말로 설명하려니까 이해가 안될 수 있으므로 그림으로 설명해보겠다. 예제 입력1을 기준으로 이해한 그림은 아래와 같다. 이렇게 하면, 예제 입력 1은 만족하는 듯 보였다. 예제 입력 2를 살펴보자. 결과가 ..

차근차근 문제에서 주어진 로직을 풀어보면, 그다지 어렵지 않은 문제였다. 문제의 로직은 따로 설명하게 없을 정도로, 문제에서 주어진 대로 그대로 구현하면 다들 풀 수 있을 것이다. 처음 입력받는 N과 M은 각각 '주차장 공간의 수'와 '차량의 수'이다. 모든 차량은 한 번씩 주차장에 들어갔다가 나오므로 (차량의 수 *2) 만큼의 출입 순서를 입력받아야 했다. 우선 index오류를 막기 위해, '요금을 나타내는 리스트'와 '각 차량의 무게를 나타내는 리스트'를 빈 리스트 [] 가 아닌 [0]으로 시작했다. 들어오는 출입 순서를 덱으로 큐화 시켰다. popleft()를 쓰기 위함이다. 이 출입리스트가 빌 때 까지, 계산을 반복한다. 이 문제에서 생각해야 할 관건은 크게 2가지만 생각해주면 됐다. 주차 가능한..