반응형 백준36 [알고리즘/백준] 1922번 네트워크 연결 Python 파이썬 이번 문제는 어려워서 풀이만 하는데도 1시간 넘게 걸린 문제였습니다. 모든 컴퓨터가 연결했을 때 최소 비용을 구하는 문제로 처음 문제를 보고 생각한 풀이 방법은 가중치가 적은 순으로 나열해연결할까 생각했는데 그 경우 어떻게 모든 컴퓨터가 연결되었는지 확인 방법이 생각 안났습니다. 그래서 두번째는 한 점을 잡아서 작은 가중치로 타고 타고 연결할까 했지만 그 경우 최소값을 구할 수 없다는 점이 있었습니다. 결국 머리 싸매다가 다른 분의 풀이를 찾아봤고 새로운 알고리즘에 대해 알게 되었습니다. (대개 문제가 안 풀리면 기존에 알고 있는 알고리즘으로는 안 풀리는 거 같습니다ㅠㅠ) 이번에 알게된 알고리즘은 "최소 스패닝 트리"하는 알고리즘으로 이해하는데는 해당 블로그(https://www.crocus.co.kr/.. 2023. 3. 29. [알고리즘/백준] 1915번 가장 큰 정사각형 Python 파이썬 이번 문제는 시간복잡도를 고려한 문제 DP 알고리즘이 필요한 문제였습니다. 배열이 주어졌을 때 최대 정사각형 넓이 구하는 문제로 단순하게 생각하면 반복문을 통해 검사해서 답을 구할 수 있지만 이 경우 시간초과가 날 수 있습니다. 이를 방지하기 위해서는 DP 알고리즘을 사용하여 시간 복잡도를 줄어야 통과가 될 수 있습니다. 아래와 같은 코드로 통과하였습니다. import sys input = sys.stdin.readline n, m = map(int, input().split()) map_list = [] dp = [[0]*m for _ in range(n)] for i in range(n): map_list.append(list(map(int, input().rstrip()))) answer = 0 f.. 2023. 3. 27. [알고리즘/백준] 1753번 최단경로 Python 파이썬 이번 문제는 처음으로 heap 을 사용해보고 푸는데 애 먹었던 문제였습니다. 문제는 보기에 간단해보입니다. 시작점이 주어졌을때 각 정점의 최소 경로 거리를 구해서 출력하는 문제입니다. 저는 처음에 탐색 문제로 판단하고 BFS를 통해서 풀려고 접근했습니다 풀다가 너무 복잡해진게 틀린 거 같아서 다른 분의 풀이를 찾아보니 다들 heap을 사용하시더라고요 그래서 왜 heap을 사용해서 푸는 가? 의문이 생겼는데 해당 블로그 https://my-coding-notes.tistory.com/200 이해할 수 있었습니다. 간단히 말하면 효율성 때문에 heap을 써주는 것이었습니다. heap의 특징으로는 최소값을 먼저 pop 해주는데 이를 통해서 최소 경로를 구하는데 계산을 단축할 수 있게 됩니다. 아래와 같은 코드.. 2023. 3. 26. [알고리즘/백준] 2072번 오목 Python 파이썬 한동안 문제가 어려워서 직접 풀지 못하고 풀이를 참고한 경우가 많아서 글을 못 올렸네요... 오래만에 스스로 풀 수 있는 문제가 나와서 좋았습니다. 이번 문제는 문제로 많이 등장하는 오목 문제입니다. 문제가 길어서 중간에 생략하고 시작과 끝만 첨부합니다. 문제를 요약하면 돌 좌표가 흑, 백 번갈아가면서 놓여질 때 오목이 되는지 안되는지 확인해서 만약에 오목이 된다면 해당 돌 번째를 출력하는 문제입니다. 주의할 부분은 승패가 갈리지 않은 경우 -1를 해주고 놓았을 때 오목(=5)이 아닌 6 등 그 이상이 된다면 오목으로 안치고 그대로 게임을 이어간다는 점입니다. 저 같은 경우 문제를 보고 dfs 로 풀어야겠다고 생각하고 풀었습니다. 다만 다 풀고 나서 생각해보니 dfs보다는 bfs 방식이 좀 더 코드 줄을.. 2023. 3. 25. 이전 1 2 3 4 5 6 ··· 9 다음 반응형
