안토니 블로그 안토니 블로그

알고리즘 문제를 풀때 어떤 자료구조를 사용해야하는가? python snake = [] snake.append((1,3)) snake.append((1,2)) snake.append((1,1)) (1,3) (1,2) (1,1) => (1,4) (1,3) (1,2) 1. 단일 객체에 대한 표현 - Point : 간단하기 때문에 굳이 자료구조를 사용하지 않음. 2. 단일 객체에 대한 표현 - Array 1. 탐색 : O(N) 2. 삽입 : O(N) but 맨 뒤 삽입은 O(1) 3. 삭제 : O(N) but 맨 뒤 삭제는 O(1) 4. 값 조회 : O(1) - 머리 추가 : O(N) - 뱀 옮기기 : O(N) 3. 단일 객체에 대한 표현 - LinkedList 참고로 파이썬에선 링크드리스트가 없어 deque로..

파이썬에서 2차원 이상의 리스트를 초기화할땐 list = [[0]*n for _ in range(n)] 와 같이 해야한다. list = [[0]*n]*n 처럼 초기화를 할 경우 n개의 [0]*n이 모두 같은 객체를 가리키기 때문이다. ex) n = 4 # case 1 list_1 = [[0]*n]*n print(list_1) list_1[2][3] += 1 print(list_1) """ [[0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0]] [[0, 0, 0, 1], [0, 0, 0, 1], [0, 0, 0, 1], [0, 0, 0, 1]] """ # case 2 list_2 = [[0]*n for _ in range(n)] print(list_2) lis..

# case 1 - for문과 append를 이용해 만든 리스트 numbers = [] for i in range(1,11): numbers.append(i) print(numbers) output [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] # case 2 - list comprehension을 이용해 만든 리스트 numbers2 = [i for i in range(1,11)] print(numbers2) output [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] # case 3 - 조건문이 추가된 list comprehension numbers3 = [i for i in range(1,11) if i%2 == 1] print(numbers3) output [1, 3, 5, 7,..

1. 먼저 가장 적은 강의실을 사용하기 위해선 시작시간과 종료시간이 빠른 수업을 먼저 배치한다. 따라서 시작시간이 빠른 순서대로, 시작 시간이 같다면 종료시간이 빠른 순서대로 정렬을 해야한다. 2. 수업을 강의실에 배치할 때 종료시간이 수업의 시작시간보다 같거나 빠른 경우 같은 강의실에서 강의를 할 수 있다. 3. 수업을 강의실에 배치할 때 종료시간이 수업의 시작시간보다 늦는 경우 새로운 강의실이 필요하다. scd는 n개의 [시작시간, 종료시간]를 가지고 있다. 이 솔루션은 시간초과가 발생하였는데 오답의 원인을 생각해보니 N의 개수가 20만개이기 때문에 O(N^2)의 방법으로는 불가했다. scd가 빌때까지 순회를 하면서 skip(이전 종료시간)보다 현재 노드의 시작시간이 더 빠른 경우를 건너뛰었으며 그렇..

https://www.acmicpc.net/problem/2156 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규 www.acmicpc.net 가장 많은 양의 포도주를 마실 수 있도록 하는 프로그램입니다. 연속으로 3잔은 선택할 수 없다는 조건이 있는데요. 이 조건을 적용해서 3잔을 마시는 경우에 대해서 생각해봅니다. 1 2 3 X O O O X O O O X 가 됩니다. 이를 확장해서 생각해보면.. 앞에서부터 그 항 까지의 합의 최대값을 dp라 할때 ~dp + O + O - (1) ~dp + X + O - (2) ~~~~dp + X - ..

백준 9251번 문제 LCS(최장 공통 부분수열) ACAYKP CAPCAK 와 같이 입력이 주어지면 A C A Y K P C A P C A K => ACAK가 모두의 부분수열이 되는 수열 중 가장 긴 것이 된다. # 9251_LCS.py s1 = input() s2 = input() len_a = len(s1) len_b = len(s2) lcs_list = [[0 for i in range(len_a+1)] for j in range(len_b+1)] count = 0 for i in range(1,len_b+1): for j in range(1,len_a+1): if s2[i-1] == s1[j-1]: lcs_list[i][j] = lcs_list[i-1][j-1] + 1 else: lcs_list[..

■ 알고리즘의 분석 □ 정확성 분석: 모든 입력 사례에 대해서 정확한 해답을 찾는다는 것을 증명 □ 효율성 분석: 입력 크기가 커지는 정도에 따라 성능의 변화량을 증명 - 시간 복잡도: 시간을 기준으로 알고리즘의 효율성 분석 - 공간 복잡도: 공간을 기준으로 알고리즘의 효율성 분석 ■ 알고리즘의 성능 분석 □ 퍼포먼스 측정: 실행 시간을 직접 측정하거나 실행 명령의 숫자 세기 - 컴퓨터의 성능이나 프로그래밍 언어에 따라 달라짐 □ 복잡도 분석: 컴퓨터나 프로그래밍 언어와 무관하게 성능 분석 - 입력 크기에 따른 단위 연산의 실행 횟수 세기 ■ 복잡도 분석 □ 입력 크기: 문제가 가진 파라미터, 즉, 입력 사례의 크기 □ 단위 연산: 알고리즘 실행의 기본이 되는 명령어들의 집합 ■ 알고리즘의 시간 비교 □..

알고리즘 공부를 하다보니 예전 자료구조 내용도 다까먹었고 기본적인 부분이 부족한 것 같아 인강을 보기 시작했어요 백준 인강 들으려고 했었는데 무료강의가 찾아보니 있더라구요 https://www.inflearn.com/course/%ED%8C%8C%EC%9D%B4%EC%8D%AC-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EA%B8%B0%EC%B4%88#curriculum [무료] 파이썬으로 배우는 알고리즘 기초 - 인프런 | 강의 Pseudo 코드로 설명하는 알고리즘 강의에 지치셨나요? 실행 가능한 Python 소스 코드로 알고리즘의 기초를 다져봅시다!, 알고리즘 학습, 파이썬 코딩으로 장벽을 낮춰보세요! 파이썬으로 배우는 www.inflearn.com 무료라고 하니 한번 들어보..