반응형 알고리즘23 [백준] 14888번: 연산자 끼워넣기 Python (DFS, BFS) | LIM 이 문제의 경우는 순서대로 연산자에 상관없이 계산해야하기 때문에 연산자를 하나씩 뽑아서 즉, popleft를 사용하여 구현해야 한다고 생각했다. 즉 BFS를 사용하여 문제를 해결하였다. 1. 숫자는 순서의 바뀌지 않고 연산자의 순서만 바뀌기 때문에 연산자의 조합이 어떻게 올 지 부터 먼저 구해야 한다. (조합은 permutation을 이용하여 구했다. 다만, permutation의 경우 ['+','+','+','+']의 경우 모두 다르게 인식하여 경우의 수를 많이 만들기 때문에 set을 사용하여 조합을 unique한 상태로 변경해야 한다.) 2. 연산자의 특성 중 나눗셈 부분이 기존 나눗셈의 개념과는 다르기 때문에 나같은 경우 함수로 사칙연산을 구현해주었다. (생각보다 시간이 오래 걸리지 않았다..) 3.. 2021. 9. 12. [백준] 18405번: 경쟁적 전염 Python (DFS, BFS) | LIM 이 문제는 BFS를 이용하여 풀었다. 생각보다 이 문제는 간단하게 풀 수 있었다. 먼저, 바이러스가 존재하는 위치와 그 위치에 바이러스 값을 저장했다. 또한, 바이러스 숫자가 작을수록 우선수위를 갖기 때문에 바이러스 숫자가 작은 순서대로 sorting 해주었다. popleft()를 통해 앞에 있는 것(바이러스 숫자가 작은것)부터 뽑아내며 상하좌우로 퍼지게 하였다. 퍼지게 한 후 바이러스가 전염된 부분의 바이러스 값과 인덱스를 기존 virusIndex에다가 뒤로 저장하였다. 맨 처음에 순서대로 sorting 해주었기 때문에 추후에 저장되는 바이러스 값은 자동으로 정렬이 되어 있다. 기존에 있던 바이러스가 모두 popleft()를 통해 사라지고 그 바이러스를 통해 전염된 바이러스와 인덱스만 남게 되면 시간을.. 2021. 8. 31. [백준] 14502번: 연구소 Python (DFS, BFS) | LIM DFS와 BFS에 관련하여 설명은 너무 많기에 내가 기억하고 싶은 것만 정리하고자 한다. DFS - Depth-First Search(깊이 우선 탐색) 즉, 깊은 부분부터 탐색하겠다는 이야기이다. 깊은 부분부터 탐색한다는 말이 사실 잘 이해가 되지 않기에 그냥 DFS는 스택을 사용한다로 외웠다. DFS는 스택을 이용하는 알고리즘이기 때문에 실제 구현은 재귀함수를 이용했을 때 매우 간결하게 구현할 수 있다. 스택은 박스 쌓기에 비유할 수 있다. 박스를 쌓다가 아래에 있는 박스를 치우기 위해서는 위에 박스부터 먼저 치워야 한다. 이러한 구조를 선입후출, 후입선출 구조라고 한다. 그냥 먼저 들어온게 나중에 나간다고 생각하면 쉽다. 왜냐하면 쌓기 때문이다. DFS가 동작하는 과정은 다음과 같다. 1. 탐색 시작.. 2021. 8. 31. 동적계획법(DP) 동적계획법은 큰 문제를 작은 문제로 나누어 푸는 문제를 일컫습니다. 동적계획법이 어떤 부분에서 동적으로 프로그래밍이 이루어진다는 말은 아닙니다. 동적계획법은 입력 크기가 작은 부분 문제들을 모두 해결한 후에 그 해들을 이용하여 보다 큰 크기의 부분 문제들을 해결하여, 최종적으로 원래 주어진 입력의 문제를 해결하는 것입니다. 동적계획법의 조건은 이러합니다. 1. 작은 문제가 반복하여 일어나는 경우(중복이 있는 경우) 2. 같은 문제는 구할 때마다 정답이 같은 경우 이러한 위와 같은 조건을 만족하는 경우에만 동적 프로그래밍을 사용할 수 있습니다. 작은 문제의 결과 값이 항상 같다는 점을 이용해서 큰 문제를 해결하는 방법입니다. 이와 같은 특성을 이용하여 한 번 계산한 작은 문제를 저장해놓고 다시 사용을 할 .. 2021. 2. 9. 프로그래머스-스킬트리(부제 : For-else문에 대하여) 코딩테스트를 풀고 난 후 다른 사람의 풀이를 보는데 평소처럼 if~else를 쓴 것이 아닌 for~else를 쓴 구문을 보고 들여쓰기를 잘못했다고 생각했으나 나의 착각이었다. 파이썬에서는 else가 for문과도 함께 쓰이기도 한다. for문을 사용하다보면, 루프 중간에 break문으로 빠져나오는 경우들이 있는데, break문이 걸려서 빠져나가는 지 아닌지를 판단이 필요한 경우가 있다. 즉, for~else문은 "for문에서 break가 발생하지 않았을 경우"의 동작을 else문에 적어준다고 보면 된다 이 때 else의 사용으로 간단하게 해결할 수 있습니다. for-else의 사용 예시 data=[1,2,3,4,12,5] test=0 for num in data: if num > 10: test=1 bre.. 2021. 1. 17. 이전 1 2 3 4 다음 반응형
