본문 바로가기
  • 살짝 구운 김 유나

분류 전체보기146

퀵 정렬 퀵 정렬 : 주어진 배열을 두 개로 분할하고, 각각을 정렬한다 병합 정렬과의 차이점 1. 퀵 정렬은 분할 시에 pivot item을 중심으로, 이보다 작은 것은 왼편, 큰 것은 오른편에 위치시킨다. 2. 각 부분 정렬이 끝난 후, 병합 정렬은 병합하는 과정이 필요하나 퀵 정렬은 후처리가 필요하지 않다. 아이디어 - pivot보다 큰 값은 오른쪽, 작은 값들은 왼쪽 집합에 위치하도록 한다. - 피봇을 두 집합의 가운데에 위치시킨다. 구현 def partition(l, r): # 피봇을 A[l]로 설정 pivot = A[l] i, j = l, r # i, j가 교차하면 i, j는 피봇을 기준으로 작은 값과 큰 값들의 경계에 위치 while i 2022. 9. 26.
병합 정렬 병합 정렬 : 여러 개의 정렬된 자료의 집합을 병합하여 한 개의 정렬된 집합으로 만드는 방식 * 분할 정복 알고리즘 사용 - 자료를 최소 단위의 문제까지 나눈 후에 차례대로 정렬하여 최종 결과를 얻어냄 - top-down 시간 복잡도 >> O(nlogn) 구현 arr = [69, 10, 30, 2, 16, 8, 31, 22] # 병합하는 과정 def merge(llst, rlst): result = [] lp = rp = 0 # 오른쪽, 왼쪽 리스트의 원소를 차례대로 비교하면서 작은 순으로 새로운 배열에 담기 while lp < len(llst) and rp < len(rlst): if llst[lp] < rlst[rp]: result.append(llst[lp]) lp += 1 else: result... 2022. 9. 26.
SWEA_1267_작업순서 SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 코드 import sys sys.stdin = open('1267_input.txt', 'r') def bfs(v): Q = [] Q.append(v) visited[v] = 1 res.append(v) while Q : v = Q.pop(0) for t in G[v]: check = 1 for p in P[t]: if not visited[p]: check = 0 break # 앞선 작업을 다 수행한 상황이면 다음 노드로 if check and visited[t] == 0: Q.append(t) visited[t] = 1 res.append(t) for test.. 2022. 9. 25.
SWEA_2832_미생물격리 SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 해결방법 1. 모든 미생물들이 움직인 이후에 두개 이상의 군집이 모이는 곳을 확인해야 한다. -> 방향이 잘 못 결정될 수 있기 때문 -> 추가로 선언한 3차원 배열에 저장하면서 진행하고 모든 미생물이 움직인 후에 하나의 군집으로 다시 생성 2. 한 시간이 지날 때 마다 미생물들의 정보를 새롭게 갱신해주어야 한다. 3차원 배열 선언 posiLst = [[[] for _ in range(N)] for _ in range(N)] 한줄 if - else cells[i][3] = cells[i][3] - 1 if cells[i][3] % 2 == 0 else cells[.. 2022. 9. 23.
SWEA_1247_최적경로 SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 문제 삼성전자의 서비스 기사인 김대리는 회사에서 출발하여 냉장고 배달을 위해 N명의 고객을 방문하고 자신의 집에 돌아가려한다. 회사와 집의 위치, 그리고 각 고객의 위치는 이차원 정수 좌표 (x, y)로 주어지고 (0 ≤ x ≤ 100, 0 ≤ y ≤ 100) 두 위치 (x1, y1)와 (x2, y2) 사이의 거리는 |x1-x2| + |y1-y2|으로 계산된다. 여기서 |x|는 x의 절대값을 의미하며 |3| = |-3| = 3이다. 회사의 좌표, 집의 좌표, 고객들의 좌표는 모두 다르다. 회사에서 출발하여 N명의 고객을 모두 방문하고 집으로 돌아오는 경로 중 가장.. 2022. 9. 22.
SWEA_5188_최소합, SWEA_5189_전자카트 둘다 재귀로 완전탐색..! SWEA_5188_최소합 문제 그림처럼 NxN 칸에 숫자가 적힌 판이 주어지고, 각 칸에서는 오른쪽이나 아래로만 이동할 수 있다. 맨 왼쪽 위에서 오른쪽 아래까지 이동할 때, 지나는 칸에 써진 숫자의 합계가 최소가 되도록 움직였다면 이때의 합계가 얼마인지 출력하는 프로그램을 만드시오. 1 2 3 2 3 4 3 4 5 그림의 경우 1, 2, 3, 4, 5순으로 움직이고 최소합계는 15가 된다. 가능한 모든 경로에 대해 합을 계산한 다음 최소값을 찾아도 된다. 입력 첫 줄에 테스트케이스의 수 T가 주어진다. 1 2022. 9. 22.
조합 조합 : 서로 다른 n개의 원소 중 r개를 순서 없이 골라낸 것 조합의 수식 1. 반복문을 통한 조합 생성 # 0, 1, 2, 3, 4 중 3개의 숫자 조합 만들기 N = 5 for i in range(N-2): for j in range(i+1, N-1): for k in range(j+1, N): print(i, j, k) ''' 0 1 2 0 1 3 0 1 4 0 2 3 0 2 4 0 3 4 1 2 3 1 2 4 1 3 4 2 3 4 ''' 2. 재귀 호출을 이용한 조합 생성 def nCr(n, r, s): if r == 0: print(*comb) else: # s -> 선택할 수 있는 구간의 시작 # s부터 마지막 데이터 중 선택할거야 for i in range(s, n-r+1): comb[r-.. 2022. 9. 21.
순열과 부분집합 순열 : 서로 다른 것들 중 몇개를 뽑아서 한 줄로 나열하는 것 1. 단순하게 순열을 생성하는 방법 : {1, 2, 3} 을 포함하는 모든 순열을 생성하는 함수 >> 루프를 통한 순열 for i in range(1, 4): for j in range(1, 4): if i != j: for k in range(1, 4): if i != k and j != k: print(i, j, k) ''' 1 2 3 1 3 2 2 1 3 2 3 1 3 1 2 3 2 1 ''' 2. 최소 변경을 통한 방법 : 각각의 순열들은 이전의 상태에서 단지 두 개의 요소들 교환을 통해 생성 >> 재귀 호출을 통한 순열 def f(i, k): # 깊이가 k이면 리턴 if i == k: print(p) else: for j in ra.. 2022. 9. 21.
SWEA_4615_재미있는오셀로게임, SWEA_2117_홈방범서비스 SWEA_4615_재미있는오셀로게임 재미 한탱이도 없음 SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 문제 오셀로라는 게임은 흑돌과 백돌을 가진 사람이 번갈아가며 보드에 돌을 놓아서 최종적으로 보드에 자신의 돌이 많은 사람이 이기는 게임이다. 보드는 4x4, 6x6, 8x8(가로, 세로 길이) 크기를 사용한다. 6x6 보드에서 게임을 할 때, 처음에 플레이어는 다음과 같이 돌을 놓고 시작한다(B : 흑돌, W : 백돌). 4x4, 8x8 보드에서도 동일하게 정가운데에 아래와 같이 배치하고 시작한다. 그리고 흑, 백이 번갈아가며 돌을 놓는다. 처음엔 흑부터 시작하는데 이 때 흑이 돌을 놓을 수 있는 곳은 다음과.. 2022. 9. 16.
SWEA_1248_공통조상, SWEA_11315_오목판정 SWEA_1248_공통조상 SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 문제 이진 트리에서 임의의 두 정점의 가장 가까운 공통 조상을 찾고, 그 정점을 루트로 하는 서브 트리의 크기를 알아내는 프로그램을 작성하라. 예를 들어, 위의 이진 트리에서 정점 8과 13의 공통 조상은 정점 3과 1 두 개가 있다. 이 중 8, 13에 가장 가까운 것은 정점 3이고, 정점 3을 루트로 하는 서브 트리의 크기(서브 트리에 포함된 정점의 수)는 8이다. 입력 가장 첫 번째 줄에 테스트케이스의 수가 주어진다. 각 케이스의 첫 번째 줄에는 정점의 개수 V(10 ≤ V ≤ 10000)와 간선의 개수 E, 공통 조상을 찾는 두 .. 2022. 9. 15.

티스토리툴바