전체 글
-
[Data Structure] 배열의 크기 조정하기알고리즘 & 자료구조 2021. 1. 24. 16:03
소스 코드를 보기전에 먼저 생각해보자 우리가 이미 일정한 크기의 배열을 선언 했다면, 그 크기를 키우려면 어떻게 해야할까? list[0] = 1; list[1] = 2; list[2] = 3; 밑에 표를 메모리라 생각해보자 list[3] 에 4를 저장하고 싶지만 h라는 값이 메모리에 담겨있다. e m m a 1 2 3 h e l l o 단순히 메모리의 위치 바로옆에 일정 크기의 메모리를 덧붙일수 없다. 따라서 안전하게 새로운 공간에 큰 크기의 메모리를 다시 할당하고 기존 배열의 값들을 하나씩 옮겨줘야 한다. 이러한 작업은 O(n), 즉 배열의 크기 n만큼의 실행 시간이 소요될것이다. 이 과정을 코드로 나타내면 아래와 같다. #include #include int main(void) { //첫번째 방법 /..
-
[프로그래머스 C++] 모의고사알고리즘 & 자료구조/코딩테스트 2021. 1. 21. 21:43
문제 설명 수포자는 수학을 포기한 사람의 준말입니다. 수포자 삼인방은 모의고사에 수학 문제를 전부 찍으려 합니다. 수포자는 1번 문제부터 마지막 문제까지 다음과 같이 찍습니다. 1번 수포자가 찍는 방식: 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, ... 2번 수포자가 찍는 방식: 2, 1, 2, 3, 2, 4, 2, 5, 2, 1, 2, 3, 2, 4, 2, 5, ... 3번 수포자가 찍는 방식: 3, 3, 1, 1, 2, 2, 4, 4, 5, 5, 3, 3, 1, 1, 2, 2, 4, 4, 5, 5, ... 1번 문제부터 마지막 문제까지의 정답이 순서대로 들은 배열 answers가 주어졌을 때, 가장 많은 문제를 맞힌 사람이 누구인지 배열에 담아 return 하도록 solution 함수를 작..
-
[알고리즘] 병합 정렬알고리즘 & 자료구조 2021. 1. 21. 16:31
병합 정렬 병합 정렬은 원소가 한 개가 될 때까지 계속해서 반으로 나누다가 다시 합쳐나가며 정렬을 하는 방식이다. 그리고 이 과정은 재귀적으로 구현된다. 아래의 숫자들을 오름차순으로 정렬해 보자 7 4 5 2 6 3 8 1 먼저 숫자들을 반으로 나눈다. 7 4 5 2 | 6 3 8 1 그리고 나눠진 부분 중 첫번째를 한번 더 반으로 나눈다. 7 4 | 5 2 | 6 3 8 1 마지막으로 한 번 더 나눠준다 7 | 4 | 5 2 | 6 3 8 1 이제 숫자가 7 과 4로 나뉘어져있다. 두 숫자를 병합 해보자. 단, 작은 숫자가 먼저 오도록한다 4 7 | 5 2 | 6 3 8 1 마찬가지로 5 ,2 역시 나눈 후 병합해보면 4 7 | 2 5 | 6 3 8 1 이제 4 7 | 2 5 부분을 병합 2 4 5 7..