SWEA 5247 연산 (그래프) (파이썬)
2022. 9. 28. 20:09
SWEA
https://swexpertacademy.com/main/learn/course/lectureProblemViewer.do SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 풀이 및 해설(주석) from collections import deque # bfs탐색 def solve(num): global rst # print(nums) Q = deque() # Q에는 현재 숫자와 카운트 해줄 숫자를 튜플로 넣어줌 Q.append((num, 0)) # 현재 숫자 방문 체크 visit.add(num) while Q: now, cnt = Q.popleft() if now == M: rst = min(rst, cnt) ..
SWEA 1865 동철이의 일 분배 (파이썬)
2022. 9. 27. 16:58
SWEA
https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5LuHfqDz8DFAXc SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 풀이 및 해설(주석) # sums는 지금까지의 확률 더한거 def solve(index, sums): global rst # rst 갱신점 if index == N: rst = max(rst, sums) return # 간단한 가지치기 if sums
SWEA 5208 전기버스2 (파이썬)
2022. 9. 27. 16:08
SWEA
https://swexpertacademy.com/main/learn/course/lectureProblemViewer.do SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 아이디어 전기 배터리를 가스라고 부르겠음 가스가 있는 경우와 없는 경우로 나누어서 재귀함수를 만든다. 함수에 넘겨줄 매개변수는 index==정류장번호, cnt==가스 넣는 개수, gas==gas양 풀이 및 해설(주석) def solve(index, cnt, gas): global rst gas -= 1 if index >= (N-1): rst = min(rst, cnt) return if cnt >= rst: return #가스가 있는 경우..
SWEA 5209 최소 생산 비용 (파이썬)
2022. 9. 27. 16:04
SWEA
https://swexpertacademy.com/main/talk/solvingTalk/boardCommuView.do?commuId=AWrmdCqqQeYDFARG SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 풀이 및 해설(주석) def solve(depth, sums): global rst # depth가 N이 되면 return if depth == N: rst = min(rst, sums) return # 가지치기 if sums >= rst: return # visit체크 확인 하고 안갔으면 ㄱㄱ # 같은 행과 열을 가지지않음 for i in range(N): if visit[i]: continue v..
N-Queen
2022. 9. 27. 12:27
알고리즘 개념
제약 조건 같은 행에 두지 못한다. 같은 열에 두지 못한다. 대각에 두지 못한다. 행과 열의 정보를 저장할 1차원 리스트를 만든다. 리스트의 인덱스는 행번호, 요소는 열번호 대각에 있는지 확인 여부는 행값의 차이와 열값의 차이가 같으면 대각에 있다. 또는, 대각에 있는지를 기록해 놓는 방법도 있다. N*N 배열에서 대각선은 2N-1개 있다. (r, c)의 좌표가 어느 대각의 줄에 있는지 알면 된다. r + c 를 해보면 구별이 된다. 대략 2N개 정도의 크기를 가지는 1차원 리스트를 만들어 대각의 방문 체크를 한다. 반대의 대각은 r - c를 하면 구별할 수 있다. -(N-1) ~ (N-1)까지의 숫자가 나온다. 여기서 r-c+(N-1)을 해준다. 이 대각의 방문표시를 해줄 리스트를 2N정도로 만들어 준..
분할정복 병합정렬 (파이썬)
2022. 9. 26. 19:34
알고리즘 개념
병합 정렬 병합 정렬은 여러 개의 정렬된 자료의 집합을 병합하여 한 개의 정렬된 집합으로 만드는 방식 분할 정복 알고리즘을 활용 시간복잡도 O(nlogn) 분할 작업 병합 작업 파이썬 코드 from collections import deque; import sys; sys.stdin = open('input_분할정복_백트래킹.txt', 'r') def merge_sort(lst): global cnt if len(lst) == 1: return lst # 왼쪽과 오른쪽을 나눔 mid = len(lst)//2 left = lst[:mid] right = lst[mid:] # 왼쪽 부분과 오른쪽 부분을 재귀 l = merge_sort(left) r = merge_sort(right) # 병합 과정 rst는 ..
백준 1654 랜선 자르기 (이진 탐색) (파이썬)
2022. 9. 25. 18:43
백준
풀이 및 해설(주석) import sys def solve(start, end): # 탈출 조건 if end - start = N return solve(mid, end) K, N = map(int, sys.stdin.readline().strip(' ').split()) cable = [int(sys.stdin.readline().strip(' ')) for _ in range(K)] max_cable = max(cable) print(solve(1, max_cable+1))
백준 2108 통계학 Counter 사용 (파이썬)
2022. 9. 25. 17:36
백준
아이디어 최빈값 구하는게 중요할 것 같다. 각 숫자의 개수를 구하기 위해 Counter 를 사용해야 겠다는 생각이 들었다. 풀이 from collections import Counter from heapq import nsmallest N = int(input()) nums = [] for _ in range(N): nums.append(int(input())) print(round(sum(nums)/N)) nums.sort() print(nums[N//2]) counter = Counter(nums) conut_num = counter.most_common() if len(conut_num) > 1: if conut_num[0][1] == conut_num[1][1]: print(conut_num[1]..