whatisworth 님의 블로그 whatisworth 님의 블로그

https://www.acmicpc.net/problem/2573이 문제는 그래프 탐색 문제로, 문제에서 설명하는대로 착실하게 구현만 하면 되는?(그게 어렵지만,,)문제라고 할 수 있다. 빙산이 분리가 되는지 탐색하는 것은 bfs를 통해 구현하였고, 1년 후 빙산의 상태는 이중 for문으로 구현하였다. 중요한 점은 방문 그래프가 반복문을 실행할 때마다 초기화 되어야 한다는 것이다. import sys from collections import dequeread = sys.stdin.readline N, M = map(int, read().split())graph = []for _ in range(N):    graph.append(list(map(int, read().split())))# 상하좌우 dx ..

https://www.acmicpc.net/problem/14891빡구현으로 유명한 삼성 기출문제이다. 꼼꼼하지 못한 나는 언제 이런 문제를 빠르게 풀 수 있을까,, 한숨이 나왔지만 어쨌든 정진하기로...ㅠㅜㅠ이 문제의 특징은 톱니바퀴의 회전을 양옆으로 전파 시켜야 한다는 것이다. 나는 처음에 각 톱니바퀴의 순서에 따라 회전하는 방향을 모두 지정하려고 했었는데, 굳이 그럴 필요가 없었다. import sys read = sys.stdin.readline cogwheel_state = []for _ in range(4):    cogwheel_state.append(list(map(int,read().rstrip())))K = int(input())turns = []for _ in range(K):    ..

https://www.acmicpc.net/problem/2667이 문제는 DFS와 BFS모두 풀이가 가능한 문제이다.나는 BFS로 풀었는데, 사실 BFS는 구현하기가 어렵진 않았지만, 잊어버린 부분이 몇가지 있다. 방문 리스트를 초기화할때, visited = [[False] * N] * N이런식으로 하게되면, visited 배열의 모든 행이 같은 리스트 객체를 참조하도록 만들기 때문에, 나중에 방문처리를 하게 될때, 한 행의 값을 수정하면, 모든 행의 값이 동시에 변경된다. visited = [[False for _ in range(N)] for _ in range(N)] 이렇게 초기화 해야한다!또 주의해야할 부분은 bfs(0,0)만 하게 되면 단지 하나만 탐색하고 끝나버리는데, 이를 방지하기 위하여 ..

https://www.acmicpc.net/problem/1697이번 문제도 어제와 마찬가지로 그래프 탐색 문제이다. 나는 항상 코딩테스트 문제를 잘 풀기 위해서는 이 문제를 어떤 알고리즘을 사용하여 풀어야할지 고민해봐야한다고 생각하는데, 이문제는 최단경로 라는 단어에서 힌트를 준것 같았다. DFS는 깊이 우선탐색으로, 특정한 경로를 원할 때 주로 사용한다고 보면되고, BFS는탐색을 현재 노드와 가까운 노드부터 순서대로 진행합니다.큐를 사용하며, 먼저 들어온 노드부터 처리됩니다.특징: BFS는 모든 경로를 동일한 깊이(거리)로 탐색하므로, 특정 노드에 처음 도달한 순간이 곧 최단 경로임이 보장됩니다. 라는 특징 때문에 이 문제에 사용할 수 있다고 생각하였다. 처음에는 node를 print하면 최단경로가 ..

https://www.acmicpc.net/problem/1260 99클럽 1주차는 이분탐색이나 투포인터 문제를 풀었다면, 2주차의 문제 주제는 그래프 탐색인 것 같다. 이번 문제는 DFS와 BFS의 개념을 확실히 알 수 있는 문제이다. 먼저 그래프는 두가지 형태로 입력받을 수 있는데, 인접행렬과 인접리스트 형태이다. 인접행렬과 인접리스트의 차이는 다음과 같다. 예를 들어 다음과 같은 그래프가 있다고 가정해볼 때, 인접행렬과 인접리스트는 다음과 같이 입력될 수 있다. 1. 인접행렬 : 각 노드가 연결되어 있는지 아닌지를 0혹은 1로 나타낸 행렬이다. (모든 노드에 대한 연결정보를 저장하므로, 공간메모리가 소모되서 잘 안쓰이는 것 같다.)2. 인접리스트 : 각 연결 정보를 중첩리스트를 활용하여 나타낸 것이..

https://www.acmicpc.net/problem/2470 이 문제는 투포인터 문제이다! 이분탐색과 상당히 비슷해보이지만, 다른 점이 있는데, 이분탐색이 중간점(mid)를 타겟 값과 계속해서 비교해 나가면서 범위를 좁혀나가는 방식이라면, 투포인터 문제는 말 그대로 움직이는 포인터(start, end)가 두개이다! 즉, 양 끝단에서 두 포인터를 움직여가면서 조건에 만족하는 답을 찾아내는 방식이라고 할 수 있다.이 문제는 정렬된 용액의 특성값 리스트에서 두 포인터가 만날 때까지 현재 용액의 특성값의 합과 이전 용액의 특성값의 합의 크기를 비교해 나가면서 현재 용액의 특성값의 부호가 달라지는 조건에 따라 포인터를 움직이는 방식으로 풀었다. import sys read = sys.stdin.readlin..

https://www.acmicpc.net/problem/11663해당 문제는 앞선 두 문제와 마찬가지로 이분탐색 문제이다! 문제를 보자마자 이분탐색인 것을 깨달았던 것이, 어떤 값이 어떤 리스트에서 어떤 위치를 차지하는지? 에 대한 문제였기 때문에 바로 알아차릴 수 있었다. 처음 풀이는 공간 메모리 초과 오류가 떴는데, 그 이유는 주어진 선분의 처음과 끝을 for문으로 길게 늘린다음 해당 점이 그 안에 포함되어 있는지 이분탐색으로 찾았기 때문이였다. import sys read = sys.stdin.readline N, M = map(int, read().split())coord = list(map(int, read().split()))lines = []for _ in range(M):    lines..

https://www.acmicpc.net/problem/1654 백준에서 이분탐색의 두번째 문제로 랜선자르기 문제를 풀어보았다. 이전에 암기왕에서 이분탐색 알고리즘을 그대로 사용했다면, 이번 문제는 실버2 단계의 문제인 만큼 조금의 응용이 필요했다. 기본 이분탐색 알고리즘이 정렬된 리스트에서 찾고자 하는 숫자의 인덱스 정보를 이분법으로 나누어 찾았다면, 이번 문제는 start, end의 값을 랜선의 길이로 바꾸어주어야 했다...!  import sys read = sys.stdin.readline K, N = map(int, read().split())lans = []for _ in range(K):    lans.append(int(read()))def binary_search(data):    st..