전체 글

https://www.acmicpc.net/problem/4963 4963번: 섬의 개수 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다. 둘째 줄부터 h개 줄에는 지도 www.acmicpc.net dfs/bfs로 풀 수 있는 문제인데 특이점은 대각선 방향도 고려해주어야 하는 것이다. 상하좌우 + 대각선 방향 = 총 8가지의 경로를 확인하면 된다. 1) dfs 풀이 import sys sys.setrecursionlimit(10000) def dfs(x, y): dx = [-1, 1, 0, 0, -1, -1, 1, 1] dy = [0, 0, -1, 1, -1, 1, -1, 1] # 8개..

array = [5,3,2,1,4] for i in range(len(array)): min_index = i # 가장 작은 원소의 인덱스 for j in range(i+1, len(array)): if array[min_index] > array[j]: min_index = j array[i], array[min_index] = array[min_index], array[i] print(array) 선택 정렬의 원리: 가장 작은 데이터를 선택하여 앞에 있는 데이터를 바꿔치기 하는 것을 (n-1)번 반복한다. 다음과 같은 배열이 있다고 하자. 현재 맨 앞의 데이터와 배열에서 가장 작은 원소인 1을 교환한다. 1은 이미 정렬된 인덱스 이므로 제외한다.두번째 인덱스 3과 나머지 원소들 중 가장 작은 원소인 ..

https://www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 쉽지않은 계단수 문제였따 .. 여기서 (0-9)는 맨 끝자리수이고 N은 문제에서와 같이 자리수를 뜻한다. 규칙은 이렇게 각 끝자리수의 개수를 대각선 방향 왼쪽 위 + 대각선 방향 오른쪽 위 를 더하면 구할 수 있다. 즉, dp[i][j] = dp[i-1][j-1] + dp[i-1][j+1] 라는 식이 나온다 !!! 끝자리 수가 0, 9일때는 각각 한쪽방향의 대각선에서만 존재하니까 그 수를 그대로 옮겨오면 된다. 위의 그림에서는 파란 선을 참고! 자리수가 1일때 (한자리수)일 때는 직접 초기화를 해주어야 한다. ..

$ git reset --hard

다이나믹 프로그래밍은 전형적으로 보텀업 방식 형태를 보인다. 그렇지만 탑다운 방식과 보텀업 방식의 차이를 알아볼 필요가 있다. 상향식, 하향식에 따라 재귀호출인지 반복호출인지의 차이도 보여지기 때문이다. 1. 탑다운 방식 (Top-down) 재귀 함수를 이용하여 DP를 작성하는 방법. 큰 문제를 해결하기 위해 작은 문제를 호출한다. d = [0] * 100 def fibo(x): print('f(' + str(x) + ')', end=' ') if x == 1 or x == 2: return 1 if d[x] != 0: # 이미 계산한 적 있으면 그대로 값을 반환한다. return d[x] d[x] = fibo(x-1) + fibo(x-2) return d[x] * 실행 결과 f(10)을 구하기 위해서 ..

1. Stack 스택 자료구조 선입후출 (First In Last Out) 구조 stack = [] stack.append(1) # push 를 append()로 구현한다. stack.append(2) stack.append(3) stack.pop() stack.append(4) print(stack) # 스택의 가장 밑에 있는 원소부터 출력 print(stack[::-1]) # 스택 가장 위에 있는 원소부터 출력 [1, 2, 4] [4, 2, 1] 파이썬에서 stack 자료구조를 구현하기 위해서는 이렇게 다른 라이브러리가 필요없이, list 구조에서 append()와 pop()으로 간단히 구현할 수 있다. 2. Queue 큐 자료구조 선입선출 (First In First Out) 구조 , 나중에 온 사..

array = [1,2,3,4,5] print(array) print(array[::-1])

https://www.acmicpc.net/problem/1476 1476번: 날짜 계산 준규가 사는 나라는 우리가 사용하는 연도와 다른 방식을 이용한다. 준규가 사는 나라에서는 수 3개를 이용해서 연도를 나타낸다. 각각의 수는 지구, 태양, 그리고 달을 나타낸다. 지구를 나타 www.acmicpc.net 간단한 구현문제 ! 초기값을 1 1 1 이라고 가정하고 우리가 구하고자 하는 준규네 나라의 날짜와 같은 e s m이 나올때 까지 하나씩 더해가면서 값을 비교한다 e, s, m = map(int, input().split()) a, b, c = 1, 1, 1 # 초기값 count = 1 while True: if a == e and b == s and c == m: print(count) break if..