Category: algorithms

2018
0
computer sciencealgorithms

백준[13300] - 방 배정

문제백준 13300 문제 보기 접근 방법인원을 학년별로 같은 성별끼리 저장한 뒤, 방의 최대 인원으로 각 학년별 인원을 나누었다. 코드#include <iostream> #include <cstring> #include <math.h> using namespace std; int K; // 방의 최대 인원 수 int N; // 학생

0
computer sciencealgorithms

백준[14864] - 줄서기

문제백준 14864 문제 보기 접근 방법문제를 손으로 적어보고 그대로 구현해보니깐 정답이 나왔다. 그래도 초반 몇번의 제출에서는 시간 초과가 나왔는데 벡터를 사용하는 대신 배열을 사용해서 시간 초과가 났다. 이유는 중간을 지웠을 경우 중간 인덱스서 부터 맨끝까지 한 칸씩 앞으로 땡겨야 했다.문제 접근은 처음 입력을 받으면서 나보다 뒤에 몇명이 작은 숫자를

0
computer sciencealgorithms

백준[14863] - 서울에서 경산까지

문제백준 14863 문제 보기 접근 방법빠르게 틀을 만들어 놓고 이상한 곳에서 실수를 너무 많이했다. 문제 접근은 처음 도보와 자전거를 모두 dfs로 탐색한다. 하지만 이전에 진행했던 경로를 저장하지 않으면 시간복잡도는 O(2^n)으로 시간 초과를 유발한다. 따라서 이전에 지나갔던 노드라면 memo에서 꺼내어 여지껏 노드까지 온 거리를 더해서 리턴한다.하지

0
computer sciencealgorithms

백준[14697] - 방 배정하기

문제백준 14697 문제 보기 접근 방법처음에는 dfs로 문제를 접근하려했다. 하지만 dfs로 문제를 풀 경우 O(3^N)이라는 큰 시간복잡도를 보인다. 이를 해결하기 위해 복잡한 예외 처리 및 메모이제이션을 사용해야할 것 같아 다른 방법을 생각해 보았다. 결과적으로 브루스포스로 접근하면 O(N^3)으로 쉽게 해결할 수 있다. 코드 #include <i

2017
0
computer sciencealgorithms

힙 정렬(Heap sort)

#들어가기이번 포스팅에는 힙 정렬(heap sort)에 대해 알아보겠습니다. #힙 정렬(heap sort)먼저 힙 정렬(heap sort)을 이해하기 위해서 힙(heap) 에 대해 알아보겠습니다.힙(heap) 은 다음과 같은 두가지 조건을 만족해야 합니다. complete binary tree heap property 즉, 완전 이진 트리이면서 힙이 가

0
computer sciencealgorithms

퀵 정렬(Quick sort)

#들어가기이번 시간에는 분할정복법을 사용한 퀵 정렬(quick sort)를 알아보겠습니다. #퀵 정렬(quick sort)먼저 퀵 정렬(quick sort)의 간략한 개념부터 살펴보겠습니다. 위의 사진에서 볼수 있듯이 pivot을 선택 pivot을 기준으로 분할 분할된 구역에서 다시 순환적으로 정렬(정복) 즉, 퀵 정렬(quick sort)의 중요한