728x90 프로그래밍43 [알고리즘 시리즈] 분할 정복 : Divide and Conquer 분할 정복 : Divide and Conquer목차1. 분할 정복의 목적2. 분할 정복의 적용 절차3. 분할 정복이 적용된 형태4. 재귀적으로 분할된 알고리즘의 시간복잡도를 분석하는 방법1. 분할 정복의 목적복잡한 전체 문제를 쉬운 부분 문제로 나누어 푼다. 2. 분할 정복의 적용 절차전체 문제를 부분 문제로 나눈다. -> divide부분 문제를 해결한다. -> conquer해결된 부분 문제들을 합친다. -> combine 3. 분할 정복이 적용된 형태아래는 분할 정복을 이용하여 병합 정렬을 수행하는 코드다.배열을 절반으로 분리한다. 투 포인터를 이용해 두 배열을 하나의 배열에 오름차순으로 정렬한다. def merge_sort(arr): if len(arr) > 1: mid = len(.. 2024. 9. 14. [알고리즘 시리즈] 알고리즘 분석 방법 : 시간복잡도와 공간복잡도 알고리즘 분석 방법목차1. 알고리즘이란 무엇인가2. 알고리즘을 분석하는 방법3. 시간복잡도란 무엇인가4. 시간복잡도를 계산하는 방법5. Growth of functions6. 공간복잡도란 무엇인가7. 좋은 알고리즘이란 무엇인가1. 알고리즘이란 무엇인가문제를 해결하는 일반적인 방법이다. 2. 알고리즘을 분석하는 방법알고리즘의 효율성은 아래 두 가지 기준으로 판단한다.시간 복잡도 (Time Complexity)공간 복잡도 (Space Complexity)또한, 입력값이 주어지는 상황을 3가지로 나누어 알고리즘을 분석한다.worst-case : 최악의 시간 복잡도를 가지는 입력값이 주어진 경우average-case : 평균의 시간 복잡도를 가지는 입력값이 주어진 경우best-case : 최상의 시간 복잡도를 .. 2024. 9. 13. [네트워크 시리즈] 패킷 전송 과정에서 발생하는 delay 다음 노드로 패킷이 전송되기까지 총 4번의 딜레이가 발생합니다. 1. processing delay : 처리 지연패킷의 다음 목적지(output link)를 결정하는데 걸리는 시간입니다.고정적이며, 하드웨어 스펙을 올리지 않는 이상 건드릴 수 있는 방법이 없습니다. 2. queueing delay : 큐잉 지연해당 패킷이 라우터에서 전송되기까지 스케쥴링 큐에서 기다리는 시간입니다.지연 시간이 나노초에서 마이크로초까지 가변적이며, 사람이 느낄 수 있는 정도까지 지연 시간이 길어질 수 있어 주의해야합니다. 3. transmission delay : 전송 지연라우터에서 회선으로 밀어내는 과정에서의 지연 시간을 의미합니다.계산 공식 : 패킷 크기 bits / 대역폭 bps 4. propagation delay .. 2024. 9. 11. [백준 시리즈] 2012번 : 실버3 - 등수 매기기 / Python 제목 : 등수 매기기출처 : 백준 / 2012번: 등수 매기기 (acmicpc.net) 사용 자료구조&알고리즘 : 그리디, 정렬 문제 설명1. 모든 학생의 시험 정보를 날려 1등부터 N등까지 동석차 없이 등수를 임의로 매겨야 한다. 2. 예상 등수와 결과 등수의 차를 불만도라고 할 때, 불만도의 합의 최소가 되도록 등수를 매기려고 한다.3. 불만도 합의 최솟값을 구해라. 제한시간 제한 : 2초메모리 제한 : 256 MBN (1예상 등수는 500,000 이하의 자연수이다. 문제 풀이1단계 : 최대 시간복잡도는 얼마인가?N의 크기가 10,000 이상이기 때문에 O(NlogN) 이하 시간복잡도가 요구된다. 2단계 : 핵심 아이디어는 무엇인가?예상 등수를 정렬하고 정렬된 등수대로 실제 등수를 부여하여 불만도를.. 2024. 9. 11. [백준 시리즈] 13900번 : 실버4 - 순서쌍의 곱의 합 / Python 제목 : 순서쌍의 곱의 합출처 : 백준 / 13900번: 순서쌍의 곱의 합 (acmicpc.net) 사용 자료구조&알고리즘 : 수학 문제 설명N개의 정수 중 서로 다른 위치의 두 수를 뽑는 모든 경우의 두 수의 곱의 합을 구하라. 제한시간 제한 : 1초메모리 제한 : 256 MBN (2입력 받는 각 수는 0이상 10,000 이하의 정수이다. 문제 풀이1단계 : 최대 시간복잡도는 얼마인가?N의 크기가 100000 이하이기 때문에 O(NlogN) 이하의 시간복잡도가 요구된다. 2단계 : naive하게 생각해보자.이중 반복문을 이용해 모든 두 수를 뽑고 곱하고 더하면 시간복잡도가 $O(N^2)$이다. 시간 초과가 발생하며 다른 방법을 생각해내야한다. 3단계 : 핵심 아이디어는 무엇인가?완전 제곱식을 이용한다.. 2024. 9. 10. [백준 시리즈] 21756번 : 브론즈2 - 지우개 / Python 제목 : 지우개출처 : 백준 / 21756번: 지우개 (acmicpc.net) 사용 자료구조&알고리즘 : 수학, 시뮬레이션 문제 설명 1. N (12. 다음 작업을 수가 정확히 하나가 남을 때까지 반복한다.홀수번 칸의 수들을 모두 지운다.남은 수들을 왼쪽으로 모은다.3. 마지막으로 남은 수를 계산해라. 제한시간 제한 : 1초메모리 제한 : 512 MB 문제 풀이1단계 : 최대 시간복잡도는 얼마인가?N의 크기가 100 이하이기 때문에 시간 복잡도 제한이 없다. 2단계 : 핵심 아이디어는 무엇인가?문제에서 제시된 기능들을 정직하게 구현하면 되는 문제이다.홀수 또는 짝수번 칸의 수만 남으므로 각 숫자의 새로운 위치는 '현재 위치 / 2'이다.$log_2N$번만 실행하면 무조건 답이 나온다.정답 코드impor.. 2024. 9. 10. [DB 시리즈] 관계형 데이터베이스 : Relational database 1. 관계형 데이터베이스란 무엇일까2차원 표 형태의 데이터 모델을 가지는 데이터 베이스를 관계형 데이터베이스라고 합니다. 데이터 모델로 사용되는 표를 relation이라고 부릅니다.2. Relation은 어떻게 구성되어 있을까1) attribute : 속성Relation의 한 열을 attribute라고 하며, attribute를 세는 단위는 degree 라고 합니다. 각 attribute의 이름은 모두 달라야 하며 한 개의 값만을 가질 수 있습니다. 또한, 원자성을 가집니다. 원자성이란 의미적으로 더 이상 쪼갤 수 없음을 의미합니다.마지막으로, 데이터 타입, 값의 크기 등 한 attribute가 취할 수 있는 값의 집합을 domain이라고 합니다. 2) tuple : 튜플Relation의 한 행을 tu.. 2024. 9. 9. [백준 시리즈] 19638번 : 실버 1 - 센티와 마법의 뿅망치 / Python 제목 : 센티와 마법의 뿅망치출처 : 백준 / https://www.acmicpc.net/problem/19638사용 자료구조&알고리즘 : 힙 문제 설명1. 횟수 제한이 있는 뿅망치를 전략대로 이용하여 모든 거인이 센티보다 키가 작도록 만들 수 있는지 구한다.2. 전략은 매번 가장 키가 큰 거인 가운데 하나를 때리는 것이다.3. 키가 1인 경우를 제외하고, 뿅망치에 맞은 거인은 키가 floor(맞은 사람의 키 / 2)가 된다.4. 전략이 먹히는 경우 YES와 최소 뿅망치 횟수를 출력하고, 전략이 먹히지 않는 경우 NO와 가장 큰 거인의 키를 출력한다. 제한시간 제한 : 1초 (최대 약 2000만번의 연산)메모리 제한 : 1024 MB인구수 N (1센티의 키 H (1뿅망치 횟수 T (1 문제 풀이1단계 .. 2024. 9. 9. [백준 시리즈] 14430번 : 실버 2 - 자원 캐기 / Python 제목 : 자원 캐기출처 : 백준 / https://www.acmicpc.net/problem/14430사용 알고리즘 : 다이나믹 프로그래밍 문제 설명1. (1, 1) 부터 (N, M)까지 자원을 탐색하여 얻을 수 있는 자원의 최대 숫자를 구해라2. 한 번에 오른쪽 또는 아래쪽으로 한 칸 이동할 수 있다. 제한시간 제한 : 2초메모리 제한 : 256 MBN(1 문제 풀이1단계 : 최대 시간복잡도는 얼마인가?최대 요소의 개수는 90000개이므로 O(NlogN) 이하의 알고리즘이 필요하다. 2단계 : 핵심적인 아이디어는 무엇인가?모든 칸에 대해 도달하였을 때의 자원의 최댓값을 구하고, 마지막 줄에서 최종적으로 최댓값을 구한다.(i, j)번째 요소에 도달하기 위해선 이전 위치가 (i, j)의 왼쪽 또는 위쪽이.. 2024. 9. 9. 이전 1 2 3 4 5 다음 728x90
