Computer Science
[Algorithm] 자료구조(Data Structure) 란?
자료구조(Data Structure) - 데이터의 구체적 표현이며, 데이터를 프로그래머 관점에서 정의한다 - 데이터를 메모리에 저장하는 방법을 나타낸다 - 문제 유형에 따라 최적의 자료 구조를 선택해야 한다 자료 구조의 종류 💡 자주 사용되는 자료구조들 다음 자료 구조의 링크를 클릭하면 해당 게시글로 넘어갑니다! 🏃🏃🏃 - 배열 : codesyun.tistory.com/107 [Algorithm] 배열(Array) 배열 같은 자료형의 다중 원소 집합 순서대로 번호(인덱스, index)가 붙은 원소들이 연속적인 형태로 구성되어 있다 배열의 사용과 시간복잡도 1. k번째 위치에 원소 삽입 : 상수 시간 O(1)에 k번째 codesyun.tistory.com - 연결 리스트 : codesyun.tistory...
[Algorithm] 빅오 표기법과 시간 복잡도의 개념 및 예제
알고리즘에서 중요한 속성 1. 정확성 : 주어진 입력을 모두 처리하며 올바르게 출력해야 한다. 2. 효율성 : 문제를 효율적으로 해결해야 한다. 두 가지 변수로 측정 - 시간 복잡도 : 알고리즘이 얼마나 빠르게 결과를 출력하는지 측정, 입력 크기 n에 대한 시간 함수 T(n)으로 표현 - 공간 복잡도 : 원하는 결과를 얻기 위해 알고리즘이 얼마나 메모리를 사용하는지 측정, 입력 크기 n에 대한 메모리 사용 함수 S(n)으로 표현 빅오 표기법 (big-O) - 점근적 분석의 한 방법 - 수학적 정의 - cg(n)은 모든 n >= n0에 대해 f(n)의 상한이다. - 최고차항의 차수로 표현하고 계수와 낮은 차수의 항은 무시한다. (예시) n^2 + n = O(n^2) 시간 복잡도 알고리즘에 주로 나오는 시간..
[Algorithm] 소수를 찾는 방법, 에라토스테네스의 체
에라토스테네스의 체 란? 소수(Prime number)를 찾는 알고리즘 대량의 소수를 빠르고 정확하게 구할 수 있는 방법 에라토스테네스의 체 원리 소수를 판별할 범위의 배열을 할당하고, 값을 지워나가는 방법 1. 배열을 생성하여 초기화 2. 2부터 시작하여, 특정 수의 배수를 모두 지운다. (자기 자신은 지우지 않는다) 3. 2부터 남아있는 모든 수는 소수이다. 에라토스테네스의 체 구현 (C++) void Eratos(int n){ /* 인덱스 0과 1은 사용하지 않음을 고려하여 배열을 할당해야 한다 */ bool num[1000001]; /* 배열 초기화 : 모두 소수라고 가정한 true 값을 준다 */ for (int i = 2; i
Debugging(디버깅)이란?
Bug 벌레 프로그램의 오류 / 에러 Debug 벌레를 없애는 것 프로그램의 오류를 없애는 것 Bug의 종류는 크게 3가지 1. Complie Error 프로그램에 문법적 오류가 있어서 정상적으로 컴파일 되지 않는 경우 출력창에 어디서 에러가 발생했는지 알려주기 때문에 해결하기 쉽다. 2. Runtime Error 프로그램이 실행 중 비정상적으로 꺼지는 경우 컴파일 에러처럼 컴파일러가 에러 발생 위치를 알려주지 않기 때문에 어디서 에러가 발생했는지 찾기가 까다롭다. 프로그램을 한 줄씩 실행해보면서 문제가 발생하는 줄을 찾아야 한다. 3. Logic Error 프로그램의 결과가 이상하게 나오는 경우 예를 들어, 구구단 6단을 출력하려고 했는데 5단이 출력되었다.
[Algorithm] 브루트 포스와 BFS, DFS
브루트 포스(Brute Force) 란? Brute(무식한) + Force(힘) 브루트 포스는 완전 탐색 알고리즘으로, 가능한 모든 경우의 수를 탐색하고 조건에 충족되는 결과만을 가져온다. 무식하게 모두 탐색하기 때문에 100%의 확률로 정답을 출력합니다. 알고리즘은 기본적으로 해가 존재할 것으로 예상되는 범위를 탐색하기 때문에, 브루트 포스 알고리즘을 설계할 때, '해가 하나 이상 존재한다'는 가정을 세우고 모든 범위를 탐색합니다. 100% 정답률을 가지며 만들기 쉽다는 장점이 있지만, 실행 시간이 오래 걸린다는 단점이 있습니다. 구조에 따른 브루트 포스의 종류 브루트 포스는 모든 자료를 탐색해야하기 때문에 어떤 구조더라도 전체를 탐색할 수 있는 방법을 가진다. 선형 구조를 전체 탐색하는 방법은 순차 ..
프로그래밍 언어에서 Error의 종류. Syntax와 Semantics의 차이
Syntax와 Semantics의 정의 Syntax : 문법(Form), 일정형태의 형식에 맞게 작성된다. - 문장이 언어의 문법(grammer)에 따라 유효한지 혹은 타당한지 확인하는 것과 관련있다. Semantics : 문법에 맞는 형식을 취했을 때 그 문법이 하는 일, 의미 - 문장이 타당한 의미를 지니는지 아닌지를 판별하는 것과 관련있다 ERROR의 종류 소프트웨어의 오류는 크게 Syntax Error(구문 오류), Runtime Error(실행 오류), Semantic/Logical Error(의미적 오류)로 나눌 수 있다. 1. Syntax Error(구문적 오류) 프로그래밍 언어의 문법적인 에러를 말한다. 컴파일 과정에서 나오는 것들이며, 구문 오류, 컴파일 타임 에러라고도 한다. 예를 들어..