어제보다 한걸음 더

누구나 자료 구조와 알고리즘 | 제이 웬그로우 - 교보문고 누구나 자료 구조와 알고리즘 | product.kyobobook.co.kr 이번 장에서는 여러가지 상황에서 빅 오 표기법을 사용해 시간 복잡도를 계산하는 방법을 알려준다. 상황 1 : 짝수의 평균 문제: 배열에서 모든 짝수의 평균을 반환할 때의 빅 오 표기법을 사용해 시간 복잡도를 구한다. 평균 = 짝수의 합 / 짝수의 개수 메서드로 전달 된 수 배열 == 데이터 원소 N (N은 배열의 크기) 짝수의 합, 짝수의 개수를 담을 변수를 각각 만든다. (2) 루프를 돌면서 원소를 순회한다. (N) 짝수라면 짝수의 합에 더한다 (N) 짝수의 개수를 늘린다. (N) 짝수의 평균을 구하기 위해 나누기를 수행한다. (1) 2.에서 최악의 경우 배열의 모든 ..

누구나 자료 구조와 알고리즘 | 제이 웬그로우 - 교보문고 누구나 자료 구조와 알고리즘 | product.kyobobook.co.kr 사담 정리하는 습관을 들이고자 책을 읽고 내용을 정리하는 스터디를 시작하게 되었다. 이전까지의 내용은 시간이 되면 다시 정리하기로 하고, 지금부터 읽은 내용들부터라도 차근차근 정리하려고 한다. 정리 이전 장(챕터)까지 버블 정렬, 선택 정렬에 대한 알고리즘 효율성을 알아봤다. 두 정렬 알고리즘 모두 최악의 경우에 O(N^2)를 가지지만, 선택 정렬의 경우는 O(N^2 / 2)를 가지므로 약간 더 빠르다는 사실을 알 수 있었다. (하지만 빅오 표기법에서는 상수를 제거하므로 선택 정렬도 최악의 경우 O(N^2)가 정확한 표기법이기는 하다) 이번 장(챕터)에서는 삽입 정렬까지 ..

문제: https://www.acmicpc.net/problem/14499 14499번: 주사위 굴리기 첫째 줄에 지도의 세로 크기 N, 가로 크기 M (1 ≤ N, M ≤ 20), 주사위를 놓은 곳의 좌표 x, y(0 ≤ x ≤ N-1, 0 ≤ y ≤ M-1), 그리고 명령의 개수 K (1 ≤ K ≤ 1,000)가 주어진다. 둘째 줄부터 N개의 줄에 지 www.acmicpc.net 알고리즘 유형은 구현 문제로, 문제 자체가 어렵진 않았지만 코드로 정리하는데에는 오래 걸렸다. 처음 제출한 코드가 조금 아쉬워서 다른 사람이 봐도 이해하기 쉽도록 리팩토링을 진행했다. import sys input = sys.stdin.readline # (지도의)세로, 가로, (주사위의)x, y, 명령어 개수 N, M, x..

문제: https://www.acmicpc.net/problem/4485 4485번: 녹색 옷 입은 애가 젤다지? 젤다의 전설 게임에서 화폐의 단위는 루피(rupee)다. 그런데 간혹 '도둑루피'라 불리는 검정색 루피도 존재하는데, 이걸 획득하면 오히려 소지한 루피가 감소하게 된다! 젤다의 전설 시리즈의 주 www.acmicpc.net 요새 젤다의 전설 왕국의 눈물 재밌게 하고 있는데 이런 문제가 있어서 냉큼 풀어보게 되었다.ㅎㅎ 이 문제는 BFS나 다익스트라(테이크스트라)로 풀 수 있는데, 다익스트라에 익숙하지 않아서 처음에는 BFS와 섞어서 문제를 풀게 되었다. # 첫번째 제출 코드 import sys from collections import deque input = sys.stdin.readlin..

14235번: 크리스마스 선물 크리스마스에는 산타가 착한 아이들에게 선물을 나눠준다. 올해도 산타는 선물을 나눠주기 위해 많은 노력을 하고 있는데, 전세계를 돌아댕기며 착한 아이들에게 선물을 나눠줄 것이다. 하지만 www.acmicpc.net 문제: https://www.acmicpc.net/problem/14235 알고리즘 분류는 자료구조, 우선순위 큐 였다. 문제에서는 Max-heap 정렬을 요구했지만, 파이썬에서 제공하는 모듈인 heapq를 사용할 경우에 정렬은 min-heap 이었다. 때문에 heapq에 선물을 저장 할 때에는 양수인 우선순위를 음수로 바꿔 min-heap으로 정렬되게 하고, 꺼낼 때는 음수를 다시 양수로 변환해서 출력해줬다. 파이썬에서는 음수 -> 양수로 바꿀 때 그저 하이픈(-..

13335번: 트럭 입력 데이터는 표준입력을 사용한다. 입력은 두 줄로 이루어진다. 입력의 첫 번째 줄에는 세 개의 정수 n (1 ≤ n ≤ 1,000) , w (1 ≤ w ≤ 100) and L (10 ≤ L ≤ 1,000)이 주어지는데, n은 다리를 건너는 트 www.acmicpc.net 문제: https://www.acmicpc.net/problem/13335 import sys # queue 보다 사용 가능한 메서드가 더 많은 deque를 사용했다. from collections import deque input_line = sys.stdin.readline n, w, L = list(map(int, input_line().rstrip().split())) trucks = deque(list(ma..

1244번: 스위치 켜고 끄기 첫째 줄에는 스위치 개수가 주어진다. 스위치 개수는 100 이하인 양의 정수이다. 둘째 줄에는 각 스위치의 상태가 주어진다. 켜져 있으면 1, 꺼져있으면 0이라고 표시하고 사이에 빈칸이 하나씩 www.acmicpc.net 문제: https://www.acmicpc.net/problem/1244 import sys # 실패 # 20개 단위로 끊어서 출력하는 요구사항 파악을 못하는 실수가 있었다. def switch_switch(switches, i): if switches[i] == 0: switches[i] = 1 elif switches[i] == 1: switches[i] = 0 def male_switch_control(switches, receive_n, switch..

1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 문제: https://www.acmicpc.net/problem/1149 import sys n = int(sys.stdin.readline().rstrip()) dp = [[0]*3 for _ in range(n+1)] for i in range(1, n+1): R_0, G_1, B_2 = list(map(int, sys.stdin.readline().rstrip().split())) dp[i][0] = R_0 + min(dp[i-1][1..

2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 문제: https://www.acmicpc.net/problem/2579 # 실패 # 1. 점화식 수정 # 2. 작은 수를 넣었을 때 dp와 stairs 생성이 불가, 런타임 에러가 나서 수정 n = int(input()) dp = [0] * n # stairs = [] # for i in range(0, n): # stairs.append(int(input())) stairs = [int(input()) for _ in range(n)] if n

1063번: 킹 8*8크기의 체스판에 왕이 하나 있다. 킹의 현재 위치가 주어진다. 체스판에서 말의 위치는 다음과 같이 주어진다. 알파벳 하나와 숫자 하나로 이루어져 있는데, 알파벳은 열을 상징하고, 숫자는 www.acmicpc.net 문제: https://www.acmicpc.net/problem/1063 # 1063번 킹 import sys def position_calculate(position, moves): column_index = column.index(position[0]) + move_calculate_column(moves) row_index = row.index(position[1]) + move_calculate_row(moves) if (0