gaebaljob

시니어 (9년 이상)

<h3 style="text-align: left">1. <code>STL 제약이 있을 경우</code></h3>파이썬은 기본적으로 프로그램이 무한 루프에 빠져 다운되는 것을 막기 위해, 함수가 자기 자신을 호출하는 '재귀 깊이'를 약 1,000번으로 제한하고 있습니다.<code>sys.setrecursionlimit</code>을 사용할 수 없는 상황이라면, 재귀 함수 대신 스택(Stack)을 활용한 반복문 형태의 DFS로 코드를 수정해야 합니다. 파이썬의 기본 리스트는 <code>append()</code>와 <code>pop()</code>을 지원하므로 외부 모듈 없이도 완벽하게 스택으로 활용할 수 있습니다.작성해주셨던 코드를 기반으로, 모듈 임포트 없이 기본 기능만 사용하여 수정한 반복문 DFS 코드는 다음과 같습니다.<pre><code># sys 모듈을 비롯한 어떤 import도 사용하지 않습니다.

N, M = map(int, input().split())

# defaultdict 대신 기본 딕셔너리와 리스트 컴프리헨션 사용
dic = {i: [] for i in range(1, N + 1)}
visited = set()
result = 0

for _ in range(M):
 x, y = map(int, input().split())
 dic[x].append(y)
 dic[y].append(x)

# 재귀 대신 스택(리스트)을 사용한 반복문 DFS
def dfs_iterative(start_node):
 stack = [start_node] # 탐색을 시작할 노드를 스택에 넣습니다.
 
 while stack: # 스택에 노드가 남아있는 동안 계속 반복
 node = stack.pop() # 스택의 가장 위(마지막)에 있는 노드를 꺼냄
 
 if node not in visited:
 visited.add(node)
 # 현재 노드와 연결된 방문하지 않은 노드들을 스택에 추가
 for n in dic[node]:
 if n not in visited:
 stack.append(n)

# 모든 정점을 순회하며 연결 요소 찾기
for i in range(1, N + 1):
 if i not in visited:
 dfs_iterative(i)
 result += 1

print(result)</code></pre><code>sys.stdin.readline</code>을 쓰지 못해 <code>input()</code>을 사용하면 속도가 다소 느려집니다. 하지만 모듈 사용을 막아둔 실제 코딩테스트라면, 출제자 역시 이를 감안하여 시간 제한을 넉넉하게 두거나 테스트 케이스의 크기를 조절해 두었을 테니 이 부분은 너무 걱정하지 않으셔도 됩니다.&nbsp;<h3 style="text-align: left">2. 수업 노트에 있는 Queue를 사용하는 코드</h3>수업 노트에서 보신 코드는 DFS가 아니라 BFS(Breadth-First Search, 너비 우선 탐색) 알고리즘입니다.<ul><li>DFS (깊이 우선 탐색): 한 방향으로 갈 수 있을 때까지 깊게 파고드는 방식입니다. (질문자님이 처음에 작성하신 방식)</li><li>BFS (너비 우선 탐색): 시작점에서 가까운 이웃 노드들부터 물결이 퍼지듯 넓게 탐색하는 방식입니다.</li></ul>11724번 문제처럼 단순히 '그래프가 몇 덩어리로 나뉘어 있는지'를 찾는 문제에서는 노드를 빠짐없이 방문하기만 하면 되므로, DFS와 BFS 중 편한 것을 선택해서 풀면 됩니다. 특히 BFS는 구조적으로 재귀를 사용하지 않기 때문에 지금처럼 <code>RecursionError</code>를 피해야 할 때 아주 좋은 대안입니다.⚠ 단, 주의할 점이 하나 있습니다.질문자님께서 겪고 계신 제약 조건이 <code>import</code> 자체를 완전히 금지하는 것이라면, 수업 노트에 있는 <code>from collections import deque</code> 역시 사용할 수 없습니다. <code>collections</code>도 파이썬의 내장 라이브러리이기 때문입니다.만약 <code>deque</code>도 쓸 수 없는 상황이라면, 앞서 스택을 만들 때처럼 파이썬 기본 리스트를 큐로 활용해야 합니다.기본 리스트에서 맨 앞의 데이터를 꺼내는 <code>pop(0)</code>은 <code>deque</code>보다 속도가 느립니다. 하지만 이 문제에서는 정점(N)이 최대 1,000개로 매우 작기 때문에 기본 리스트만으로도 시간 초과 없이 무사히 통과할 수 있습니다.

itertools, sys같은 STL을 사용할 수 없는 경우 질문드립니다.(백준 11724)

네, 잘 작성하셨습니다. DFS 코드는 문제 없이 정상적으로 동작합니다.&nbsp;차이점을 이미 잘 아시겠지만 정리하자면:&nbsp;<ul><li>제 코드(ver 1): 이동할 방향(dirY, dirX)을 배열로 정의하고, for문으로 상하좌우를 탐색합니다. 이 방식은 이동 가능한 방향이 많을 때 코드를 간결하게 작성할 수 있습니다.</li><li>작성하신 코드: if문을 사용해 아래(y + n)와 오른쪽(x + n) 방향을 각각 따로 확인하고 있습니다. 이 방법도 문제에서는 동일하게 동작하고, 오히려 더 직관적으로 이해하기 쉽습니다.</li></ul>&nbsp;&nbsp;두 방식 모두 visited 배열을 활용하기 때문에 논리적으로 완벽하며, 결과에도 차이는 없습니다.

dfs 부문을 이렇게 작성해도 되나요?

안녕하세요,&nbsp;저도 처음 접했을 때 이 부분이 많이 헷갈렸어서 두 가지 답변을 드려볼게요:) 우선 변수를 서로 바꾸는 것은 전혀 문제 없습니다. 아시다시피 변수명은 문법적 오류만 없으면 컴퓨터는 전혀 신경을 쓰지 않으니 본인이 이해하기 편한 코드를 짜는 것이 가장 중요합니다.다만 대부분의 분들이 이러한 표기법을 사용해서 저도 같은 방식으로 작성하고 있고, 추후에 취업이 되신다면 모두가 이해할 스 있는 읽기 좋은 코드도 중요해집니다.아직은 이것까지 고민하실 때는 아니니 본인이 직관적으로 이해할 수 있는 코드/변수명을 사용하시길 권장드립니다!

x랑 y를 거꾸로 쓰는 개념이 너무 헷갈립니다...

안녕하세요,&nbsp;우선 두번째로 이부분에 정리하신 내용이 맞습니다!<blockquote>아니면 answer로 하면 단순 dfs 함수 호출 횟수를 늘리는거고, 이 문제의 본질은 트리의 depth를 물어보는거가 되는거고 그래서 count로 depth를 알려주는건가 싶습니다</blockquote>&nbsp;자세하게 부연 설명을 추가하면 이렇습니다.dfs 함수에 count 파라미터를 넣는 이유는 현재 노드까지의 거리를 추적하기 위함입니다. answer 변수를 단순히 전역으로 선언하고 dfs 함수 내부에서 answer++를 하는 방식은 올바른 촌수를 계산하지 못할 수 있습니다.​이유:​올바른 촌수(거리) 계산: 이 문제는 시작 노드에서 목표 노드까지의 가장 짧은 거리를 찾는 것입니다. dfs(idx, count)처럼 재귀 호출 시 count + 1을 파라미터로 넘겨주면, 각 함수 호출마다 현재 노드까지의 거리가 정확하게 계산됩니다.​전역 변수 문제: 만약 answer를 전역 변수로 두고 answer++를 한다면, 재귀 호출이 끝난 후 다른 경로를 탐색할 때 answer 값이 그대로 유지되어 올바르지 않은 값이 나올 수 있습니다. 예를 들어, dfs 함수가 깊이 3까지 들어갔다가 백트래킹(backtracking)을 할 때, answer 값은 3이 된 상태로 남아있게 됩니다. 새로운 경로를 탐색할 때 이전에 증가한 answer 값부터 시작하게 되므로, 정확한 거리를 계산할 수 없습니다.​지역적 범위와 재귀의 특징: count 파라미터는 함수 호출 시마다 독립적인 값으로 전달됩니다. 이는 각 재귀 호출이 자신의 count 값을 가지게 되어, 여러 탐색 경로가 서로 영향을 주지 않고 독립적으로 거리를 계산할 수 있게 해줍니다. 즉, 한 경로가 실패하여 돌아오더라도 다른 경로를 탐색할 때 초기 상태인 0부터 다시 시작할 수 있습니다.​결론적으로, count 파라미터는 dfs가 재귀적으로 여러 경로를 탐색하는 과정에서 각 경로의 깊이(거리)를 정확하게 측정하기 위한 필수적인 요소입니다.

dfs 파라미터에 count를 넣는이유

안녕하세요 dnrwls91152585님 :)두 for문은 역할이 완전히 다릅니다. 하나는 그래프의 '틀'을 만드는 초기화용이고, 다른 하나는 그 틀에 간선 '내용'을 채우는 용도입니다.<ol><li><code>for (int i = 1; i <= N; i++)</code> 루프의 역할<ul><li>이 코드는 정점의 개수(N)만큼 반복하면서, 각 정점에 연결될 간선들을 저장할 빈 <code>ArrayList</code>를 만들어주는 역할을 합니다.</li><li><code>graph = new ArrayList[MAX]</code> 라고 선언만 하면 <code>graph</code>의 각 칸은 비어있는 상태(<code>null</code>)라서, 이 과정을 거치지 않고 <code>graph[i].add()</code>를 호출하면 오류가 납니다.</li><li>즉, <code>N</code>개의 정점 각각에 대해 "이제부터 여기에 간선을 저장할 수 있어"라고 준비시켜주는 단계입니다.</li><li>문제에서 노드의 번호를 0 ~ N-1이 아닌 1 ~ N까지로 정의했기 때문에 1 부터 N을 포함한 지점까지 반복하도록 정의했습니다.</li></ul></li><li><code>for (int i = 0; i < M; i++)</code> 루프의 역할<ul><li>이 코드는 간선의 개수(M)만큼 반복하면서, 입력으로 주어진 간선 정보를 읽어옵니다.</li><li><code>u v</code>를 읽어서, 위 1번 과정에서 만들어 둔 <code>graph[u]</code> 리스트에 <code>v</code>를 추가하고, <code>graph[v]</code> 리스트에 <code>u</code>를 추가하는 일을 합니다.</li><li>미리 준비된 공간에 실제 데이터를 채워 넣는 단계라고 보시면 됩니다.</li></ul></li></ol>요약하자면, 첫 번째 N번 반복하는 루프는 <code>N</code>개의 빈 서랍(리스트)을 만드는 작업이고, 두 번째 M번 반복하는 루프는 <code>M</code>개의 서류(간선)를 해당 서랍에 넣는 작업이라고 생각하시면 쉽습니다. 그래서 하나는 정점 수(N)를 기준으로, 다른 하나는 간선 수(M)를 기준으로 반복하는 것입니다.

graph 채울때 for문 설계 질문

안녕하세요 eovnfjfpa4963님!말씀하신 대로 N 이 큰 경우 ArrayList를 사용하는 것이 기본적인 원칙인데, 해당 유형에서는 그 정도로 큰 N이 주어지는 경우가 드물다고 보셔도 될 것 같습니다! 이전 유형처럼 연결된 정보를 map으로 저장하는 경우, '누가 누구와 저장되었는가'를 저장하기 위한 논리적 지도를 의미하지만, 해당 문제 유형의 map은 실제로 이동이 가능한 물리적 지도를 뜻하기 때문에, '어떤 위치에 0/1이 저장되어 있는가'의 정보를 담고 있어서, 기존 방식처럼 어레이 리스트로 압축하기가 까다롭습니다. 그래서 해당 유형에 대해서는 어레이 리스트 활용을 고민하지 않으셔도 될 것 같습니다! 만약 하셔야 한다면 말씀하신대로 2차원 어레이 리스트를 만들어서 x, y 좌표에 맞게 arrayList를 접근해야 하고, 해당 arrayList는 int 하나가 아닌 다음 방문 가능한 (x,y) 좌표 정보를 묶어서 저장해야될 것 같습니다! (아니면 x * N + y 이런 식으로 한 값을 저장하여 값을 읽을 때 매번 z / N => x, z % N => y 이런식으로 나눠쓰는 방법도 가능하고요)

질문있습니다.

안녕하세요 세진님!알고리즘이 재밌어지셨다니... 최고의 칭찬이네요 ㅠ 강의 잘 들어주셔서 정말 감사합니다!다만 제가 요즘 제 나름의 커리어 변화를 시도하고 있어서 강의 제작은 많이 늦어지고 있습니다. ㅠ 마음 같아서는 얼른 만들어서 올려드리겠다고 하고 싶지만, 세진님의 취업을 위해서는 다른 강의를 통해서 배우시는 것이 도움될 것 같습니다.그리디는 어떤 면에서는 단순한데, 알고리즘이라고 하기에는 공통적인 풀이가 존재하지 않아서 약간 어려우실수도 있습니다. 그저 '미래는 생각하지 않고 당장 앞에 놓인 선택에서 최선을 선택한다'라는 태도(?)의 알고리즘이고, 어떤 면에선 우리가 많이 들어온 마시멜로 이야기와 정반대로 눈 앞에 마시멜로가 보이면 당장 먹고, 내일 2개가 보이면 2개를 먹는 것을 선택하는 알고리즘입니다.그래서 문제를 어떻게 정의할지 (어떤 기준으로 정렬하면, 미래를 따지지 않고 당장 눈앞에 놓인 선택만 해도 미래까지 좋은 선택이 될까?)가 핵심이고, 이게 정의되고 나면 구현은 생각보다 정말 간단한 유형입니다.그래서 저는 이 유형은 오래 고민하시기 보다 여러 문제를 풀며 감을 익히는 걸 추천드려요. 시간도 많고 여유롭다면 한 문제를 일주일 동안 고민하시는 게 사고력에 가장 큰 도움이 되지만... 문제 은행식 알고리즘 시험을 대비하기엔 너무 안일한 계획이기도 해서요. 그리디도 여러 문제 풀어보시면 '이래서 정렬을 잘하라 했구나' 감이 오실거에요!이렇게 정리하고 나니 유형별로 문제 뽑아서 얼른 강의 촬영하고 싶어지네요 ㅠ 제 나름의 도전에서 아직 길을 찾고 있는 중이라 조금 더 자리가 잡히면 강의 잘 준비해서 찾아뵙겠습니다. 물론 그땐 꼭 취업하셔서 뵈어요! 공부 화이팅 하세요 세진님 :)

다른 강의 언제나오나용?

안녕하세요 mangmang02211119님 :)좋은 질문 감사합니다! 말씀하신 것처럼, 문제에서 정의된 변수 기준으로 보자면 <code>M</code>이 행 (row), <code>N</code>이 열 (column)이 맞기 때문에, 강의 코드에서 사용한 <code>N</code>과 <code>M</code>의 역할은 문제 기준과 반대입니다.즉, 문제 기준에 맞추려면 <code>M → N</code>, <code>N → M</code>으로 바꿔주는 게 맞습니다.다만, 현재 강의 코드에서는 <code>N</code>을 행 개수로, <code>M</code>을 열 개수로 사용하는 방식으로 일관되게 구현했기 때문에, 변수 이름만 문제와 다를 뿐 실제 동작에는 문제가 없습니다. DFS 탐색 범위나 종료 조건도 이 기준에 맞춰 작성되어 있어서 코드 자체는 정상 작동합니다.결론적으로, ✔ 코드 논리에는 문제가 없지만, ✔ 문제 설명과 변수 의미를 맞추려면 <code>M</code>과 <code>N</code>의 역할을 바꿔주는 게 맞습니다!제가 이 부분을 틀린지도 모르고 당연히 N, M 이라고 가정하고 작성했네요..!! 정확하게 잡아주셔서 감사합니다 :)

백준 13565 침투 질문

안녕하세요 정구호님 🙂 입력 형태는 문제에서 주어지는 예제 입력 형태를 보고 설명과 함께 유추할 수 있습니다! 대부분의 경우 이 부분은 헷갈리지 않도록 명확하게 적어주고 있어서, 예제 형태를 그대로 적용하시면 될 것 같습니다!&nbsp;그리고 다음 추가 질문에 대해 답변 드리자면<blockquote>하나더 질문이 있는데 섬의개수에서 for i in range(1,H+1)row = list(map(int,input().split())) 이 부분으로 그래프를 채울수 있는거 아닌가요? 이 코드 이후에 것(for j in range(1, M + 1): map_[i][j] = (row[j - 1] == 1))들은 왜 구현한건지 이해가 잘안됩니다</blockquote>row 변수는 한 행에 해당하는 입력 값을 하나의 list로 입력 받은 것이고, 이 정보를 다시 map에 반영하기 위해서는 row list의 값을 확인하여 하나씩 입력해줘야 하기 때문에 이렇게 넣었습니다!

침투/섬개수 질문

안녕하세요 nurugji님 🙂 말씀하신 대로 대부분의 경우에는 사이클이 없는 구조, 즉 트리 형태에서 주로 사용됩니다. 이 경우, 노드 u와 v 사이의 경로는 유일하기 때문에 count 변수를 이용해 거리를 쉽게 계산할 수 있습니다.그러나 사이클이 존재하는 그래프에서도 몇 가지 추가 처리를 통해 이 방식을 사용할 수 있습니다. 예를 들어:<ol><li>방문 여부(visited 배열)를 관리하여 이미 방문한 노드를 다시 방문하지 않도록 처리하면 사이클을 무시할 수 있습니다.</li><li>DFS 시작점을 고정하고, 각 노드의 거리를 기준점(루트 또는 특정 노드)으로 계산한 후, 두 노드의 거리를 비교하여 결과를 구할 수 있습니다.</li></ol>하지만 일반적으로 사이클이 있는 그래프에서는 BFS나 다익스트라 알고리즘과 같은 방법이 더 안정적이고 효율적일 수 있습니다.따라서 사이클이 없는 경우에는 설명 드린 방식이 유효하지만, 사이클이 있는 경우에는 위와 같은 추가 처리를 고려해 주시면 더 정확한 결과를 얻을 수 있습니다.혹시 추가로 궁금하신 부분이 있다면 알려주세요! 감사합니다 :)

gaebaljob

Posts