봉보로봉봉

선택(Selection) 문제 입력 : n개의 값과 k (1 어떤 알고리즘도 최소 일정 횟수만큼 비교를 해야한다. 상한과 하한이 같다면 최소한의 비교 횟수로 원하는 값을 찾을 수 있다는 뜻이다. -> 완전히 풀림 k = 1, n : 최대값, 최소값 찾기 - 왼쪽에서부터 하나씩 비교하면 2n - 3 n - 1 번 비교 -> 최대값 n - 2 번 비교 -> 최소값 - 토너먼트 방식으로 비교하면 3/2n - 2 -> 상한, 하한 n - 1 번 비교 -> 최대값 토너먼트 1차전에서 탈락한 n / 2에서 비교를 해 (n / 2) - 1 번 비교 -> 최소값 k = 1, 2 : 제일 작은 값, 두번째로 작은 값 - 왼쪽에서부터 하나씩 비교하면 2n - 3 최소값 -> n - 1 번 비교 두번째로 작은 값 -> n ..

프로그램을 측정할 때 - 하드웨어와 소프트웨어 환경이 상이 - 다양한 크기의 입력이 존재 이런 것들에 영향을 받지 않고 객관적으로 알고리즘이 어느 정도 성능을 보이는지 측정하고 비교하는 방법을 필요로 하게 되었다. 객관적인 측정을 위해 가상컴퓨터(RAM) + 가상언어 + 가상코드의 조건에서 성능을 측정한다. 가상컴퓨터(RAM) 기본 연산이 1단위 시간내에 수행된다고 정의한 가상의 컴퓨터 기본연산 배정연산, 대입연산, 복사연산 : a = b 산술연산 : +, -, *, /, % 등 비교연산 : =, ==, != 논리연산 : and, or, not 비트연산 : bit별 and, or, not 가상언어 가상컴퓨터 위에서 돌아가는 언어, 아래와 같은 사항을 만족하는 가상의 언어 기본연산을 표현할 수 있어야한다...

자료구조 - 자료(data)를 가지고 저장공간(memory)을 연산(읽기, 쓰기, 삽입, 삭제, 탐색)으로 구성된 형태(구조) - 자료를 담는 구조 - 사용하는 연산에 따라서 다양한 자료구조가 존재함 알고리즘 - 입력을 유한한 횟수의 연산들을 반복해서 정답을 출력하는 것 - 자료구조에 담긴 데이터들을 가공해서, 다양한 연산을 통해서 원하는 정답을 출력하는 것 인류 최초의 알고리즘 최대공약수(GCD) 계산 알고리즘

알고리즘을 풀 때 자주 최대공약수가 필요한 경우가 생겼다. 최대공약수를 사용해 풀었던 문제 프로그래머스 레벨 0 / 분수의 덧셈 프로그래머스 레벨 0 / 유한소수 판별하기 프로그래머스 레벨 1 / 최대공약수와 최소공배수 여러 번 최대공약수를 구해야 하는 문제를 풀었는데도 매번 기억이 안 나서 까먹을 때마다 보려고 기록해 둔다. 최대공약수 유클리드 호제법 최대공약수는 유클리드 호제법을 이용하면 구할 수 있다. 두 개의 숫자가 있을 때 x를 y로 나누었을 때 나머지(r)가 0이면 y는 이 두 수의 최소공배수가 된다. 나머지가 0이 될 때까지 값을 앞으로 당겨가며 계속 반복하면 된다. while문을 사용해서 표현했을 때 최소공배수가 구해진 시점(r이 0일때)에 y가 r이 되면 0이 되므로 종료된다. 하지만 그..