본문 바로가기

분류 전체보기

 (108)
[python] Maximum Subarray Problem 분할 정복 문제 Kadane 알고리즘 ,Brute Force 알고리즘으로 해결하기 Maximum Subarray Problem   Maximum Contiguous Subsequence은 가장 큰 연속적인 배열의 합을 구하는 문제이다. 예를 들어 다음과 같은 14개의 정수가 주어졌을 때,  [4, -6, 0, 2, 3, -4, 1, 3, 0, -9, 4, 1, -3, 2] 이 배열에서 가장 큰 합을 가지는 연속적인 서브 배열은 [2, 4], [2, 7], [2, 8], [3, 4], [3, 7], [3, 8], [10, 11] 등으로 최대합은 5이다. 문제 마다 요구하는 출력조건은 다르지만, 이번에는 구간 시작 정수가 0이 아니고 index가 가장 작은 경우만 출력하고  만약 시작 index가 가장 작은 경우가 여러개라면 그중에서 가장 짧은 구간을 가지는 구간을 출력하도록 하겠다.  ..
[SQL 코테준비] 가격이 제일 비싼 식품의 정보 출력하기, 잡은 물고기 중 가장 큰 물고기의 길이 구하기 프로그래머스 | 가격이 제일 비싼 식품의 정보 출력하기https://school.programmers.co.kr/learn/courses/30/lessons/131115 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 해결 방법 : 가격을 기준으로 내림 차순 정렬을 한다. 제일 값이 비싼 상위의 한가지만 출력한다.  SELECT PRODUCT_ID, PRODUCT_NAME, PRODUCT_CD, CATEGORY, PRICEFROM FOOD_PRODUCTORDER BY PRICE DESCLIMIT 1  | 잡은 물고기 중 가장 큰 물고기의 길이 구하기 https://scho..
[python] Quick Sorting 퀵 정렬 Hoare(호어), Lomuto(로무토) 분할 정복을 사용한 정렬 알고리즘 Quick Sorting 퀵 정렬이란 Charles Antony Richard Hoare가 개발한 정렬 알고리즘으로 다른 원소와의 비교만으로 정렬을 수행하는 분할 정복 알고리즘이다. 평균적으로 다른 정렬알고리즘보다 수행속도가 매우 빠르기 때문에 퀴 정렬이라고 한다. 퀵 정렬의 정렬 과정을 설명하면 다음과 같다. 배열 중에 임의의 데이터를 pivot으로 선택한다.배열에 있는 데이터들을 pivot 보다 작은 데이터 그룹은 왼쪽으로 pivot보다 큰 데이터 그룹은 오른쪽으로 나눈다. pivot을 중심으로 왼쪽과 오른쪽으로 나누어진 두 그룹에 대해 재귀를 통해 위의 과정을 반복한다.quick sort가 반복 호출 되면서 정렬이 완료된다.   퀵 정렬은 Top-down방식으로 구현되며, 평균 시간 복잡도는 O(n..
[MySQL] 프로그래머스 코딩테스트 문제 풀이 SELECT 과일로 만든 아이스크림 고르기, 조건에 부합하는 중고거래 댓글 조회하기 과일로 만든 아이스크림 고르기https://school.programmers.co.kr/learn/courses/30/lessons/133025# 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr SELECT FIRST_HALF.FLAVORFROM FIRST_HALF inner join ICECREAM_INFOon FIRST_HALF.FLAVOR = ICECREAM_INFO.FLAVORWHERE TOTAL_ORDER >=3000 AND INGREDIENT_TYPE = 'fruit_based'order by TOTAL_ORDER desc;  조건에 부합하는 중고..
[분할 정복] 파이썬 트로미노(tromino) 타일링 알고리즘 트로미노(tromino)트로미노(tromino)는 크기가 같은 정사각형 3개를 이어붙여 만든 다각형을 말한다. 트로미노는 아래의 2종류가 있다.우리가 오늘 문제에서 사용할 트로미노는 왼쪽의 계단 형 트로미노이다.    트로미노 타일링 문제를 해결하기 위해서는 분할정복 기법을 사용할 수 있다.  1. 분할정복 (Divide & Conquer)분할 정복은 Recursion 기반의 해결기법이다. 분할정복 기법의 문제 해결 시나리오는 다음과 같다. 분할(Divide) : 주어진 문제를 두 개 혹은 그 이상의 같은 형식의 작은 문제로 나눈다. 정복 (conquer) : 나누어진 작은 문제는 재귀적으로 해결한다. 즉, 나누어진 작은 문제는 더 이상 나누어서 문제를 해결할 필요가 없이 직접 문제를 해결할 수 있을 때..
[python]파이썬 나이트 투어 반복 알고리즘 Knight's Tour Problem iteration https://codinghago.tistory.com/55 [python]파이썬 나이트 투어 재귀 알고리즘 Knight's Tour Problem recursiveKnight's Tour Problem 체스판에서 기사(Knight)말의 움직임은 아래와 같다. 임의의 위치에 놓여진 기사를 움직여서 모든 64개의 격자를 모두 방문하도록 기사말을 옮기는 방법을 계산하라. 단, 기사가codinghago.tistory.com 앞서 살펴보았던 나이트 투어 알고리즘을 재귀함수가 아닌 반복문으로 해결해 보려고 한다. stack을 사용하면 반복문으로 해결할 수 있다.  스택(STACK)스택은 자료구조의 한 형태로, LIFO(Last In First Out) 후입선출의 원칙에 따라 데이터를 관리한다. 즉,  가장 마지막..
[SQL/DFL] SELECT문의 WHERE절과 논리, 비교, SQL 연산자 WHERE절 SELECT [ALL|DISTINCT] {COLUM_name [[AS] COLUM_alias],}+ | *}FORM TABLE_LIST[WHERE 투플_조건식]WHERE절을 사용하면 투플 조건식을 이용하여, 테이블에서 조건에 맞는 투플만을 선택할 수 있다. 여기서 투플_조건식이란 비교연산자, SQL연산자, 논리연산자를 의미한다. 기본예제) SELECT PLAYER_ID, PLAYER_NAME, BACK_NO, TEAM_IDFROM PLAYERWHERE TEAM_ID = 'K06';WHERE절을 사용해서 TEAM_ID가 'K06'인것만 출력할 수 있다.  1. 연산자의 종류 연산자의 종류는 비교연산자, SQL 연산자, 논리 연산자가 있다. 3가지 연산자의 우선순위는 비교 연산자와 SQL연산자..
[SQL] SQL을 공부하기전 알면 좋은 기본 지식 SQL의 기본 1) 출력은 항상 테이블 검색 질의의 결과는 항상 테이블이다. 예를들어 다음과 같이 함수를 사용해서 값이 하나가 나올 상황을 살펴보자 이 경우에도 SQL은 무조건 테이블로 출력값이 나온다.SELECT LENGTH('SQL Expert') AS ColumnLenght;  2) FROM은 생략 가능? 불가능? MySQL, SQL server에서는 FROM 절도 생략가능하다. 하지만 Oracle에서는 절대 FROM 절 생략 불가하다.SELECT LENGTh('SQL Expert') AS ColumnLenght;FROM DUAL;이와 같이 함수를 출력할 때도 Oracle의 가짜 테이블이자 기본 테이블인 DUAL을 FROM해야함. DUAL테이블은 사용자 SYS가 소유하고 있는 테이블이며 모든 사용자..

티스토리툴바