yuns

알고리즘 문제 해결 전략 Chap5 수학적 귀납법과 반복문 불변식 수학적 귀납법 반복적인 구조를 갖는 명제들을 증명하는 데 유용하게 사용되는 증명 기법 단계 나누기 첫 단계 증명 귀납 증명 반복문 불변식 귀납법: 알고리즘의 정당성을 증명할 때 가장 유용하게 사용되는 기법 반복문 불변식(loop invariant) 반복문의 내용이 한 번 실행될 때마다 중간 결과가 우리가 원하는 답으로 가는 길 위에 잘 있는지를 명시하는 조건 불변식을 이용하면 반복문의 정당성을 다음과 같이 증명 반복문 진입시에 불변식이 성립함을 보인다. 반복문 내용이 불변식을 깨뜨리지 않음을 보인다. 반복문 내용이 시작할 때 불변식이 성립했다면 내용이 끝날 때도 불변식이 항상 성립함을 보인다. 반복문 종료시에 불변식이 성립하면 항상 우리가..

알고리즘 문제해결 전략 Chapter 4 개관 알고리즘 어떤 작업이 주어졌을 때 컴퓨터가 이 작업을 해결하는 방법 문제를 해결할 때 한 가지 방법을 명료하게 써 놓아야 함 가능한 한 명료하고 모호한 표현을 써야 함 알고리즘을 평가하는 요소 두가지 요소 시간: 적은 시간을 사용 공간: 적은 공간을 사용 - 더 작은 용량의 메모리를 사용 서로 상충되는 경우가 많기 때문에, 메모리 사용량을 희생해 속도를 높이거나, 속도를 희생해서 메모리 사용량을 줄일 수 있음 알고리즘의 시간 복잡도 분석 속도 비교 방법 직관적으로는 수행 시간 측정하기 but, 수행시간은 사용한 프로그래밍 언어, 하드웨어, 운영체제, 컴파일러 등 수 많은 요소에 의해 바뀔 수 있음 심지어, 어떤 문자열을 구현했는지, 함수인자를 어떻게 넘겼는지..

unordered_map map보다 더 빠른 탐색을 하기 위한 자료구조 해쉬테이블로 구현한 자료구조로 탐색 시간복잡도는 O(1) map는 binary search tree로 탐색 시간 복잡도는 O(logn) #include 중복된 데이터 허용 안함 key가 유사한 데이터가 많을 경우 해시 충돌로 인해 성능 감소 함수 정리 find(key) map에서 key에 해당하는 원소를 찾는 함수 key가 있을 경우, 해당 위치, 아닌 경우, s.end()반환 count(key) key에 해당하는 원소의 개수를 반환 있을 경우 1, 없을 경우 0 insert({key, value}) earse(key) s[key] = value;형태로 선언 가능 [참고] https://math-coding.tistory.com/31

연관컨테이너 노드 기반 컨테이너 균형 이진트리로 구현 set container 연관 컨테이너 중 하나 노드 기반 컨테이너이며 균형 이진트리로 구현되어 있음 key라 불리는 원소들의 집합으로 이루어진 컨테이너 (원소 = key) python에서 순서가 있는 dictionary로 생각하면 되나봄 key값은 중복 허용 안 됨 원소가 insert에 의해 추가되면 자동으로 정렬됨 default는 오름차순! set 사용법 #include set [변수 이름]; set s; set s(pred); pred의 정렬 기준을 가짐 set s2(s1); s1을 복사한 s2 연산자 사용이 가능 s.begin(); 맨 첫번째 원소를 가리키는 반복자를 리턴(참조) s.end(); 맨 마지막 원소를 가리키는 원소의 끝부분을 알 때..

#include #define endl '\n' #define MAXN 16 using namespace std; int arr[MAXN]; int n, cnt; int cmp = (1 sync_with_stdio(false); int T; cin >> T; for(int tc = 1; tc > n; cnt = 0; for(int i = 0; i > str; for(int j = 0; j < str.size(); j++){ val |= 1

이 문제는 예시랑 내가 짠 코드가 정확히 일치하지 않아서 로직이 잘못 된 줄 알고 계속 고민하느라 오랜 시간이 소요됐다. 문제 https://www.acmicpc.net/problem/1379 1379번: 강의실 2 첫째 줄에 강의의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 줄마다 세 개의 정수가 주어지는데, 순서대로 강의 번호, 강의 시작 시간, 강의 종료 시간을 의미한다. 강의 www.acmicpc.net 코드 arr에는 시작 시간 기준으로 sorting을 하고, heapq에는 끝나는 시간 기준으로 우선순위 큐 정렬하기 from heapq import heappush, heappop pq = [] n = int(input()) room = [0] * n a..

https://programmers.co.kr/learn/courses/30/lessons/17684 코딩테스트 연습 - [3차] 압축 TOBEORNOTTOBEORTOBEORNOT [20, 15, 2, 5, 15, 18, 14, 15, 20, 27, 29, 31, 36, 30, 32, 34] programmers.co.kr def solution(msg): dic = {} for i in range(1, 27): dic[chr(64 + i)] = i idx = 27 answer = [] k = 0 while k < len(msg): tmp = msg[k] k += 1 while k < len(msg): tmp += msg[k] k += 1 if tmp not in dic: dic[tmp] = idx id..

문제: https://www.acmicpc.net/problem/20419 입력 r, c = 가로, 세로 길이 k = 0, 1(0이면 주문서 없음, 1이면 주문서 있음) 아이디어 k = 0 일때는 도착 할 수 있는지 간단하게 확인하기 k = 1일 때는, visited의 크기를 r x c x 4와 같이 정의 한 뒤, 마지막의 위치를 k라 할 때, ( 0: 한 개도 안 씀, 1: 오른쪽 하나 씀, 2: 왼쪽 하나 씀, 3: 왼, 오른 다 씀 ) 오른쪽을 한 번도 안 쓸 경우, 해당 값을 queue에 넣기 왼쪽을 한번도 안 쓸 경우, 해당 값을 queue에 넣기 code from collections import deque r, c, k = map(int, input().split()) dxy = [[-1, ..