Python_알고리즘
-
[Python] 백준 2798 블랙잭Python_알고리즘 2021. 8. 6. 23:04
문제 바로가기 문제분석 # n개의 카드 중에서 3장을 골라 그 값의 합이 딜러가 외친 m과 같거나 가장 근접한 값을 찾아야 한다. # 3장을 골라 조합해야하므로 삼중 반복문으로 풀이한다. 문제풀이 n, m = map(int, input().split()) cards = list(map(int, input().split())) sum = [] # 각 조합으로 더한 값들을 저장 for i in range(n): for j in range(i+1, n): for k in range(j+1, n): card_sum = cards[i] + cards[j] + cards[k] if card_sum
-
[Python] 백준 1002 터렛Python_알고리즘 2021. 8. 6. 00:56
문제 바로가기 문제분석 # 두 점에서 각각 적까지의 거리가 주어지므로 두개의 원을 만들 수 있다. # 이 때, 두 원의 교점이 적의 위치가 되기 때문에 교점의 개수가 답이 된다. # 네가지 케이스로 나눠서 풀이한다. 거리가 0이 아니라면 두 원의 중심 사이의 거리를 반지름의 합, 차와 비교한다.(거리가 0일 경우라면 두 원이 일치하므로 무한대 경우의 수가 나온다.) 거리가 반지름의 합과 같다면 두 원이 밖에서 만나게되고(원이 외접하는 것), 차와 갑다면 한 원 안의 다른 원이 한 점에서 만난다(원이 내접하는 것). 거리가 반지름의 합보다 작고 차보다 크면, 두 점에서 만난다. 나머지 경우는 서로 만나지 않는 경우다. 문제풀이 T = int(input()) for i in range(T): x1, y1, ..
-
[Python] 백준 2579 계단 오르기Python_알고리즘 2021. 8. 5. 00:41
문제 바로가기 문제분석 # 규칙 # 1. 계단은 한번에 한계단 또는 두계단씩 오를 수 있다. # 2. 한계단을 밟으면서 다음계단 또는 2계단으로 오를 수 있다. # 3. 연속된 세계의 계단을 밟을 수 없다(시작점 제외) # 4. 첫째, 마지막 계단은 반드시 밟아야 한다. # 규칙 풀이 # 1번째 계단은 무조건 올라가므로 1번째 계단의 합을 구한다. # 문제의 조건에서 3칸을 연속해서 올라갈 수 없으므로, # 자신의 위치(계단) 점수 + 1칸 밑의 점수 + 3칸 밑의 점수의 합과, # 자신의 위치 점수 + 2칸 밑의 점수 중 높은 것을 택하여 리스트에 저장한다 # 1번째 계단, 2번째 계단, 3번째 계단을 미리 구한 후, for문을 통해 마지막계단까지 구한다. 문제풀이 N = int(input()) dp ..
-
[Python] 백준 9663 N-QueenPython_알고리즘 2021. 8. 4. 00:47
문제 바로가기 문제분석 # N개의 퀸이 N X N 크기의 체스판에 놓여야 하므로, 퀸들이 각 행마다 반드시 1개씩 존재해야 하고 따라서 행, 즉, 좌우는 확인할 필요가 없다. # 확인해야 할 남은 방향은 열기준인 상, 하와 대각선 열의 경우 길이가 N인 1차원 배열을 만들어 체크 대각선의 경우, 퀸을 기준으로 ↗, ↙ 이 두 가지 방향은 현재 인덱스의 합이 해당 대각선 방향 각각의 인덱스의 합들과 같다는 규칙이 있었음 # 따라서 길이가 N * 2 -1인 1차원 배열로 체크 가능 # 나머지 ↖, ↘ 이 두 방향의 경우도 똑같은 원리로 인덱스 제어 변수가 i, j라고 쳤을 때 i-j+N-1이라는 규칙이 성립 문제풀이 import sys input = sys.stdin.readline def dfs(i): g..
-
[Python] 백준 15650 N과 M (2)Python_알고리즘 2021. 8. 3. 01:47
문제 바로가기 문제분석 # 백트래킹 = DFS(재귀) + 가지치기(break or continue) # 모든 경우의 수를 탐색하면서 break나 continue로 가지치기를 해 경우의 수를 줄이는 방법 # 순열 공식 : nPr = n!/(n-r)! # 조합 공식 : nCr = nPr/r! 문제풀이 from itertools import combinations N, M = map(int, input().split()) arr = [i for i in range(1, N+1)] answer = list(combinations(arr, M)) for element in answer: for element2 in element: print(element2, end=" ") print() # 자연수 n, m을 입..
-
[Python] 백준 2108 통계학Python_알고리즘 2021. 7. 31. 00:41
문제 바로가기 문제분석 # 산술평균 : N개의 수들의 합을 N으로 나눈 값 # 중앙값 : N개의 수들을 증가하는 순서로 나열했을 경우 그 중앙에 위치하는 값 # 최빈값 : N개의 수들 중 가장 많이 나타나는 값 # 범위 : N개의 수들 중 최댓값과 최솟값의 차이 문제풀이 import sys input = sys.stdin.readline n = int(input()) num = [] # [1, 3, 8, -2, 2] for _ in range(n): num.append(int(input())) # 산술평균 print(round(sum(num) // n)) # 중앙값 num.sort() print(num[n//2]) # 최빈값 from collections import Counter mc = Counter..
-
[Python] 백준 1260 DFS와 BFSPython_알고리즘 2021. 7. 30. 00:53
문제 바로가기 문제분석 # DFS(Depth First Search) 깊이우선탐색 최상위 노드부터 하위 노드까지 한 길만 깊게 탐색하고 다시 위로 올라가서 다른 노드를 깊게 탐색 # BFS(Breadth First Search) 너비우선탐색 최상위 노드부터 다음 차수를 모두 탐색하고, 그 다음 차수를 모두 탐색하는 방법 문제풀이 # Depth First Search def dfs(n): print(n, end=' ') visited[n] = True for i in graph[n]: if not visited[i]: dfs(i) # Breadth First Search def bfs(n): visited[n] = True queue = deque([n]) while queue: v = queue.popl..
-
[Python] 백준 1874 스택 수열Python_알고리즘 2021. 7. 27. 00:08
문제 바로가기 문제분석 # 스택은 자료를 넣는(push) 입구와 자료를 뽑는(pop) 입구가 같아 제일 나중에 들어간 자료가 제일 먼저 나온다. (LIFO, Last in First out) # 스택에 push하는 순서는 반드시 오름차순이다. # 임의의 수열이 주어졌을 때 스택을 이용해 그 수열을 만들 수 있는지 없는지, 있다면 어떤 순서로 push와 pop 연산을 수행해야 하는지를 알아낼 수 있다. 이를 계산하는 프로그램을 작성하라. # 스택에 넣었다가 뽑아 늘어 놓는것은 pop으로 뽑아낸 순서가 입력값 순이라는 뜻. # push하는 순서는 오름차순이므로 가장 작은 수에서부터 큰 수로 진행된다. # 스택을 이용해 해당 수열을 만들 수 없을때는 no를 출력한다. 입력값에 따른 출력값 example 1 2..