크래프톤 정글 week01, day06 - 1주차 공부키워드 - 1

공부한 것

- 컴파일 시스템

- 1주차 공부 키워드 - 1

배열, 문자열, 반복문과 재귀 함수, 복잡도(BigO,시간,공간), 정렬, 완전 탐색, 정수론

---

 

컴파일 시스템

- 소스코드를 기계어로 변환하는 과정을 담당하는 프로그래밍 도구

​

소스 코드(main.cpp)

#include <iostream>

int main() {
    std::cout << "Hello, World!";
    return 0;
}

 

단계

1. 프로세서

- #include나 #define과 같은 소스코드 내의 전처리 지시어를 해석하고 처리한다.

- 위의 코드에서 프로세서가 iostream 라이브러리를 코드에 포함하라는 지시를 처리

 

2. 컴파일러

- 전처리된 소스코드가 컴파일러에 의해 어셈블리어 같은 저수준 언어로 변환

- 예시)

.section .data
.section .text
.globl main
main:
    pushq %rbp
    movq %rsp, %rbp
    movl $.LC0, %edi
    call puts
    movl $0, %eax
    popq %rbp
    ret

 

3. 어셈블러

- 위의 어셈블리어 코드를 기계어 코드로 변환하고, 오브젝트 파일에 저장

 

4. 링커

- 여러 오브젝트 파일과 라이브러리를 링커에 의해 하나의 실행파일로 결합

- 위의 경우에 “Hello, World!”를 출력하는 실행파일이 생성

---

배열

• 일련의 동일한 데이터 타입을 가진 요소들을 일정한 순서대로 나열한 것
• 배열의 특징
  • 고정 크기 : 생성 시 지정된 크기를 가지며, 이후엔 크기를 변경할 수 없다
  • 동일한 데이터 타입 : 같은 타입의 데이터로 저장되며, 예를 들면 정수형 배열은 정수만을 저장할 수 있다
  • 연속적인 메모리 할당 : 배열의 요소들은 메모리 상에서 연속적으로 위치, 이는 계산을 단순화하고 빠른 접근을 가능하게 함
  • 인덱스 접근 : 각 요소는 인덱스를 통해 접근 가능하며 보통 0부터 시작

​

• 배열의 연산
  •  삽입 : 배열에 새로운 요소를 추가. 배열은 고정 크기를 가지기 때문에, 기존 요소를 대체하거나 배열의 크기를 초과하지 않는 범위에서만 추가가 가능
  • 삭제 : 배열의 요소를 제거. 요소가 삭제되면 다른 요소들이 이동하여 채울 수 있다.
  • 검색 : 주어진 값이 배열 내에 존재하는지 찾는 작업. 선형 검색이나 이진 검색과 같은 알고리즘 사용 가능
  • 업데이트 : 배열의 특정 인덱스에 있는 값을 변경

​

• 배열의 장단점
  • 장점
    • 빠른 접근 : 인덱스를 통해 O(1)의 시간 복잡도로 요소에 접근 가능
    • 간단한 구현 : 데이터 구조 중 가장 기본적이고 이해하기 쉬운 구조
  • 단점
    • 고정 크기 : 한번 정하면 변경하기 어렵기 때문에, 크기를 정확히 알거나 충분히 할당 해야 함
    • 낭비 공간 : 배열을 너무 크게 할당하면, 사용하지 않는 공간이 생겨 메모리 낭비
    • 삽입과 삭제 비효율성 : 배열의 중간에 삽입 및 삭제를 할 경우, 나머지 요소들이 이동해야 해서 비효율적일 수 있다.

​

• 배열 관련 다른 데이터 구조
  • 동적 배열 : 배열 크기를 동적으로 변경할 수 있는 데이터 구조, ex) 파이썬 - list, 자바 - ArrayList
  • 다차원 배열 : 2차원 배열은 행렬을 나타내는데 사용되며, 3차원 이상의 배열도 가능

---

문자열

• 연속된 문자들의 나열을 의미, 텍스트 데이터를 처리할 때 필수적으로 사용됨
• 문자열의 특징
  • 불변성 : 한번 생성된 문자열은 변경 불가, 변경하려면 새로 생성하고 할당해야 한다.
  • 순차적 구조 : 문자가 순차적으로 나열되었기 때문에 각 문자엔 인덱스가 부여됨
  • 인덱싱 : 문자열의 특정 위치에 있는 문자에 접근하기 위해 인덱스 사용 가능, 인덱스는 0부터 시작
  • 슬라이싱 : 문자열의 일부분을 추출. 인덱스의 시작과 종료를 지정해 부분 문자열을 추출
• 기본 연산
  • 연결 : 두 개 이상의 문자열을 붙여 새로운 문자열 생성
  • 검색 : 특정 문자나 문자열이 주어진 문자열 내에 있는지 찾는다. 이 때 선형 검색, KMP알고리즘, 보이어-무어 알고리즘 등이 사용될 수 있다.
  • 비교 : 두 문자열이 같은지 혹은 어느 것이 사전식으로 더 앞서는지 비교. 문자열의 정렬이나 사전 편집 알고리즘에 사용됨
  • 길이 : 길이 체크. 문자열을 구성하는 문자들의 총 개수를 의미
  • 치환 : 특정 문자를 다른 문자로 바꾸는 작업
  • 분할 : 특정 구분자를 기준으로 여러 부분으로 나눔
• 문자열의 활용 예시)
  • 문자열 매칭 : 웹 검색 텍스트 편집기에서 찾기 기능 등에 사용
  • 정규 표현식 : 복잡한 문자열 패턴을 찾거나 치환할 때 사용
  • 데이터 파싱 : JSON 같은 데이터 포맷을 처리할 때 분석하여 필요 정보 추출
  • 문자열 암호화 : 보안을 위해 문자열 데이터를 암호화하고 복호화하는 과정에 사용

---

반복문과 재귀 함수

• 특정 작업을 여러 번 수행할 때 사용하는 주요 방법들
• 반복문
  • 조건이 참인 동안 일련의 명령을 반복해서 실행하는 구조. 주로 쓰는 for문과 while문이 있다.
  • for문
    • 특정 횟수를 기준으로 반복할 때 주로 사용. ex) 배열의 모든 요소를 순회할 때 적합

# 0에서 10미만으로 반복
for i in range(10):
	print(i)

• while문
  • 특정 조건이 만족하는 동안 계속해서 반복 실행 시 사용

# i가 10이 될때까지 반복. 한바퀴 돌 때마다 1씩 증가 
i = 0
while i < 10:
	print(i)
	i += 1

• 장점
  • 직관적이라 이해하기 쉽다.
  • 재귀에 비해 메모리 사용이 효율적일 수 있다.
  • 대부분의 반복 작업에 적합
• 단점 
  • 복잡한 알고리즘에서 코드가 장황해질 수 있음

•  

​

• 재귀 함수
  • 자기 자신을 호출하여 문제를 해결하는 방식의 함수. 모든 재귀 함수는 종료 조건을 가져야 하며, 조건에 도달했을 시 종료됨

n값을 받아 한번 돌 때마다 1씩 감소하며 1이 되기 전까지 반복해서 else의 return값 적용 
def factorial(n):
	if n == 1:
		turn 1
	else:
		return n * factorial(n-1)

• • 장점
    • 복잡한 문제를 간결하고 이해하기 쉬운 코드로 표현 가능
    • 자연스러운 문제 분해 방식. 트리나 그래프 같은 자료 구조를 다룰 때 유용
  • 단점
    • 호출 스택이기 때문에 메모리 사용이 많을 수 있다.
    • 재귀 호출에 대한 오버헤드가 있다.
    • 종료 조건을 잘못 설정 시 무한 재귀에 빠질 수 있다.

​

• 요약
  • 간단한 반복 시 반복문 복잡한 알고리즘 시 재귀 함수
  • 재귀 함수는 스택 오버플로우가 발생할 수 있으니 꼬리 재귀 최적화 같은 기법으로 이를 방지할 수 있다.

---

복잡도(BigO,시간,공간)

• 알고리즘의 효율성을 분석하는 데 사용하는 척도. 복잡도를 이해하는 것은 알고리즘의 성능을 예측하고 최적화하는데 중요하다.​
• 시간 복잡도
  • 알고리즘이 문제 해결 시 걸리는 시간이 입력 크기에 따라 어떻게 증가하는지 나타내는 개념
  • 일반적으로 Big O 표기법을 사용해 표현. 최악의 경우 복잡도를 나타내며, 입력 크기가 무한으로 커졌을 때의 성장률을 나타내는데 중점을 둠
  • 예시)
    • O(1) : 상수 시간 복잡도. 입력 크기와 무관하게 일정한 시간이 걸림
    • O(log n) : 로그 시간 복잡도. 이진 탐색이 좋은 예
    • O(n) : 선형 시간 복잡도. 입력 크기에 비례해 시간이 증가
    • O(n log n) : 선형 로그 시간 복잡도. 많은 효율적인 정렬 알고리즘이 이에 해당
    • O(n^2) : 제곱 시간 복잡도. 이중 반복문을 사용하는 알고리즘에서 자주 보임
    • O(2^n) : 지수 시간 복잡도. 피보나치 수열의 재귀적 해법이 이에 속함
    • O(n!) : 팩토리얼 시간 복잡도. 가장 긴 시간이 걸리는 복잡도 중 하나

​

• 공간 복잡도
  • 알고리즘이 작업 수행 시 필요한 메모리 공간의 양이 입력 크기에 따라 어떻게 변하는지 나타냄
  • 시간 복잡도와 마찬가지로 Big O 표기법을 사용해 표현
  • 알고리즘이 사용하는 총 공간은
    • 고정된 부분 - 알고리즘의 코드, 상수 단순 변수 등
    • 가변적인 부분 - 함수 호출 시 생성되는 스택, 할당된 힙 메모리 등이며 공간 복잡도는 주로 가변적인 부분에 초점을 맞춘다.
  • 예시)
    • O(1) : 상수 공간 복잡도. 입력 크기와 상관 없이 일정한 메모리를 사용
    • O(n) : 선형 공간 복잡도. 입력 크기에 비례하여 메모리 소비가 증가
    • O(n^2) : 제곱 공간 복잡도. 2차원 배열을 전체 저장할 때 나타나는 복잡도

​

• 복잡도 분석의 중요성
  • 분석을 통해 알고리즘의 성능을 예측할 수 있는데, 이는 대규모 데이터를 다루는 경우나 시스템의 응답 시간이 중요한 실시간 시스템에서 매우 중요하다.
  • 시간과 공간은 한 쪽을 줄이면 다른 한 쪽이 증가할 수 있기 때문에 자원의 제한을 고려해 잘 선택해야 한다.

---

정렬

• 데이터를 특정 순서대로 나열하는 과정. 일반적으로 숫자나 문자와 같은 데이터를 오름차순이나 내림차순으로 정렬한다.
• 주요 정렬 알고리즘
  • 버블 정렬
    • 개념 : 인접한 두 요소를 비교해 크기가 순서대로 되지 않은 경우 서로 교환
    • 시간 복잡도 : 평균 및 최악의 경우O(n^2), 최선의 경우(O(n) (이미 정렬된 경우)
    • 공간 복잡도 : O(1)
    • 특징 : 구현이 간단하지만 비효율적인 경우가 많다.
  • 선택 정렬
    • 개념 : 가장 작거나 큰 요소를 선택해 이를 배열의 앞쪽 또는 뒤쪽으로 이동
    • 시간 복잡도 : 항상 O(n^2)
    • 공간 복잡도 : O(1)
    • 특징 : 버블 정렬과 비슷하지만 교환 횟수는 적다.
  • 삽입 정렬
    • 개념 : 각 반복에서 요소를 이미 정렬된 배열 부분에 삽입
    • 시간 복잡도 : 최선의 경우O(n), 평균 및 최악의 경우(O(n^2)
    • 공간 복잡도 : O(1)
    • 특징 : 작은 데이터 세트에 효율적이며, 거의 정렬된 데이터에 매우 빠름
  • 퀵 정렬
    • 개념 : 분할 정복 알고리즘을 사용해 기준점을 기준으로 데이터를 분할, 그리고 각 부분을 재귀적으로 정렬
    • 시간 복잡도 : 평균 및 최선의 경우O(n log n), 최악의 경우(O(n^2)
    • 공간 복잡도 : O(log n) (재귀적 구현 시)
    • 특징 : 대부분의 경우 매우 빠른 정렬 알고리즘
  • 병합 정렬
    • 개념 : 분할 정복 방식을 사용해 데이터를 반으로 나누고, 각 부분을 정렬 후 병합
    • 시간 복잡도 : 항상 O(n log n)
    • 공간 복잡도 : O(n)
    • 특징 : 안정 정렬이며, 대규모 데이터 세트에 효율적
  • 힙 정렬
    • 개념 : 최대 힙 트리나 최소 힙 트리를 구성하여 정렬
    • 시간 복잡도 : 항상 O(n log n)
    • 공간 복잡도 : O(1)
    • 특징 : 추가 메모리를 거의 사용하지 않으며, 정렬된 데이터에 대해 좋은 성능을 보임

​

• 정렬 알고리즘의 선택 시 다음과 같은 요소를 고려해야 함
  • 데이터의 크기와 상태(이미 정렬되었는지 등)
  • 메모리 사용량
  • 안정성(동일한 값을 가진 요소의 상대적 순서가 정렬 후에도 유지되는지)
  • 평균, 최선, 최악의 경우에 대한 성능

---

완전 탐색

• 가능한 모든 경우의 수를 시도하며 해답을 찾는 가장 기본적인 알고리즘
• 모든 가능성을 체계적으로 검토하기 때문에 해답이 존재하면 반드시 찾을 수 있다.
• 특징
  • 단순성 : 알고리즘의 로직이 매우 단순하고 이해하기 쉽다.
  • 정확성 : 가능한 모든 경우를 확인하기 때문에, 어떻게든 해답을 찾을 수 있다.
  • 비효율성 : 경우의 수가 많을 땐 매우 비효율적일 수 있고, 시간이 오래걸린다

​

• 예시
  • 순차 탐색
    • 리스트에서 특정 값을 찾기 위해 처음부터 끝까지 차례대로 검사하는 방법
  • 넓이 우선 탐색
    • 그래프의 모든 노드를 체계적으로 탐색하는 방법 중 하나. 시작 노드에서 가까운 노드부터 차례대로 탐색
  • 깊이 우선 탐색
    • 그래프의 모든 노트를 체계적으로 탐색하는 방법 중 하나. 한 방향으로 가능한 깊게 노드를 탐색 후, 없으면 이전 분기점으로 돌아가 다른 방향의 노드를 탐색
  • 백트래킹
    • 모든 가능한 조합을 탐색하지만 유망하지 않은 조합을 발견하면 이전 단계로 돌아가 다른 가능성을 탐색. 완전 탐색의 개선 방법으로 불필요한 경우의 수를 줄여줌
  • 완전 순열
    • 주어진 요소들로 만들 수 있는 모든 순열을 나열
  • 조합
    • 주어진 요소들 중에 일부를 선택하는 모든 조합 나열

​

• 사용 시기
  • 경우의 수가 적어 모든 경우를 탐색할 수 있을 때
  • 복잡한 알고리즘을 사용하기에 문제의 크기가 작을 때
  • 문제의 해답을 반드시 찾아야 할 때
  • 해결법을 찾기 어려울 때 근본적인 방법으로 사용됨

​

• 시간 복잡도가 매우 높을 수 있어, 크기가 커지면 실행 시간이 기하급수적으로 증가할 수 있다. 따라서 기본적으로 사용하되 더 효율적인 알고리즘을 찾거나 최적화하여 사용하는 경우가 많다.

---

정수론

• 수학의 한 분야로 정수와 이와 관련된 연산에 대해 다룸
• 알고리즘에서 데이터 분석이나 숫자 관련 문제 해결에 필수적인 개념 제공
• 주요 주제는 암호학, 랜덤 수 생성, 알고리즘 효율성 향상 등 CS의 응용 분야에 사용
• 주요 개념들
  • 소수
    • 1과 자기 자신으로만 나눠지는 수(1 포함 x)
    • 소수 판별 및 생성, 소인수 분해 등 알고리즘 포함
  • 최대공약수
    • 두 개 이상의 공통된 약수 중 가장 큰 수
    • 유클리드 알고리즘이 유명한 GCD를 구하는 방법
  • 최소공배수
    • 두 개 이상의 공통된 배수 중 가장 작은 수
    • GCD를 이용해 효율적으로 계산 가능
  • 모듈로 연산
    • 나눗셈의 나머지에 대한 연산, 암호학에서 매우 중요한 역할
  • 확장 유클리드 알고리즘
    • GCD를 구하면서, 동시에 베주 항등식의 해를 찾는 알고리즘
    • 베주 항등식
      • 두 정수와 최대공약수 사이의 관계를 보여주는 항등식
  • 중국인의 나머지 정리
    • 여러 개의 서로소인 모듈에 대한 나머지가 주어졌을 때, 이를 만족하는 정수를 찾는 정리
  • 페르마의 소정리
    • 소수 p와 p로 나누어 떨어지지 않는 정수 a에 대해, a^(p-1)을 p로 나눈 나머지는 1이 된다는 정리
  • 오일러의 피 함수
    • 어떤 수보다 작거나 같은 양의 정수 중에 그 수와 서로소인 수의 개수를 나타냄

​

학습시간 : 10 ~ 25시