programing/Algorithm
-
[Algorithm] 정렬 알고리즘에 대하여 3programing/Algorithm 2019. 7. 13. 16:03
안녕하세요, Einere입니다. (ADblock을 꺼주시면 감사하겠습니다.) 2019/06/26 - [programing/Algorithm] - [Algorithm] 정렬 알고리즘에 대하여 1 2019/06/27 - [programing/Algorithm] - [Algorithm] 정렬 알고리즘에 대하여 2 이번 포스트에서는 이진 힙(binary heap)를 이용한 힙(heap) 정렬에 대해 알아보도록 하겠습니다. 힙 (heap) 힙은 다음과 같은 성질을 지니고 있습니다. 완전 이진 트리 (complete binary tree) 모든 노드는 최대 두 개의 자식을 가질 수 있습니다. 모든 잎 노드 (leaf node)의 깊이(depth)는 동일하며, 왼쪽부터 빈틈없이 채워져야 합니다. 모든 잎 노드를 제외..
-
[Algorithm] 프로그래밍 대회에서 배우는 알고리즘 문제해결 전략 4programing/Algorithm 2019. 7. 12. 16:44
안녕하세요, Einere입니다. (ADblock을 꺼주시면 감사하겠습니다.) 2019/07/02 - [programing/Algorithm] - [Algorithm] 프로그래밍 대회에서 배우는 알고리즘 문제해결 전략 1 2019/07/09 - [programing/Algorithm] - [Algorithm] 프로그래밍 대회에서 배우는 알고리즘 문제해결 전략 2 2019/07/09 - [programing/Algorithm] - [Algorithm] 프로그래밍 대회에서 배우는 알고리즘 문제해결 전략 3 해당 포스트는 "프로그래밍 대회에서 배우는 알고리즘 문제해결 전략"을 읽고 간단하게 정리한 포스트입니다. 정당성 증명 수학적 귀납법과 반복문 불변식 수학적 귀납법 단계 나누기 첫 단계 증명하기 귀납 증명하기..
-
[Algorithm] 연속구간의 최대 합을 구하는 알고리즘programing/Algorithm 2019. 7. 9. 20:19
안녕하세요, Einere입니다. (ADblock을 꺼주시면 감사하겠습니다.) 해당 포스트에서는 연속구간의 최대 합을 구하는 여러 알고리즘에 대해 포스팅하겠습니다. 문제 정의 정수로 이루어진 수열에 대해, 연속된 부분구간 중, 그 합이 최대가 되는 구간을 찾고자 합니다. 무차별 대입(brute force) 알고리즘 int bruteFroce(int[] arr) { int n = arr.length; int max = Integer.MIN_VALUE; for (int i = 0; i < n; i++) { for (int j = i; j < n; j++) { int sum = 0; for (int k = i; k < j; k++) sum += arr[k]; max = Math.max(max, sum); } }..
-
[Algorithm] 프로그래밍 대회에서 배우는 알고리즘 문제해결 전략 3programing/Algorithm 2019. 7. 9. 17:32
안녕하세요, Einere입니다. (ADBlock을 꺼주시면 감사하겠습니다.) 2019/07/02 - [programing/Algorithm] - [Algorithm] 프로그래밍 대회에서 배우는 알고리즘 문제해결 전략 1 2019/07/09 - [programing/Algorithm] - [Algorithm] 프로그래밍 대회에서 배우는 알고리즘 문제해결 전략 2 해당 포스트는 "프로그래밍 대회에서 배우는 알고리즘 문제해결 전략"을 읽고 간단하게 정리한 포스트입니다. 시간복잡도 분석 방법 반복문의 반복 횟수 측정 선형 시간(linear time) 알고리즘 이동평균(moving average) 이동평균은 시간에 따라 변화하는 값들을 관찰할 때 유용하게 사용할 수 있는 통계적 기준입니다. 시간에 따라 관찰된 숫..
-
[Algorithm] 프로그래밍 대회에서 배우는 알고리즘 문제해결 전략 2programing/Algorithm 2019. 7. 9. 16:33
안녕하세요, Einere입니다. (ADblock을 꺼주시면 감사하겠습니다.) 2019/07/02 - [programing/Algorithm] - [Algorithm] 프로그래밍 대회에서 배우는 알고리즘 문제해결 전략 1 해당 포스트는 "프로그래밍 대회에서 배우는 알고리즘 문제해결 전략"을 읽고 간단하게 정리한 포스트입니다. 좋은 코드를 짜기 위한 원칙 간결한 코드 작성하기 적극적으로 코드 재사용하기 표준 라이브러리 공부하기 항상 같은 형태로 프로그램을 작성하기 알관적이고 명료한 명명법 사용하기 모든 자료를 정규화하여 저장하기 특정 로직과 데이터를 분리하기 자주하는 실수 산술 오버플로우 범위 밖 인덱스 접근 일관되지 않은 범위 표현 방식 사용 반 열린 구간(half-open interval)을 사용하자 o..
-
[Programmers] 모의고사programing/Algorithm 2019. 7. 5. 21:40
안녕하세요, Einere입니다. (ADblock을 꺼주시면 감사하겠습니다.) 모의고사 Level 1 Label 완전탐색 문제설명 점심시간에 도둑이 들어, 일부 학생이 체육복을 도난당했습니다. 다행히 여벌 체육복이 있는 학생이 이들에게 체육복을 빌려주려 합니다. 학생들의 번호는 체격 순으로 매겨져 있어, 바로 앞번호의 학생이나 바로 뒷번호의 학생에게만 체육복을 빌려줄 수 있습니다. 예를 들어, 4번 학생은 3번 학생이나 5번 학생에게만 체육복을 빌려줄 수 있습니다. 체육복이 없으면 수업을 들을 수 없기 때문에 체육복을 적절히 빌려 최대한 많은 학생이 체육수업을 들어야 합니다. 전체 학생의 수 n, 체육복을 도난당한 학생들의 번호가 담긴 배열 lost, 여벌의 체육복을 가져온 학생들의 번호가 담긴 배열 re..
-
[Programmers] 체육복programing/Algorithm 2019. 7. 5. 21:28
안녕하세요, Einere입니다. (ADblock을 꺼주시면 감사하겠습니다.) 체육복 Level 1 Label 탐욕법(Greedy) 문제설명 점심시간에 도둑이 들어, 일부 학생이 체육복을 도난당했습니다. 다행히 여벌 체육복이 있는 학생이 이들에게 체육복을 빌려주려 합니다. 학생들의 번호는 체격 순으로 매겨져 있어, 바로 앞번호의 학생이나 바로 뒷번호의 학생에게만 체육복을 빌려줄 수 있습니다. 예를 들어, 4번 학생은 3번 학생이나 5번 학생에게만 체육복을 빌려줄 수 있습니다. 체육복이 없으면 수업을 들을 수 없기 때문에 체육복을 적절히 빌려 최대한 많은 학생이 체육수업을 들어야 합니다. 전체 학생의 수 n, 체육복을 도난당한 학생들의 번호가 담긴 배열 lost, 여벌의 체육복을 가져온 학생들의 번호가 담긴..
-
[Algorithm] 프로그래밍 대회에서 배우는 알고리즘 문제해결 전략 1programing/Algorithm 2019. 7. 2. 21:58
안녕하세요, Einere입니다. (ADblock을 꺼주시면 감사하겠습니다.) 해당 포스트는 "프로그래밍 대회에서 배우는 알고리즘 문제해결 전략"를 읽고 간단하게 정리한 포스트입니다. 문제해결 과정 문제를 읽고 이해한다. 문제를 익숙한 용어로 재정의한다. 어떻게 해결할 지 계획을 세운다. 계획을 검증한다. 프로그램으로 구현한다. 어떻게 풀었는지 회고하고, 개선할 방법이 있는지 찾아본다. 문제해결 전략 체계적인 접근을 위한 질문들 비슷한 문제를 풀어본 적이 있는가? 단순한 방법에서 시작할 수 있을까? 해결 과정을 수식화할 수 있을까? 문제를 단순화할 수 없을까 그림으로 그려볼 수 있을까? 수식으로 표현할 수 있을까? 문제를 분해할 수 있을까? 역순으로 풀 수 있을까? 순서를 강제할 수 있을까? 정규화할 수 ..