개발하는데 다 이유가 있겠지

배열(Array)

• 변수 : 한 개의 데이터를 저장하는 공간
• 배열 : 여러 개의 데이터를 저장하는 공간
• 방번호(index) : 0번방부터 n-1번방까지 존재함(배열 선언시 설정한 크기(n))

{
   // 배열 선언
   int arr[5];
   /*
   int : 배열에 담긴 데이터의 자료형
   arr : 배열 이름
   [5] : 데이터의 크기(5개의 데이터를 담을 수 있음)
   */
   
   // 데이터 주입(초기화)
   arr[0] = 1;
   arr[1] = 2;
   arr[2] = 3;
   
   // 배열 초기화
   int arr[5] = {1,2,3}
   /*
   데이터 주입과 동일한 내용
   배열의 크기는 5개인데 3개만 초기화를 해줬기 떄문에
   arr[3], arr[4]에는 쓰레기 값이 담겨있음
   !! 초기화를 해주지 않으면 쓰레기 값이 담김 !!
   */
}

배열의 선언, 데이터 주입 및 초기화

 

! 주의사항 !

1. C언어 특성상 배열의 크기보다 큰 인덱스(방번호)에 데이터를 넣으면 해당 주소에 데이터가 쓰여짐(기존 데이터가 있다면 덮어씀)
-> 에러로 막아주지 않음

2. int arr[-1] 출력해봤더니 (null) 출력되지만, [warray bound] 경고

2차원 배열

{
   int arr[행의 개수][열의 개수]
}

---

문자열

• 문자(char)들의 배열
• C언어에는 문자열(String)이 따로 없음(큰 따옴표 ""을 통해 초기화 가능)
• 널 문자(종단문자, '\0') 때문에 배열 크기를 글자 수보다 최소 1개 더 크게 선언
• 문자열 끝에는 반드시 널 문자(종단문자, '\0')가 들어가야 함
  • 널 문자가 생략된다면 쓰레기 값도 같이 출력될 수 있음
• 문자열은 문자(char)들의 배열이지만 방번호(index)로 입출력하지 않고 (%s)라는 변환문자를 사용해 편리함
• scanf를 통해 문자열을 입력받을 때는 &(참조 연산자)를 사용하지 않아도 됨
• strcpy() 함수를 이용해 원하는 문자열을 저장할 수 있음
  • strcpy(변수, "내용")

{
  char arr[20] = "hello"
  
  char arr[20] = {'h','e','l','l','o'}
}

 

❗️❗️불변성 : 기존 객체의 값을 바꾸는 것이 아닌 수정된 값을 가지는 새로운 객체를 만듦❗️❗️

---

반복문(Iteration)

while문

조건식이 True인 동안 반복되는 구조

while(조건문){
   실행문
}

 

작동방식

1. 조건문이 True인 동안 실행문을 실행

2. 실행문이 끝나면 다시 조건을 검사해서 조건이 False가 될 때까지 반복 진행

---

for문

for (초기식 ; 조건식 ; 증감식) {
   실행문
}

• 초기식 : 초기 데이터의 값을 지정함
• 조건식 : 종료 조건을 넣어서 반복을 제어
• 증감식 : 초기 데이터를 증가, 감소시킴

2중 for문

for (초기식; 조건식; 증감식){
   실행문 2;
   for (초기식; 조건식; 증감식){
      실행문 1;
   }
}

• 초기식에 변수를 다르게 지정(서로에게 영향을 주지 않게 하기 위해서)

---

do - while문

do{
   실행문
}while(조건문);

• 첫 실행문은 반드시 실행되고 이후 조건문이 True인 동안 반복

---

break, continue

조건문에서 사용되는 제어 문법

 

break : 반복문의 조건식과는 상관없이 무조건 반복을 중단시키는 역할(반복문 종료)

 

continue : 반복문을 종료시키지 않고 이번 과정을 생략하는 역할(다음 cycle로 넘어감)

---

재귀함수(recursion)

자기 자신을 재참조하는 함수 / 하나의 함수에서 자기 자신을 호출하여 작업을 수행

def factorial(num):
   if num <= 1;
   	return 1
   else :
   	return num * factorial(num)	# 자기 자신을 재호출함

 

! 주의사항 !

1. 작은 단위의 문제로 분할(동일한 작업이 가능한 크기)

2. 종료조건을 명확하게 걸어야 함

 

장점

1. 코드가 간결해져 가독성이 높음

 

단점

1. 함수를 호출할 때 스택 메모리에 쌓이게 되는데, 함수가 마지막으로 종료될 때까지 메모리를 사용하고 있어 성능이 떨어짐

2. 반복문이 성능이 좋은 경우가 많음

(반복문은 힙 메모리를 사용)

---

복잡도(Big O, 시간, 공간)

알고리즘의 성능을 나타내기 위한 척도

시간복잡도 / 공간복잡도 2가지로 이루어졌음

 

Big O 표기법(Big O Notation)

• 알고리즘의 효율성을 보여주는 표기법
• 알고리즘의 효율성을 상한선 기준으로 표시(최악의 경우로 표시)
• 영향력 없는 계수와 낮은 차수의 항과 상수는 무시

함수의 성능 비교

---

시간 복잡도(Time complexity)

• 알고리즘이 실행되고 종료될 때까지 걸리는 시간
• 알고리즘을 위해 필요한 연산 횟수

1. O(1) - Constant Time
   • 상수 시간
   • 입력 데이터의 크기에 상관없이 언제나 일정한 시간이 걸리는 알고리즘
   • 데이터가 얼마나 증가하든 성능에 영향을 거의 미치지 않음
   • 예) stack의 push, pop
2. O(log n) - Log Time
   • 로그 시간
   • 입력 데이터의 크기가 커질수록 처리 시간이 로그만큼 짧아지는 알고리즘
   • 데이터 10배 → 처리 시간 2배
   • 예) 재귀가 순기능으로 이루어질 경우, binary search 알고리즘, tree 형태의 자료구조 탐색
3. O(n) - Linear Time
   • 선형 시간
   • 입력 데이터의 크기에 비례해 처리 시간이 증가하는 알고리즘
   • 데이터 10배 → 처리 시간 10배
   • 예) 1차원인 for문이 대표적
4. O(n log n) - Log linear Time
   • 로그 선형 시간
   • 데이터가 많아질수록 처리 시간이 로그만큼 더 늘어나는 알고리즘
   • 데이터 10배 → 처리 시간 20배
   • 예) 병합/퀵/힙 정렬
5. O(nⁿ) - Quadratic/Cubic Time
   • 이차/삼차 시간
   • 데이터가 많아질수록 처리시간이 급수적으로 늘어나는 알고리즘
   • 데이터 10배 → 처리 시간 100배
   • 예) 이중 for문, 삽입/거품/선택 정렬
6. O(2ⁿ) - exponential Time
   • 지수 시간
   • 데이터가 많아질수록 처리시간이 기하급수적으로 늘어나는 알고리즘
   • 예) 피보나치 수열, 재귀가 역기능할 경우

---

공간 복잡도(Space complexity)

• 알고리즘이 실행되고 종료될 때까지 사용하는 메모리의 크기
• 알고리즘을 위해 필요한 메모리 공간

공간 복잡도에 영향을 미치는 요소

• 변수
• 자료 구조(Data structure)
• 함수 호출(Function call)
• 할당(Allocation)

---

📝 알고리즘 풀기 전 대략 계산방법

• 일반적으로 1억번 연산이 1초정도 걸리므로 시간 제한 초수 * 1억으로 연산 횟수 생각
• 위에서 계산한 가능 연산 횟수를 초과하지 않으면 됨
• 최대 입력 데이터 수를 보고 대략적으로 가능한 시간복잡도를 파악해 구상

 

[참조]

https://blog.chulgil.me/algorithm/

https://suzzeong.tistory.com/104