본문 바로가기
반응형

알고리즘39

[알고리즘/백준] 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.
[알고리즘/백준] 1584번 게임 Python 파이썬 이번 문제는 이해하는데 어려웠던 문제였습니다. 세준이가 0,0 에서 500, 500 으로 이동할 때 잃는 생명의 최솟 값을 구하는 문제로 BFS를 적용해서 풀었습니다. 풀면서 고려해야하는 점은 사방면 이동, 위험과 죽음 영역이 겹쳤을 때 처리 방법, 최솟값을 구해야한다는 점입니다. BFS로 풀다가 계속 오류나서 풀이를 보고 깨달음을 얻었습니다. 먼저, 다음과 같은 코드로 통과하였습니다. import sys from collections import deque input = sys.stdin.readline map_list = [[0]*501 for _ in range(501)] dx = [1,-1,0,0] dy = [0,0,1,-1] danger = [] death = [] def update_map(x.. 2023. 3. 21.
[알고리즘/백준] 2012번 등수 매기기 Python 파이썬 이번 게임은 쉽게 풀 수 있음에도 어렵게 생각해 헤매었던 문제였습니다. 각 사람의 예상 등수가 주어지고 임의로 등수를 지정했을 때 그 차이의 합을 최소로 하는 프로그램을 작성하는 문제였습니다. 처음에 문제를 풀이할때는 일단 등수 별로 넣어주고 동점자여서 들어가지 못한 점수들을 배치해줄려고 했는데 최솟값이라고 하니 이때 어떻게 최소 차이 등수랑 매칭해줄지(양방향 검사가 필요해짐) 머리가 복잡해졌습니다. 풀다보니 뭔가 이렇게 푸는게 아닌 것 같아 결국 다른 분들의 풀이를 찾아보았고 그리디 알고리즘에 대해 알 수 있었습니다. 그리디 알고리즘이란? 미래를 생각하지 않고 각 단계에서 가장 최선의 선택을 하는 기법입니다. 사실 위의 알고리즘을 어떻게 활용하면 좋을지 백프로 이해되지는 않지만 이를 통해 생각해보면 각.. 2023. 3. 19.
반응형

티스토리툴바