Algorithm/이론

[Algorithm] 배열(Array)과 리스트(List)

배열(Array) 배열은 메모리의 연속 공간에 값이 채워져 있는 형태의 자료구조이다. 배열의 값은 인덱스를 통해 참조할 수 있으며, 선언한 자료형의 값만 저장할 수 있다. 다음 그림은 배열을 나타낸 것이다. 그림을 보면 배열에 값 1, 값 2, ... 값 6이 채워져 있고, 각 값은 0부터 5까지 인덱스가 지정되어 있다. 배열의 특징 인덱스를 사용하여 값에 바로 접근할 수 있다. 새로운 값을 삽입하거나 특정 인덱스에 있는 값을 삭제하기 어렵다. 값을 삽입하거나 삭제하려면 해당 인덱스 주변에 있는 값을 이동시키는 과정이 필요하다. 배열의 크기는 선언할 때 지정할 수 있으며, 한 번 선언하면 크기를 늘리거나 줄일 수 없다. 구조가 간단하므로 코딩 테스트에서 많이 사용한다. 리스트(List) 리스트는 값과 포..

[Algorithm] 시간 복잡도(Time Complexity)

시간 복잡도(Time Complexity) 알고리즘에서 시간 복잡도는 주어진 문제를 해결하기 위한 연산 횟수를 말한다. 일반적으로 수행 시간은 1억 번의 연산을 1초의 시간으로 간주하여 예측한다. 시간 복잡도 유형 - 빅-오메가(Ω(n)) : 최선일 때(best case)의 연산 횟수를 나타낸 표기법 - 빅-세타(θ(n)) : 보통일 때(average case)의 연산 횟수를 나타낸 표기법 - 빅-오(O(n)) : 최악일 때(worst case)의 연산 횟수를 나타낸 표기법 코팅 테스트에서는 어떤 시간 복잡도 유형을 사용해야 할까? 코팅 테스트에서는 빅-오 표기법(O(n))을 기준으로 수행 시간을 계산하는 것이 좋다. 실제 테스트에서는 응시자가 작성한 프로그램으로 다양한 테스트 케이스를 수행해 모든 케이..