남민우의 공부 블로그

순차 탐색의 최악의 경우 시간 복잡도는T(n) = n 으로 나타내고 이는 빅-오 표기법으로 O(n) 으로 나타낸다. 이진 탐색의 최악의 경우 시간 복잡도는T(n) = Log2N + 1 로 나타내고 이는 빅-오 표기법으로 O(LogN) 으로 나타낸다. 둘을 비교하기 위해선 n에 증가량에 따른 연산 횟수를 살펴봐야 하는데단순 계산만 보더라도순차 탐색의 연산횟수보다 이진 탐색의 연산 횟수가 극단적으로 적다는 것을 알 수 있다 특히 이진 탐색의 연산 횟수는 n의 값이 증가함에 따라 그 상승폭이 점점 더 줄어드는 모습으로이는 사용하기 좋은, 매우 뛰어난 알고리즘이다 라고 결론 내릴 수 있다.

프로그래밍 및 언어/자료구조 학습 2024. 10. 19. 01:21

넥토리얼 : 당신의 즐거움이 이어지도록https://www.nexon-tutorial.com/10월 12일부터 13일에 진행된 넥슨 채용 연계형 신입 모집 공고, 일명 '넥토리얼'그 넥토리얼에 관한 설명회 '채용의 나라' 에 다녀왔다.나는 프로그래밍 직군 희망자로 12일에 사전 신청을 통해 현장을 방문하였다. 첫 일정은 10시 30분부터 시작에, 입장 시작은 10시부터 진행하는 일정이었지만 시작부터 많은 인원이 대기하고 있었다.현장에는 사전 신청을 하지 못하고 현장에 방문한 사람들을 위해 입장 등록 가능한 QR 코드까지 준비되어 있었다.이번년도에 졸업을 앞둔 4학년 학생으로서, 채용의 나라에는 처음 참관하는 자리었다.넥슨이 대기업이라는 사실은 너무나 당연하게도 알고 있었지만 대중성이 높은 게임들이 많아 ..

개인 일상 2024. 10. 18. 21:15

문자 데이터를 바꾸고, Group by 절까지 같이 사용하는 실습을 진행한다.1. 서울 지역 음식 타입 별 평균 음식 주문 금액 구하기출력 : '서울', '타입', '평균 금액' 키워드는1. 서울 지역2. 음식 타입3. 평균 주문 금액 (Avg)로 볼 수 있다. SELECT SUBSTR(addr, 1, 2) '지역', cuisine_type, AVG(price) '평균 금액' FROM food_orders foWHERE addr like '%서울%'GROUP by 1,2 //GROUP by SUBSTR(addr, 1, 2), cuisine_type 와 같은 의미 2. 이메일 도메인 별 고객 수와 평균 연령 구하기키워드는1. 이메일 도메인2. 고객 수 (Count)3. 평균 연령 (Avg)로 볼 수 있다...

내일배움캠프 학습/SQL 2024. 10. 18. 18:08

1. 특정 문자를 다른 문자로 바꾸기 : Replaceselect restaurant_name "원래 상점명", replace(restaurant_name, 'Blue', 'Pink') "바뀐 상점명"from food_orderswhere restaurant_name like '%Blue Ribbon%' Replace예제 코드에서의 활용은"restaurant_name 컬럼에서 'blue' 를 모두 'pink' 로 바꿔라"로 동작한다.  이전 이름에서 blue 가 모두 pink 로 바뀐 것을 확인할 수 있다. 사용 방법은 다음과 같다replace (바꿀 컬럼, 현재 값, 바꿀 값) 예제 코드SELECT addr "이전 주소", REPLACE(addr, '문곡리', '문가리') "바뀐 주소"FRO..

내일배움캠프 학습/SQL 2024. 10. 18. 17:58

문제1. 음식 종류 별 가장 높은 주문 금액과 가장 낮은 주문 금액 조회2. 가장 낮은 주문 금액 순으로 내림차순 정렬 풀이가장 높은 주문 금액 (max) 와 가장 낮은 주문 금액 (min) 을 조회하되,'음식 종류 별' 이라는 그룹이 묶였다 (group by) 이후 이 조회된 결과를 가장 낮은 금액 순으로 내림차순 (order by ~ desc) 정렬한다 코드SELECT cuisine_type, max(price) as '최대 주문 금액', min(price) as '최소 주문 금액'FROM food_orders fo group by cuisine_typeorder by min(price) DESC 설명먼저select *from food_orders fo를 검색해 food_orders 의 컬럼들을 확인..

내일배움캠프 학습/SQL 2024. 10. 18. 16:35

이전 #5의 마지막 문단, +1을 생략하는 이유에 이어서 진행된다. 빅-오 표기법T(n) 의 수식에서 실제로 영향력을 끼치는 부분을 '빅-오(Big-Oh)' 라고 부른다.이 영향력을 끼치는 부분만 표기하는 방법이다. 이전 +1 을 생략하는 질문을 다르게 생각해서+1 이 너무 작은 수치라 생략하는 거라면 +100, +500 과 같이 숫자가 커져도 똑같이 생략하는거냐?라는 질문을 던질 수 있다. 이 대답을 하기에 앞서, 시간 복잡도 함수를 보는데 있어서 그 관점이 어디에 있냐 를 먼저 판단해야 한다.그 관점이 어딘가 하면 항상 가정하는 최악의 경우, 즉 데이터 표본이 셀 수 없을 많을 때 이다. 데이터 표본이 너무 많아서, 예를 들어 10만, 100만의 데이터 중 원하는 값을 찾는다고 할 때과연 +100, ..

프로그래밍 및 언어/자료구조 학습 2024. 10. 18. 03:34

시간 복잡도를 구하기 위해, 당연하게도 함수를 먼저 구해서 그래프를 그려야 한다....while(first 이 기본 골격에서 핵심 연산은 " == " 연산이다.이전 순차 탐색 알고리즘에서 봤던 것과 동일하게 다른 연산자, 추가로 if / else 문 의 시행 또한 == 연산자에 의존한다. 따라서 == 연산자의 연산 횟수를 기준으로 시간 복잡도를 결정할 수 있다. 탐색 대상은 ( n => n/2 => n/4 .... ) 으로 절반씩 줄어들면서 진행된다. : 언제까지? 탐색 대상이 1개가 될 때까지 : 그래서 몇번이냐? 모른다! => 객관적 성능 비교가 불가능하다. 해서 이 탐색 대상이 1개가 될 때까지 총 몇번을 시행해야 하는지 정확한 수식을 세울 필요가 있다. 이 추론 과정을 통해 T(n) = K + 1..

프로그래밍 및 언어/자료구조 학습 2024. 10. 18. 03:17

이진 탐색 알고리즘기본적으로 이차원으로 정렬된 배열에서 탐색하는 알고리즘이다.순차 탐색 알고리즘보다 좋은 성능을 보이지만 배열이 정렬되어 있어야 한다는 제약이 있다.이때 정렬은 반드시 오름차순/내림차순 이어야 한다 가 아니라 정해진 기준이 있으면 상관없다. 이러한 배열이 있다고 할 때 3 이라는 값을 찾는 알고리즘을 설계한다고 해보자. 이진 탐색 알고리즘의 기본 골격은 다음과 같다.1. 처음 인덱스 + 끝 인덱스 값을 더한다2. 그 값을 2로 나눈다.3. 해당 결과값을 인덱스로 하여 배열의 값을 탐색한다. 이 골격을 가지고 순서를 다시 생각해본다면1. 처음 인덱스 : 0 / 끝 인덱스 : 8 => 82. 8 / 2 = 43. arr[4] = 9의 과정을 거치게 된다. 만약 여기서 arr[4] 가 우리가 ..

프로그래밍 및 언어/자료구조 학습 2024. 10. 18. 02:27