반응형 CS/자료구조와 알고리즘4 프로그래밍 기본 원리_데이터 0과 1만으로 모든 수를 표현하는 방법 [이진법] - 0과 1로 수를 표현하는 방법 - 숫자가 1을 넘어가는 시점에 자리 올림 - 일상적으로 숫자가 9 이상이 넘어갈 때 자리올림을 하는 십진법 - 이진법으로 나타내는 수를 이진수라고 한다. - 이진수 표기법: 1000(₂)/ 아래첨자로 보통 표기하지만 코드형에서 사용하는 방식 ob1000으로 표기해서 사용한다. 컴퓨터에게 숫자를 알려주려면 일상적으로 사용하는 십진수가 아닌 0과 1로 표현된 이진수를 전달한다. 1 : 1 2: 1 0 3: 1 1 4: 1 0 0 5: 1 0 1 6: 1 1 0 7: 1 1 1 8: 1 0 0 0 0 과 1로 음수 표현하기 : 2의 보수 - 어떤 수를 그보다 큰 2ⁿ에서 뺀 값 - 컴퓨터는 마이너스 부호를 인식하지 않기 때문.. 2023. 5. 10. 프로그래밍 기본 원리 (자료 구조, 2진수와 16진수) 자료구조(Data Structure) 는 자료를 저장하는 구조 데이터를 저장하고 관리하는 방식이라고 한다. ex) 전화번호부 전화를 알게 될 때마다 그때그때 하위로 저장한다. 하지만 저장된 번호가 많아질 수 록? 검색하는 속도가 늘어나고 찾기 힘들어 지게 된다. 만일 가,나,다 순으로 저장을 할 경우 위 경우보다 전화번호를 찾기 쉽게 된다. 하지만 가에 지정된 번호로 저장을 하게 된다면 또 다시 하위에 있는 리스트목록은 리셋되게 된다. 조금 더 효율적인 구조를 생각하게 된다면? ㄱ, ㄴ, ㄷ 순으로 분류를 하되 각각의 데이터 공간을 널널하게 주어 준다. 그리고 전화번호를 저장할 땐 해당하는 공간에 선착순으로 저장하게 된다. 이 구조는 저장도 쉽고 검색속도가 빨라지게 된다. 하지만 주어진 각각의 ㄱ, ㄴ,.. 2023. 4. 29. 퀵 정렬, 병합 정렬, 힙 정렬 비교식 정렬은 한 번에 두개씩 비교하여 교환을 정렬하는 방식이다. 분배식 정렬은 키 값을 기준으로 자료를 여러 개의 부분집합으로 분해하고 분분집합을 정렬하고 -> 전체를 정렬하는 방식이다. 분할(Divide): 배열을 같은 크기의 2개의 배열로 분할한다. 정복(Conquer): 분할된 배열을 정렬. 결합(Combine): 정렬된 부분 배열을 다시 합침 퀵 정렬과 병합 정렬은 둘 다 평균적으로 O(n log n) 성능을 갖는다. [공통점] divide and conquer(분할과 정복) 알고리즘에 속한다. 탐색할 배열의 크기를 쪼개서 재귀함수로 넘긴다. [차이점] 배열을 분할하는 방식이 서로 다르다. 메모리 공간의 사용량이 다르다. 퀵 정렬: 메모리 공간을 사용하지 않는다. 오직 콜 스택을 위한 메모.. 2022. 9. 4. 시간복잡도와 공간복잡도 알고리즘 성능 평가 - 시간 복잡도와 공간복잡도 동일한 기능을 수행하는 알고리즘이 있을 때 복잡도가 낮을 수록 좋은 알고리즘이라 말한다고 한다. 시간 복잡도: 특정한 크기의 입력에 대하여 알고리즘의 수행 시간 분석 / 알고리즘을 실행하여 종료할 때까지 걸리는 시간 공간 복잡도: 특정한 크기의 입력에 대하여 알고리즘의 메모리 사용량 분석 / 알고리즘을 실행하여 종료할 때까지 필요한 기억장치의 크기 1. 시간 복잡도 특정 알고리즘이 어떤 문제를 해결하는데 걸리는 시간을 의미한다. 같은 결과를 갖는 프로그래밍 소스도 작성 방법에 따라서 걸리는 시간이 달라지는데, 같은 결과를 같는 소스라면 시간이 적게 걸리는 것이 좋은 소스이다. [시간 복잡도 그래프] fasterO(1) 2022. 9. 3. 이전 1 다음 728x90 반응형
