본문 바로가기

Algorithm13

[MySQL] 조건문 (IF문, CASE문) CASEWHEN [조건식1] THEN [값1]WHEN [조건식2] THEN [값2]...ELSE [값3]END1. IF문MySQL의 IF문은 기본적으로 엑셀에서 IF함수를 작성하는 방법과 같다.사용방법은 아래와 같이 조건, 참일 때의 값, 거짓일 때의 값을 차례로 명시한다.IF( [조건식], [조건 참일 때 값], [조건 거짓일 때 값] ) 간단한 예시를 통해 실제 사용되는 IF문을 알아보자.SELECT SUBWAY_LINE,IF (SUBWAY_LINE = 1, 'BLUE', 'GRAY') AS 'LINE_COLOR'FROM SUBWAY_INFO 2. CASE ~ THEN문 CASE ~ THEN 문은 IF문과는 다르게 여러 개의 조건이 있을 때 사용할 수 있다.반드시 마지막에 END를 통해 CASE ~ .. 2024. 10. 23.
[프로그래머스 | MySQL] 자동차 대여 기록에서 장기/단기 대여 구분하기 1. 문제https://school.programmers.co.kr/learn/courses/30/lessons/151138 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr다음은 어느 자동차 대여 회사의 자동차 대여 기록 정보를 담 은 CAR_RENTAL_COMPANY_RENTAL_HISTORY 테이블입니 다. CAR_RENTAL_COMPANY_RENTAL_HISTORY 테이블은 아래와 같은 구조로 되어있으 며, HISTORY_ID, CAR_ID, START_DATE, END_DATE 는 각각 자동차 대여 기록 ID, 자동차 ID, 대 여 시작일, 대여 종료일.. 2024. 10. 17.
[백준] 13397번 구간 나누기 2 (Gold 4) 문제 링크 : https://www.acmicpc.net/problem/13397 1. 문제 접근N개의 수로 이루어진 배열을 m개의 구간으로 나누어야 한다.하나의 구간은 하나 이상의 연속된 수로 이루어져 있다.구간의 점수 = 구간 내 최대값 - 구간 내 최소값"n개의 수로 이루어진 배열" 과 "구간의 개수 m"이 주어졌을 때, "구간의 점수"의 최댓값의 최소값을 구하는 문제일단 이 문제를 이해하기 전 최대값의 최소값이 무엇인지 알아보자.정말 말도 안되는 말인 것 같지만 문장의 흐름을 어느 구간에서 끊는가가 문제를 이해하는데 아주 큰 도움이 된다.구간의 점수의 최댓값 / 의 최소값 이라고 생각해보자.m개의 구간에서 "구간의 점수"가 나올 것이다.이러한 각 구간의 점수의 최대값을 구해보자.만약 제시된 예제와.. 2024. 8. 19.
이진 탐색 / 매개 변수 탐색 1. 선형 탐색보통 생각하는 탐색(완전 탐색)은 선형 탐색으로 수행된다.예를 들어 어떤 수(10)가 배열에 존재 하는지 탐색하는 상황을 말한다.선형 탐색은 일렬된 자료를 단방향으로 모두 확인하며 탐색을 진행하기 때문에 시간복잡도는 O(n)이 나온다.만약, 배열이 정렬이 되어 있다면 더 빠르게 탐색할 수 있다.정렬이 기본적인 전제 조건으로 배열이 있다면?2. 이진 탐색정렬된 상태의 배열에서의 탐색 (10을 찾기)이진 탐색 : 탐색 범위를 절반씩 좁혀가며 탐색을 진행어떤 수를 찾을 때, 범위를 절반씩 줄여나가며 정답 후보를 갱신하므로 시간복잡도는 O(logN)이 나온다.ex) [1, 6, 8, 10, 15, 16, 20, 22, 23, 24] - 배열 내 10을 찾는 과정start 1 ~ end 24 → m.. 2024. 8. 12.
우선순위 큐(최대힙, 최소힙), 다익스트라 알고리즘 1. 최소 힙, 최대 힙 (우선 순위 큐)우선순위 큐 : 들어온 순서와 상관없이 정해진 기준에 따라 값이 먼저 나간다.1-1. 사용법최대 힙 - priority_queue pq;최소 힙 - priority_queue, greater> pq;맨 앞 - pq.top()1-2. 사용 예시최대값 또는 최소값의 빠른 접근 및 삭제가 필요한 경우예를 들어, 데이터 스트림에서 현재까지 입력된 값 중 최대값 또는 최소값을 실시간으로 추적해야 할 때 유용합니다.예시: 주어진 데이터에서 k번째로 큰 요소를 찾아야 하는 경우.동적으로 데이터의 정렬이 필요한 경우리스트나 배열에 요소를 삽입하면서 정렬된 상태를 유지해야 하는 경우에 우선순위 큐가 유리합니다.예시: 정렬된 데이터 스트림에서 새로운 데이터가 추가될 때마다 정렬을 .. 2024. 7. 29.
동적 계획법 (DP) 1. 중복이 많은 완전 탐색피보나치 수열 : 첫재 및 둘쨰 항이 1이며 그 뒤의 모든 항은 바로 앞 두항의 합인 수열점화식 : f(0) = 1, f(1) = 1, f(n) = f(n-1) + f(n-2)만약 완전 탐색(백트레킹)으로 해결한다면?f(5)가 필요하다면 ? → f(4) + f(3) 이 필요해f(4)가 필요하면 → f(3)과 f(2)가 필요해f(3)이 필요하면 → f(2)와 f(1)이 필요해탑 다운 방식으로 해결하려고 한다면 너무 비효율적이고 중복으로 구해야 하는 부분이 많다.→ 시간 복잡도 : 약 O(2^n)…. 너무 오래 걸리고 비효율적이다.그렇다면 먼저 계산한 값들을 저장해놓고 필요할 때 사용하면 편하겠는데??? → 메모이제이션 2. 메모이제이션메모이제이션 : 작은 문제의 결과값을 저장해놓.. 2024. 6. 27.
MST (Minimun Spanning Tree, 최소 신장 트리) 그래프와 트리비선형 자료구조 : 객체간의 관계를 관리하며 하나의 자료 뒤에 여러 개의 자료가 존재그래프 : 노드(정점, 위치), 간선(위치간 관계), 가중치(간선에 할당된 비용)로 이루어진 자료구조유향 그래프, 무향 그래프 : 단방향이면 유향, 양방향이면 무향트리 : 사이클 없이 모든 노드가 하나의 연결 요소인 그래프사이클 - 단순 경로(노드가 중복되지 않은 경로)의 시작점과 종점이 동일한 그래프→ 노드의 개수가 n개일 때, 간선의 개수는 n-1개 이다.기본 트리는 루트를 고려하지 않음, 루트를 고려하면 루티드 트리가 된다.신장 트리(Spanning Tree) : 그래프 내의 모든 정점을 포함하는 트리→ 최소 연결(간선의 수가 가장 적은 부분 그래프)→ n개의 노드에 n-1개의 간선으로 모두 연결된 그래.. 2024. 6. 26.
[백준] 17143번 낚시왕 (Gold 1) 문제링크 17143번: 낚시왕 낚시왕이 상어 낚시를 하는 곳은 크기가 R×C인 격자판으로 나타낼 수 있다. 격자판의 각 칸은 (r, c)로 나타낼 수 있다. r은 행, c는 열이고, (R, C)는 아래 그림에서 가장 오른쪽 아래에 있는 칸이다. www.acmicpc.net 문제 접근 1. 2차원 배열에 상어가 존재 2. 각 상어들은 (방향 / 크기 / 속도)를 가진 객체 3. 매초마다 사람은 오른쪽으로 한칸씩 이동하면서 상어를 잡는다. 4. 상어가 이동하는 방향은 1->2->1 혹은 2->1->2 혹은 3->4->3 혹은 4->3->4 이다. 5. 즉, 상어는 아무리 많이 이동해도 매초 (R-1) * 2 마다 같은 위치에 위치하고 같은 방향을 바라보게 되어 실제로 움직이는 것은 (Speed % ((R-1.. 2024. 4. 20.
[백준] 17616번 등수 찾기 (Gold 3) 문제 링크 17616번: 등수 찾기 표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에 세 정수 N, M, X가 공백을 사이에 두고 주어진다. (2 ≤ N ≤ 105, 1 ≤ M ≤ min(N(N-1)/2, 5×105), 1 ≤ X ≤ N) . 다음 M 줄에는 각각 두 정수 A, B가 주어 www.acmicpc.net 문제 접근 문제는 "최대 몇등부터 몇등까지 할 수 있냐" 를 구하는 문제다. 이 말은 "내 앞에 확정 몇명이 있고 + 내 뒤에 확정 몇명이 있냐" 를 묻는 것과 동일하다. 문제의 입력 형태 "a b"는 "a가 b보다 앞에 등수에 위치한다"는 뜻으로, 이를 통해서 2차원 벡터 vector arr[MAX] 를 통해 단방향 연결을 구현했다. 또한 vector rev_arr[MAX]를 통해 반대 .. 2024. 4. 18.

티스토리툴바