Algorithm/Baekjoon52 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. 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. 0512_백준/14499번/주사위 굴리기_파이썬 [문제 접근 방법] - 특별한 알고리즘이 있지 않고, 주어진 상황을 코드로 구현하는 문제였다. - 기본적인 로직은 주어진 명령의 방향에 따라 주사위의 면을 바꿔주는 것이다. - 기타 조건으로는 배열의 인덱스 에러 여부를 확인해주는 것 그리고 지도 위의 이동 칸이 0인지 아닌 지에 따라 주사위면과 이동칸의 숫자를 바꿔주는 로직을 넣어줘야 했다. - 주어진 상황을 빠짐 없이 조건으로 넣어주면 풀 수 있는 문제 [피드백] - 주사위의 윗면과 아랫면이 정해져 있는데, 처음에 문제를 잘못 읽어서 아랫면이 1이라고 착각했었다. - 주사위의 면을 방향에 따라 어떻게 바꿔줄지를 많이 고민했지만, 결국 하드 코딩으로 작성했다. [코드 구현] n, m, x, y, k = map(int, input().split()) ar.. 2020. 5. 12. 이전 1 ··· 5 6 7 8 9 다음
