https://www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어 www.acmicpc.net 전형적인 DFS/BFS 문제는 풀기 좀 쉽다고 들었는데, 무슨 의미인지 알 것 같다. # PYTHON CODE (1) - BFS import sys n = int(sys.stdin.readline()) m = int(sys.stdin.readline()) tree = [[] for _ in range(n + 1)] for _ in range(m): a, b = map(int, sys.stdin.read..
https://www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net 분류는 BFS지만 DFS로도 구현할 수 있는 문항이다. 이전 문제와 마찬가지로 전형적인 BFS/DFS 문제라는데 아직 어려운 것 같다.. 코드 또한 상당히 비슷하긴 하다. # PYTHON CODE(1) - BFS import sys def bfs(tree, a, b): cnt = 1 # 아래 for문이 실행할 때 tree값이 1일때부터 확인하므로 0이 아니라 1로 설정. queue = deque()..
https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 어제 문제 풀 때만 해도 아 이런 느낌이구나 하는 감이 왔었는데, 문제가 조금만 달라지면 그 느낌도 초기화가 되나 보다. 경건한 마음으로 구글링의 도움을 받았다. 100% 이해 완료하긴 했는데, 뭔가 비효율적인 것 같으면서도 거의 모든 풀이가 단일화되어 있는 걸 보면 이게 가장 좋은 풀이인가 싶은 의문이 든다. 풀이가 굉장히 알고리즘스러운데, dx, dy의 설정으로 상하좌우의 경우를 생각해주는 건 진짜 괜찮은 방법인 것 같다. ..
https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 트리 알고리즘이라고 쓰기는 했지만, DFS, BFS 문항 중 가장 기본 문제인 것 같다. 실버2에 랭크되어 있는 것에 비해 아직 숙련도가 많이 부족해서 입력값 정리, 알고리즘 전개 방식 등 다방면에서 많이 헷갈리더라. 지난번에 포스팅했던 내용과 큰 차이는 없지만 이렇게까지 기억이 안나는 걸 보면 복습이 확실히 중요한 듯싶다. 백준 티어 실버1으로 올랐다. 조금..
https://www.acmicpc.net/problem/11725 11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net 본격적으로, BFS - DFS 문제들이 등장한다. 어떤 식으로 작동하는지는 책을 통해 공부한 바가 있지만, 실질적으로 구현해보지는 않아서 구글링을 통해 몇 번 연습한 뒤 문제 풀이에 임했다. 우선 느낀 점은 단순히 알고리즘을 구현하는 일과 그걸 직접 문제에 적용시키는 일은 정말 다르다는 점이다. 거의 3시간을 BFS, DFS에 쏟을 정도로 오래 걸리더라. 남의 코드를 직관적으로 이해하는 능력이 조금 부족해서 공부의 효율이 떨어지는 듯한다. 내가 구현해 본 BF..
https://www.acmicpc.net/problem/1991 1991번: 트리 순회 첫째 줄에는 이진 트리의 노드의 개수 N(1≤N≤26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 영문자 www.acmicpc.net 어젯밤에 이진트리 알고리즘 구현 공부를 하다 자서, 감이 올라왔을 때 한 문제라도 풀어보는 게 좋을 것 같아 트리 알고리즘 중에 가장 쉬운 난이도를 골랐다. 확실히 구현 자체와 문제 풀이 간의 차이는 존재하더라. 노드 클래스와 트리 클래스를 정의해서 긴 호흡으로 끌고 가는 게 당연하다고 생각했는데, 생각보다 풀이는 단순하더라. # PYTHON CODE (1) import sys n = int..
https://www.acmicpc.net/problem/5052 5052번: 전화번호 목록 첫째 줄에 테스트 케이스의 개수 t가 주어진다. (1 ≤ t ≤ 50) 각 테스트 케이스의 첫째 줄에는 전화번호의 수 n이 주어진다. (1 ≤ n ≤ 10000) 다음 n개의 줄에는 목록에 포함되어 있는 전화번호가 www.acmicpc.net 업로드하지 않은 정렬 알고리즘이 생각나서 다시 정렬로 회귀. 이상하게 실제 문제에서는 배운 알고리즘들을 쓸 기회도 없이 sort() 함수를 쓰게 되는 것 같다. 이러다 망각하면 억울할 것 같은데... 5052는 언젠가 프로그래머스에서 마주친 듯한 문제다. 골드4에 랭크되어 있어서 살짝 겁을 먹고 풀었지만, 알고 보니 은근 골드급 문제를 많이 풀어왔더라. 결론적으로 이문제는 ..
https://www.acmicpc.net/problem/1644 1644번: 소수의 연속합 첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 4,000,000) www.acmicpc.net 소수를 구하는 알고리즘은 '에라토스테네스의 체'라는 이름으로 널리 알려져 있다. 밑의 코드에서도 구현하겠지만, 간단한 원리는 소개하는 게 좋을 것 같다. 1. 소수면 True, 아니면 False로 구성된 리스트를 만든다. 2. n ** 0.5 까지 반복문을 돌면서 소수면 그 배수들을 전부 False로 바꾼다. 3. 리스트에서 n까지 반복하며 값이 True인 인덱스를 구한다. 복잡한 듯 싶지만 꽤 간단하며 원리도 직관적이다. 이 문항은 에라토스테네스의 체와 두 포인터가 합쳐진 문젠데, 각각의 개념 자체는 어렵지 않지만..
