본문 바로가기

Algorithm144

0520_백준 17142번 : 연구소 3 / BFS 알고리즘/ Python [문제 접근] - BFS(너비우선탐색)으로 최단 시간 구하는 문제(바이러스가 확산되며 1씩 증가하는 형태) - itertools 모듈에서 chain 불러오기, list(sum(arr, [ ])) 보다 list(chain(*arr))이 속도는 더 빠름. - 처음에는 바이러스 위치를 정하는 조합을 함수로 구현하려다가 실패한 후, 결국 itertools 모듈 콤비네이션을 활용함 - deepcopy로 배열을 똑같이 만들어도 되나, 이번 코드에서는 새로운 배열을 하나 만들었다. - 문법체크✔ ① print(min(res) if res else -1) : res에 값이 있으면 (True) ->min(res) 출력, 값이 없다면(False) -> -1 출력 ② 2차원 배열 1차원 리스트로 합치기 : list(sum(.. 2020. 5. 20.
0519_백준 15683번: 감시 / 브루트 포스 알고리즘 [문제 접근] - 모든 경우의 수를 대입해보는 브루트 포스(Brute Force) 알고리즘 문제. - dfs로 완전탐색하는 코드 구현, 효율이 굉장히 낮아 pypy로 제출하여 통과함. - cctv 종류마다 탐색할 수 있는 모든 방향을 리스트에 담아 확인함. - 모든 경우의 수에서 탐색하며 감시가 가능한 영역을 표시하고 사각지대의 최소값을 확인해야 하기 때문에, deepcopy 배열을 활용함. [코드 구현] from copy import deepcopy import sys # 감시 가능 영역 표시하기 -> 영역 표시는 copy 배열에 def office(x, y, temp, d): for i in d: nx, ny = x, y while True: nx += dx[i] ny += dy[i] if 0 2020. 5. 19.
0518_백준 11403번 : 경로찾기 / 플로이드-워셜 알고리즘 [문제 풀이] 이번 경로찾기 문제는 전형적인 DFS문제이다. 처음 예제를 확인할 때는 주어진 정점 간의 연결 상태를 파악하는 게 다소 이해가 안 갔는데, '플로이드-워셜 알고리즘'을 통해 간단하게 문제를 해결할 수 있었다. 플로이드-워셜 알고리즘(Floyd-Warshall Algorithm)은 그래프에서 가능한 모든 노드 쌍에 대해 최단 거리를 구하는 알고리즘이다. 임의의 노드 s에서 e까지 가는 데 걸리는 최단거리를 구하기 위해, s와 e 사이의 노드인 m에 대해 s에서 m까지 가는 데 걸리는 최단거리와 m에서 e까지 가는 데 걸리는 최단거리를 이용한다. (출처_나무위키https://namu.wiki/w/%ED%94%8C%EB%A1%9C%EC%9D%B4%EB%93%9C-%EC%9B%8C%EC%85%9C.. 2020. 5. 18.
0515_알고리즘 백트래킹(Backtracking) 정리 그 동안 문제 풀면서 자주 들었던 말.. "이거 백트래킹으로 풀면 돼^^" 찾아야 하는 경우의 수를 줄이는 것은 알았지만, 정확히 어떤 식으로 해결하는 지는 몰랐는데 드디어 오늘 SSAFY 라이브 강의에서 백트래킹 개념을 배웠다. [개념 정리] 백트래킹을 내 식대로 정리하자면, 가장 기본적으로는 '해를 찾는 것'이다. 근데 해를 어떻게 찾느냐 하면, 깊이우선탐색(DFS)와 비슷하게 풀이된다. 이때 다른 점은 깊이우선탐색은 가능한 모든 경우의 수를 탐색하는 것이고, 백트래킹은 조건에 만족한 노드만을 찾아 탐색하다가 해를 찾으면 탐색을 멈추기 때문에 결과적으로 훨씬 적은 경우의 수를 탐색하게 된다. (물론 그렇지 않을 때도 있다.) 즉, 기본적인 뼈대는 DFS지만 만족해야 하는 조건을 넣어주어 탐색하는 경우.. 2020. 5. 15.
0514_백준 14890번/경사로_파이썬 "가로 세로 모두 확인해야 함, zip으로 전치행렬 활용" 새로 써본 것은 ziiiiiiip! [풀이 과정] - 특별한 알고리즘 없이 주어진 조건을 빠짐없이 고려하여 푸는 문제 - 가로행, 세로열 두번 탐색해야 해서 -> zip 함수 활용 zip(*iterable)은 동일한 개수로 이루어진 자료형을 묶어 주는 역할을 하는 함수 - 내가 고려한 조건들은 아래와 같다. ① 경사로를 놓는 방법을 크게 '높은 곳에서 낮은 곳으로 향하는 것', '낮은 곳에서 높은 곳으로 향하는 것' 두 가지로 나눔. 그리고 경사 높이 차이를 비교 -> 1차이가 나는지 확인 ② 범위를 벗어나지 않게 인덱스 위치 확인 ③ 경사로를 놓았는지 확인해주기 위해 visit 배열 활용 - 한 행, 한 열씩 돌아가며 길이 되는지 확인하는데 이.. 2020. 5. 14.
0513_백준 14891번/ 톱니바퀴_파이썬 "deque 모델의 rotate 메소드 사용하기" [문제 접근] - 처음에는 주어진 톱니바퀴 번호에 따라 분기처리 하여 하드코딩 했다가, 중간에 실패했다. 이유는 톱니바퀴 4개가 한번에 돌아야 하는데 내가 구현한 코드는 순차적으로 돌아가다 중간에 끊겨서 제대로 된 결과를 얻기 힘들었다. - 타 블로거님들의 코드를 참고하여 다시 풀었는데, collections 모듈의 deque(double ended queue)의 rotate 메소드를 활용했다. - rotate의 기본적인 구조 : rotate(n) 요소 n의 값에 따라 음수면 n만큼 왼쪽 회전, 양수면 n만큼 오른쪽 회전(시계방향) - 시작 톱니를 잡아 ①12시 방향을 기준으로 2번, 6번에 위치한 톱니의 극(1 또는 0) 정보와 ② 회전방향(시계 또는 .. 2020. 5. 13.

티스토리툴바