전체 글92 [python] 1003. 피보나치 함수 문제 출처 1003. 피보나치 함수 풀이 피보나치를 재귀로 짰을때 0과 1이 리턴되는 횟수를 구하는 문제이다. 이 문제를 처음에는 재귀로 풀었는데 시간 복잡도 O(2^N)으로 시간 초과가 났다. 시간을 줄이기 위해 재귀가 아닌 for문을 이용해 이 전에 계산한 결과를 저장해 다음 결과를 도출하는 DP로 풀었더니 시간복잡도가 O(N)이 나왔다. 재귀 코드(시간초과) def fib(n): global zero, one if n == 0: zero += 1 return 0 elif n == 1: one += 1 return 1 else: return fib(n-1) + fib(n-2) tc = int(input()) for _ in range(tc): n = int(input()) zero, one = 0, .. 2019. 6. 30. [python] 17086. 아기 상어2 문제 출처 17086. 아기 상어 풀이 상어가 위치한 곳으로부터 가장 먼 곳의 거리를 구하는 문제이다. 특정 포인트로 부터 BFS로 8가지 방향으로 탐색했을때 가장 늦게 상어를 만나는 지점을 구하면 된다. 모든 배열을 탐색하며 상어가 존재하지 않는 빈 칸들의 위치를 배열(vacancies)에 담는다. 최대 안전거리를 구할 변수 max_를 초기화한다. vacancies로 while문을 돌리며 매번 요소 하나를 뽑아 빈 칸으로부터 상어가 존재하는 곳까지의 경로를 담을 큐(q) 배열에 넣는다. 상어가 존재하는 곳까지 BFS 탐색을 할때 방문한 곳을 표시할 배열(check)를 만들어 초기화한다. 탐색을 시작하는 초기 위치정보 q에서 뽑아 d, y, x 변수에 선언한다. 다음 좌표에 해당하는 위치정보를 q에 담을.. 2019. 6. 29. [python] 16236. 아기 상어 문제 출처 16236. 아기 상어 풀이 아기 상어가 물고기를 먹으며 이동하는 최단거리를 구하는 문제이다. 아기 상어는 다음과 같은 조건을 만족하는 경우에만 물고기를 먹을 수 있다. 자신의 크기보다 작거나 같은 물고기가 있는 칸만 지나갈 수 있다. 자신의 크기보다 작은 물고기만 먹을 수 있다. 먹을 수 있는 물고기가 1마리보다 많다면, 거리가 가장 가까운 물고기를 먹으러 간다. (거리는 아기 상어가 있는 칸에서 물고기가 있는 칸으로 이동할 때, 지나야하는 칸의 개수의 최솟값이다.) 거리가 가까운 물고기가 많다면, 가장 위에 있는 물고기, 그러한 물고기가 여러마리라면, 가장 왼쪽에 있는 물고기를 먹는다. 위 조건을 모두 만족하는 최단거리는 우선순위를 고려한 정렬 알고리즘을 통해 구할 수 있다. 하지만 pyt.. 2019. 6. 29. [python] 10825. 국영수 문제 출처 10825. 국영수 풀이 사용자 정의 정렬은 .sort() 함수를 써서 문제를 간단히 해결할 수 있다. 국어점수 내림차순 영어점수 오름차순 수학점수 내림차순 이름의 아스키코드 오름차순 N = int(input()) students = [input().split() for _ in range(N)] students.sort(key=lambda x: (-int(x[1]), int(x[2]), -int(x[3]), x[0])) for stu in students: print(stu[0]) 2019. 6. 29. 이전 1 ··· 19 20 21 22 23 다음
