본 게시글은 "프로그래밍 대회에서 배우는 알고리즘 문제 해결 전략 (구종만 저)"의 내용을 참고하여 기재하였습니다. 분할 정복 부분 문제의 답으로부터 전체 문제의 답을 도출한다. (1) 문제를 더 작은 문제로 분할하는 과정 (Divide) (2) 부분 문제를 원래 문제로 병합하는 과정(merge) (3) 더이상 답을 분할하지 않고 바로 푸는 문제 (base case) ex) 행렬의 거듭제곱 행렬의 곱셈은 주어진 행렬의 모든 원소를 가로 세로를 곱해줘야하므로 O(n^3) 의 시간 복잡도를 가진다. 이를 분할 정복을 이용해서 풀어보자. class SquareMatrix; SquareMatrix identity(int n); SquareMatrix pow(const SquareMatrix& A, int m) ..
본 게시글은 "프로그래밍 대회에서 배우는 알고리즘 문제 해결 전략 (구종만 저)"의 내용을 참고하여 기재하였습니다. [06] 무식하게 풀기 (Brute-Force) 재귀호출 재귀호출의 기저 사례 : 더 이상 쪼개지지 않는 마지막 조각에 도달했을 때 답을 반환하는 조건문을 작성하여야 함. 이 마지막 조각을 기저 사례라고 한다. 4중 for문을 통해 4가지 원소를 고르는 사례에서, 원소들의 총 개수 더 골라야 할 원소들의 개수 지금까지 고른 원소들의 번호 이 세가지를 함수의 인자로 넣어 재귀호출을 수행할 수 있다. 따라서 재귀호출로 완전탐색 문제를 풀 때는 아래의 프로세스를 사용한다. (1) 문제의 분할 (2) 기저 사례의 선택 (3) 구현 (4) 시간복잡도 분석 문제1 : 소풍 #include using ..
A와 B 사이에 겹치는 건물이 있는지 확인하는 과정에서 "두 점 사이의 직선" 공식을 이용해서 A와 B사이에 있는 모든 건물의 높이를 계산하여 푸는 과정을 이용했다. 여기서 (double) 범벅을 한 이 코드에서 j가 자꾸 잘 못 구해지는 버그가 있었다. A와 B건물 사이의 i번째 건물의 높이가 A와 B의 지붕을 연결한 선에 겹치지 않는지 검사하기 위해서 아래 공식을 사용한 것인데, j의 계산이 잘 되지 않았다 . #include #include using namespace std; // 고층 빌딩 /* 15 1 5 3 2 6 3 2 6 4 2 5 7 3 1 5 */ vector height ; // 빌딩 A(x1, y1)이 빌딩 B(x2, y2)를 볼 수 있는 지 확인하는 함수 bool isOverla..
총 일할 수 있는 N일 중에서 연속된 M일을 선택했을 때 그 부분합이 최대가 되는 경우를 계산하는 문제이다. 구간을 정해서 부분합을 구하는 슬라이딩 윈도우 혹은 투포인터 알고리즘을 적용할 수 있고, 여기서는 M이라는 일정한 크기의 윈도우가 정해져있으므로 슬라이딩 윈도우 알고리즘을 사용하여 풀이한다. https://ji-musclecode.tistory.com/37 슬라이딩 윈도우 알고리즘(Sliding Window) (feat. 투 포인트) 1. 슬라이딩 윈도우 알고리즘 (Sliding Window) ( 슬라이딩 윈도우 알고리즘 간단 예제 ) 1, 2, 3, 4, 5, 6, 7 로 이루어진 숫자 배열에서 A[i] + A[i+1] + A[i+2] 형식으로 연속적인 3개의 숫자의 합의 최댓값을 ji-musc..
해당 리스트의 연속 수열의 합이 특정 값보다 이상이 되는 것 중 가장 짧은 것의 길이를 확인하는 문제이다. https://butter-shower.tistory.com/226 [Algorithm] 투포인터(Two Pointer) 알고리즘 알고리즘 문제를 풀다보면 종종 나오는 투포인터 알고리즘! 막 꼬여가지고 ㅋㅋㅋ 저도 중간에 제대로 못짜고 그러는 경우가 많은데요, 많은 코딩테스트 문제에 등장하는 것은 아니지만 잊을만 butter-shower.tistory.com 투포인터 알고리즘은 병합정렬에서 사용한 Conquer 방식과 유사하게 start와 end 지점에서의 부분합을 계산하는 알고리즘이다. 이 문제에서는 특정값 S의 이상이 되는 값들 중 가장 짧은 것을 구하라고 하였으니, 아래의 방법들로 소스코드를 ..
AWS에서 데스크탑으로 서버를 옮기고 개발을 마무리하기 위해 포스팅을 시작한다. 먼저 Linux 운영 체제에 Docker를 설치하고 Web Server를 깔아 아래와 같이 Localhost에 페이지를 띄우는 것을 마무리했다. https://velog.io/@vamos_eon/Docker-3-Web-Server-%EA%B5%AC%EC%B6%95-%EB%B0%8F-%EC%9B%B9-%ED%8E%98%EC%9D%B4%EC%A7%80-%EC%A0%9C%EC%9E%91 Docker (3) :: Web Server 구축 및 웹 페이지 안녕하세요, 주니어 개발자 Eon입니다. velog.io 한번 씩 로그인이 되지 않고 docker-compose up 하는 과정에서 Permission error가 뜬다면 아래 링크 ..
2022.10.22 - [ICE/Database Design] - 세미 조인과 안티 조인의 개념과 사용 방법 2022.10.21 - [ICE/Database Design] - 내부 조인/외부 조인의 종류와 분류 위에 정리한 문서들을 토대로 값을 불러오는 예제 문제들을 풀어보았습니다. 다양한 형태의 SELECT 기술을 사용해서 문제를 풀어볼 것인데, 중간중간 개념설명이 끼어 있어 보기 불편할 수 있습니다. 참고해서 읽어주시면 감사하겠습니다 : ) > 각 테이블 전체 데이터 조회 결과 (전체 데이터가 궁금하면 Cntrl + F 후 select * from 테이블명으로 찾아주세요!) 더보기 SELECT-FROM-WHERE 예제 1. 이름이 John B.Smith인 사원의 생일(BDATE)와 주소(ADDRESS..
