[패스트캠퍼스 수강 후기] 올인원 패키지 : 컴퓨터 공학 전공 필수👉C언어인강 100% 환급 챌린지 30회차 미션

 

 

환급미션 30일째...

 

 

 

소프트웨어 베이직 - 자료구조와 알고리즘 - 01. 자료구조의 개요

 

 

자료구조의 필요성 및 성능 측정 방법 학습

데이터를 효과적으로 저장, 처리하는 방법에 대한 이해

불필요한 메모리/성능 낭비를 줄이기 위해

ex)

프로그램 내에서 int형 데이터가 100만 개 사용되는 경우, 원하는 데이터를 가장 빠르게 찾도록 해주는 자료구조는 무엇일지?

 

 

 

- 자료구조의 개요

 

 

 

* 기본적인 자료구조들

 

1. 선형 구조

•배열

•연결 리스트

•스택

•큐

 

2. 비선형 구조

•트리

•그래프

 

 

 

* 자료구조와 알고리즘

 

효율적인 자료구조 설계를 위해 알고리즘 지식이 필요

효율적인 알고리즘 작성을 위해 문제 상황에 맞는 적절한 자료구조가 사용되어야 한다.

=> 자료구조론과 알고리즘이론은 모두 동일선상에 놓을 수 있다.

 

 

 

 

 

* 프로그램의 성능 측정 방법론

 

시간복잡도 (time complexity) : 알고리즘에 사용되는 연산 횟수

공간복잡도 (space complexity) : 알고리즘에 사용되는 메모리의 양

 

-> 효율적인 알고리즘을 사용한다고 가정했을 때 일반적으로 시간,공간은 반비례 관계

 

 

시간 복잡도를 표현할 때는 최악의 경우를 나타내는 Big-O 표기법을 사용

(최악의 경우를 기반으로 했을 때 시간이 얼마가 소요될 것이다.)

 

 

•O(n)의 시간 복잡도를 가지는 알고리즘

-> 입력받은 b의 값만큼 i가 0부터 b까지 반복한다.

 

 

 

•O(n^2)의 시간 복잡도를 가지는 알고리즘

-> 반복문에 반복문이 사용되는 경우

i가 0부터 n까지 반복할때마다 j가 0부터 i까지 반복한다. 기본적으로 n^2만큼 반복을 한다고 가정

 

 

 

•다음 알고리즘의 시간 복잡도는?

 

-> 그냥 a+b을 바로 출력, 시간복잡도는 O(1) 이라고 표현한다.

 

 

-> 연산 횟수가 10억을 넘지 않도록 한다.

 

 

 

•시간 복잡도를 표기할 때 항상 큰 항과 계수만 표시한다.

 

-> n을 무시, 3도 무시

(n이 무한대로 간다고 가정했을 때를 생각)

 

현실의 다양한 문제에서는 시간제한을 1초 정도라고 생각한다.

 

 

 

•공간 복잡도를 표기할 때 일반적으로 MB 단위로 표기한다.

 

 

 

 

 

 

소프트웨어 베이직 - 자료구조와 알고리즘 - 02. 연결 리스트

 

연결 리스트의 필요성과 쓰임새에 대해 학습

c언어를 활용하여 연결 리스트를 구현하는 방법에 대해 학습

 

 

일반적으로 배열을 사용해 데이터를 순차적으로 저장,나열

배열을 사용하는 경우 메모리 공간이 불필요하게 낭비될 수 있다.

 

 

 

 

- 배열 기반의 리스트

 

-> 데이터를  순차적으로 저장, 처리할 때

배열 기반의 리스트를 간단히 이용할 수 있다.

 

-----------------------------------

 

------------------------------

 

 

 

* 위의 코드를 참고로, 특정한 위치의 원소를 삭제하는 함수는 어떻게 만들 수 있을까?

 

위 코드는 '배열에서 n번째' 값을 넣었을 때의 상황을 고려해서 작성한 코드이고

 

위 코드는 인덱스값을 넣었을 때의 상황을 고려해서 작성된 코드이다.

 

 

 

 

* 배열 기반 리스트의 특징

 

배열 기반이므로 특정한 위치의 원소에 즉시 접근 가능

데이터가 들어갈 공간을 미리 메모리에 할당해야 한다는 단점

원하는 위치로의 삽입/삭제가 비효율적

(위의 코드에서 볼 수 있는 것처럼 기존의 값들을 모두 이동시켜야 한다)

 

 

 

 

 

- 연결 리스트 (포인터 기반)

 

구조체와 포인터를 함께 사용하여 구현

리스트의 중간 지점에 노드를 추가하거나 삭제할 수 있어야 한다.

필요할 때마다 메모리 공간을 할당받는다. (동적 할당을 이용)

 

 

 

* 단일 연결 리스트

 

포인터를 이용해 단방향적으로 다음 노드를 가리킨다.

하나의 구조체 안에 두 개의 변수 ( data + next:다음 구조체를 가리키는 포인터 변수 )

Head : 연결 리스트의 시작 노드, 별도로 관리

다음 노드가 없는 끝 노드의 다음 위치 값으로 NULL을 넣는다.

 

 

 

* 연결 리스트 구조체 만들기

 

 

위와 같이 코드를 작성하여 기본적인 연결리스트 구조체를 작성해보았다.

 

 

 

 

* 연결 리스트 삽입 과정 

 

위에서 작성한 코드를 활용,

첫 번째 위치에 노드를 삽입하는 과정을 다루어볼 것이다.

 

 

위의 코드를 추가하여

노드를 삽입할 수 있다.

 

 

 

 

 

* 연결 리스트 삭제 과정

 

 

삭제할 노드의 앞 노드(여기서는 헤드)의 next가 삭제할 노드 다음 노드를 가리키도록 하고,

삭제할 노드를 메모리 할당해제 하면 끝

 

 

 

 

 

* 연결 리스트 메모리 해제 함수

 

연결리스트 : 한 개씩 데이터를 거쳐가면서 리스트 전체 원소를 확인

메모리 해제 또한 마찬가지로 한 개씩 데이터를 접근해서 해제해야 한다

 

 

 

 

 

* 연결 리스트 전체 출력 함수

 

현재 연결리스트에 존재하는 모든 노드의 데이터를 출력

 

 

 

 

 

 

 

* 위에서 작성한 전체함수를 가지고 완성된 연결리스트들을 이용해볼 것이다.

 

-> 출력값은 9 7 1 2 가 된다.

 

 

 

 

 

 

* 연결리스트 구현에서 주의사항

 

 

위 소스코드에 덧붙여 삽입/삭제 기능에서 예외사항을 처리할 필요가 있다.

삭제할 원소가 없는데 삭제하는 경우, head 노드 자체를 잘못 넣은 경우 등을 체크해야 한다.

-> "더이상 삭제할 원소가 없습니다." 등의 메시지 출력 등

 

 

 

 

* 포인터를 이용한 연결 리스트의 특징

 

데이터를 선형적으로 저장하고 처리하는 방법이다.

삽입, 삭제가 배열에 비해 간단하다.

배열과는 다르게 특정 인덱스로 즉시 접근하지 못하며, 원소를 차례대로 검색해야 한다는 단점

(배열에 비해서 느릴 수 있다.)

-> 특정한 인덱스에 바로 참조해야 하는 경우가 많다면 배열을 이용하는 것이 효율적이다.

추가적인 포인터 변수가 사용되므로 메모리 공간이 낭비된다.

 

 

 

 

 

운영체제 - 운영체제 핵심 개념잡기 - 01. History로 이해하는 운영체제 핵심 기술 : 1950-1960 초반

운영체제 - 운영체제 핵심 개념잡기 - 02. History로 이해하는 운영체제 핵심 기술 : 1960 후반 _ 멀티태스킹

운영체제 - 운영체제 핵심 개념잡기 - 03. History로 이해하는 운영체제 핵심 기술 : 1960 후반 _ 시분할 시스템

 

 

 

 

- 1950년대

ENIAC : 첫 번째 컴퓨터

운영체제가 없었다. (1개의 응용 프로그램을 실행시키기도 바빴다.)

응용 프로그램이 시스템 자원을 제어

 

- 1960년대 초반

배치 처리 시스템 (batch processing system) 출현

: 여러 응용 프로그램을 등록시켜놓으면, 순차적으로 실행하는 시스템

배치 처리 시스템을 기반으로 운영체제가 출현

 

- 1960년대 후반

새로운 개념이 제안됨 (실제 운영체제로 구현되지는 않았다)

•시분할 시스템 (time sharing system)

•멀티 태스킹 (multi tasking)

 

 

 

* 시분할 시스템

 

응용 프로그램이 cpu를 사용하는 시간을 쪼개서, 여러 개의 응용프로그램을 나름대로 동시에 실행

 

-> 응답시간을 최소화시키고, 다중 사용자를 지원할 수 있게 된다.

 

 

 

* 멀티태스킹

 

단일 cpu에서, 여러 응용프로그램의 병렬 실행을 가능하게 하는 시스템

(일반적으로 시분할 시스템 = 멀티태스킹)

 

 

* 멀티 프로그래밍

 

최대한 cpu를 많이 활용하도록 하는 시스템

(시간대비 cpu 활용도를 높인다.)

 

 

 

 

* 배치 처리 시스템의 단점

 

컴퓨터 응답시간(response time) - 앞의 프로그램이 실행시간이 오래 걸리는 경우

실행 시간 - cpu가 필요없는 상황에서도 응용프로그램이 cpu를 점유

 

 

* 시분할 시스템 / 멀티 태스킹

 

시간을 잘게 쪼개서, 여러 응용 프로그램을 실행

컴퓨터 응답시간을 줄임

전체 응용 프로그램의 실행시간을 줄임

사용자는 여러 응용프로그램이 동시에 실행되는 것처럼 보이게 된다.

 

 

 

 

 

올인원 패키지 : 컴퓨터 공학 전공 필수👉https://bit.ly/3i4sCVE