문제 설명 문자열 str이 주어질 때, str을 출력하는 코드를 작성해 보세요.

제한사항 1 ≤ str의 길이 ≤ 1,000,000 str에는 공백이 없으며, 첫째 줄에 한 줄로만 주어집니다.

제출

str = input()
print(str)

2. a와 b 출력하기

문제 설명 정수 a와 b가 주어집니다. 각 수를 입력받아 입출력 예와 같은 형식으로 출력하는 코드를 작성해 보세요.

제한사항 -100,000 ≤ a, b ≤ 100,000

제출

a, b = map(int, input().strip().split(' '))
print("a =", a\n"b =", b)

3. 문자열 반복해서 출력하기

문제 설명 문자열 str과 정수 n이 주어집니다. str이 n번 반복된 문자열을 만들어 출력하는 코드를 작성해 보세요.

제한사항 1 ≤ str의 길이 ≤ 10 1 ≤ n ≤ 5

제출

a, b = input().strip().split(" ")
print( a * int(b))

4. 대소문자 바꿔서 출력하기

문제 설명 영어 알파벳으로 이루어진 문자열 str이 주어집니다. 각 알파벳을 대문자는 소문자로 소문자는 대문자로 변환해서 출력하는 코드를 작성해 보세요.

제한사항 1 ≤ str의 길이 ≤ 20 str은 알파벳으로 이루어진 문자열입니다.

제출

a = input().strip()
# 1. 함수 사용 
print(a.swapcase())

# 2 반복문 사용
for i in a:
    if i.isupper():
        print(i.lower(), end='')
    else:
        print(i.upper(), end='')

5. 특수문자 출력하기

문제 설명 다음과 같이 출력하도록 코드를 작성해 주세요.

출력 예시 !@#$%^&*('"<>?:;

제출

print("!@#$%^&*(\\\'\"<>?:;")
# print(r'!@#$%^&*(\'"<>?:;')

데이터를 안전하고 편하고 빠르게 보관 데이터 베이스는 거대하고 복잡한 데이터를 다루기 위해

👀 본질

• 데이터 베이스를 어떻게 입력하고 출력할 것인가
• 입력은 데이터의 생성, 수정, 삭제

• CRUD

💡데이터 베이스는 파일과 달리 프로그래밍 언어로 데이터를 추가, 수정, 삭제하고 읽을 수 있다 = 🎉 자동화 가능 🎉

✏️ 데이터 베이스 랭킹 확인 2023 기준 관계형 DB가 압도적 https://db-engines.com/en/ranking

Oracle: 대기업 등에서 사용, 고비용 MySQL: 오픈소스, 관계형DB + 개인, 소기업, 데이터의 신뢰성 중요도가 낮은 경우 MongoDB: 관계형X

2️⃣ MySQL 서론

데이터베이스의 목적

관계형 데이터베이스: 데이터를 표 형태로 정리 WEB + MySQL -> 폭발적 성장

✏️ 스프레드시트 VS 데이터베이스

DB는 컴퓨터 언어로 제어가 가능!! -> 대화하듯 하기에 자유롭고 다양한 활용

MySQL의 구조

🌱 표(table) > 그룹화 > 데이터베이스(database) 🌱 스키마: 서로 연관된 표들을 서로 그룹화 할 때 사용하는 일종의 폴더 > 데이터베이스 서버에 저장

MySQL 서버 접속

cd /usr/local/mysql/bin

bin ./mysql -u root -p

🌱 -u: root라는 사용자로 접속 🌱 -p: mysql이 비밀번호를 물어보도록

MySQL 스키마의 사용

🌱 DB 생성: mysql> CREATE DATABASE 스키마이름;

🌱 DB생성 확인: mysql> SHOW DATABASES; -> +--------------------+ | Database | +--------------------+ | information_schema | | mysql | | opentutorials | | performance_schema | | sys | +--------------------+

🌱 DB 사용 선언: USE opentutorials; -> Database changed

MySQL과 테이블 구조

📍SQL = Structured Query Language

• 정규화, 요청, 공통에 약속에 따른 언어

📍Table

• table, 표
• column, 열 -> 데이터의 타입
• row, record, 행 -> 데이터 자체

3️⃣ MySQL 테이블의 생성

🌱 mysql 문법에 따라 표 생성

mysql> CREATE TABLE topic( 👉 topic이라는 표에 저장 id INT(11) NOT NULL AUTO_INCREMENT, 👉 column이름, int형(숫자를 몇자리까지 노출시킬 것인지), 값이 없는 걸 허용X, id값이 자동으로 +1 title VARCHAR(100) NOT NULL, 👉 column이름, VARCHAR=char형(100), 값이 없는 걸 허용X description TEXT NULL, created DATETIME NOT NULL, author VARCHAR(15) NULL, profile VARCHAR(200) NULL, PRIMARY KEY(id)); 👉 성능, 중복 방지(식별자로 메인 KEY라는 뜻)

-> Query OK, 0 rows affected, 1 warning (0.02 sec)이 뜨면 성공!!

🌱 생성 확인

mysql> SHOW TABLES; -> +-------------------------+ | Tables_in_opentutorials | +-------------------------+ | *topic * | +-------------------------+

mysql> DESC topic; -> +-------------+--------------+------+-----+---------+----------------+ | Field | Type | Null | Key | Default | Extra | +-------------+--------------+------+-----+---------+----------------+ | id | int | NO | PRI | NULL | auto_increment | | title | varchar(100) | NO | | NULL | | | description | text | YES | | NULL | | | created | datetime | NO | | NULL | | | author | varchar(15) | YES | | NULL | | | profile | varchar(200) | YES | | NULL | | +-------------+--------------+------+-----+---------+----------------+

🌱 CHEAT SHEET

https://www.mysqltutorial.org/mysql-cheat-sheet.aspx

4️⃣ MySQL CRUD

INSERT

🌱 Create: data를 추가

mysql> INSERT INTO topic (title,description,created,author,profile) VALUES('MySQL','MySQL is...',NOW(),'egoing','developer');

-> Query OK, 1 row affected (0.01 sec) = 1개의 row가 영향을 받았다

🌱 Lead: 추가 data 확인

mysql> SELECT *FROM topic;

SELECT

https://www.w3schools.com/mysql/mysql_select.asp

🌱 테이블 모든 data 출력 SELECT *FROM topic;

🌱 특정 column만 출력 SELECT id,title,created,author FROM topic;

🌱 조건 설정 SELECT id,title,created,author FROM topic WHERE author='egoing'; -> 특정 데이터

SELECT id,title,created,author FROM topic WHERE author='egoing' ORDER BY id DESC; -> 역정렬

UPDATA

👉 Oracle is에만 ...이 없다 수정해보자

UPDATE topic SET description='Oracle is...', title='Oracle' WHERE id=2;

💡WHERE로 어떤 데이터를 수정할지 지정해주지 않으면 전부 바뀌는 참사가...

DELETE

👉 id가 1인 데이터를 삭제해보자 DELETE FROM topic WHERE id=1;

💡WHERE로 어떤 데이터를 수정할지 지정해주지 않으면 전부 삭제되는는 대대대참사가...

✏️ 관계형 데이터베이스의 필요성

중복되는 데이터를 가진 하나의 표를 분산 저장하지만 하나의 표로 보도록 👉 분할 저장, 합쳐서 보기

✏️ 테이블 분리하기

🌱 테이블 이름 수정 RENAME TABLES topic TO topic_backup;

🌱 기초 데이터 입력

✏️ JOIN_관계형 데이터 베이스

JOIN 👉 분리된 각각의 독립적인 테이블을 읽을 때 마치 하나의 테이블로 저장된 것처럼 보이도록 해준다

✔️ topic-author_id와 author-id를 연관짓고 싶다 ✔️ topic테이블을 모두 출력하는데 author_id와 같은 값을 가진 author의 행을 가져와 topic 테이블에 넣어(합성해줘)

SELECT * FROM topic LEFT JOIN author ON topic.author_id = author.id; ->

✔️ id 명칭 수정

🌟 JOIN을 통해 모든 테이블 사이 관계를 만들 수 있다 -> 원하는 테이블 생성 하나를 바꾸면 공통되는 특징을 가진 모든 테이블의 데이터를 수정할 수 있다

✏️ MySQL 클라이언트

database server

database client <--> database server

client(MySQL)가 명령어를 통해 database server를 제어, 제공

MySQL 클라이언트: GUI방식로!

리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 차례대로 확인하는 방법

👉 리스트에 특정 값의 원소가 있는지, 리스트 자료형에서 특정한 값을 가지는 원소의 개수를 세는 count() 메서드를 이용할 때 등 자주 사용

👉 O(N)의 시간복잡도

순차 탐색 소스코드

def search(n, target, arr):
    #각 원소를 하나씩 확인
    for i in range(n):
        if arr[i] == target:
            return i + 1 #인덱스가 0부터 시작하니 +1

input_data = input().split()
n = int(input_data[0])
target = input_data[1]

arr = input().split()

print(search(n, target, arr))

✏️ 이진 탐색

찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교하여 원하는 데이터를 찾는 방법

👉 정렬된 상태의 데이터에서만 사용

재귀 함수 이진 탐색 소스코드

def search(arr, target, start, end):
    if start > end:
        return None
    mid = (start + end) // 2
    if arr[mid] == target:
        return mid
    elif arr[mid] > target:
        return search(arr, target, start, mid - 1)
    else:
        return search(arr, target, mid + 1, end)

n, target = list(map(int, input().split()))
arr = list(map(int, input().split()))

result = search(arr, target, 0, n - 1)
if result == None:
    print("원소가 존재하지 않습니다.")
else:
    print(result + 1)

👉 중간 지점을 구하기 위해 (start + end) // 2 👉 몫만 구하기 위해 // 몫 연산자 사용

반복문 이진 탐색 소스코드

def search(arr, target, start, end):
    while start <= end:
        mid = (start + end) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] > target:
            end = mid - 1
        else:
            start = mid + 1

n, target = list(map(int, input().split()))
arr = list(map(int, input().split()))

result = search(arr, target, 0, n - 1)
if result == None:
    print("원소가 존재하지 않습니다.")
else:
    print(result + 1)

✏️ 실전 문제

부품 찾기

이 문제는 이진 탐색, 계수 정렬, 집합 자료형을 이용해 여러가지 방법으로 해결할 수 있다.

이 세 방법 모두 해결 아이디어는 target리스트를 반복문으로 돌리며 n리스트에 있는지 확인하면 된다.

📍 이진 탐색

해당 값이 없다면 결과값으로 return None을 하고 결과값이 None이라면 no를 출력하도록 한다. 이때 줄바꿈을 하지 않도록 end=' '코드를 사용한다.

📍 계수 정렬

arr이라는 리스트에 100001길이를 만들어 주고 부품 번호를 입력 받아 리스트에 기록한다. 그리고 arr에 손님의 부품 번호가 기록되어 있다면 yes를 출력한다.

📍 집합 자료형

arr을 입력 받을 때 set(map(int, input().split())) 를 사용해 특정 데이터가 존재하는지 검사한다. 이 소스코드가 셋 중 가장 간결함에서는 우수하다.

떡볶이 떡 만들기

처음에 가장 큰 데이터부터 -1을 하며 가장 카운트를 하고 큰 데이터가 중복일 경우 중복 데이터 모두 -1을 하는 방법으로 반복하며 카운트 수가 손님이 원하는 값과 일치할 때 리턴하는 함수를 만들어야 하나 고민했지만 매우 복잡해 보였고 이진 탐색을 이용하면 아래처럼 해결된다.

👉 절단기의 높이는 1부터 10억까지의 정수이다. 이처럼 큰 수를 보면 당연히 이진 탐색을 떠올려야 한다!!

중간점을 초기값으로 잡고 손님이 받을 값을 계산 -> 넘치거나 부족하면 상황에 따라 중간점 조절

이렇게 반복하며 손님이 원하는 값과 일치할 때의 중간점을 리턴한다.

이런 파라메트릭 서치 유형은 이진 탐색을 재귀보다 반복문을 이용해 구현하면 더 간결하게 풀 수 있다.

n, m = list(map(int, input().split()))
arr = list(map(int, input().split()))
start = 0
end = max(arr)
result = 0

while start <= end:
    total = 0
    mid = (start + end) // 2
    for x in arr:
        if x > mid:
            total += x - mid
    if total < m:
        end = mid - 1
    else:
        result = mid
        start = mid + 1

print(result)

전체 소스코드 중 잘랐을 때 떡의 양을 계산하는

for x in arr:
        if x > mid:
            total += x - mid

의 결과를 m과 비교하며 결과에 따라 mid값을 조절한다.!

💡이전에 적었던 정렬 알고리즘 글입니다┏ (゜ω゜)=☞ 이번 글은 파이썬 코드 위주로 적을 것 정렬 알고리즘 개념, 장점, 단점 요약글

아래의 코드는 오름차순 정렬을 기준으로 작성했다.

내림차순 정렬은 오름차순 정렬을 수행하는 알고리즘을 반대로 수행하면 된다. 또한 파이썬에서는 특정한 리스트의 원소를 뒤집는 메서드를 제공한다. 리스트를 뒤집는 연산은 O(N)의 시간복잡도를 가진다.

✨선택 정렬

입력 중 최솟값을 찾아 맨 앞에 있는 데이터와 바꾸고 그 다음으로 작은 값을 찾아 두 번째 데이터와 바꾸는 과정을 반복

arr = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]

for i in range(len(arr)):
    min_index = i #가장 작은 원소의 인덱스
    for j in range(i + 1, len(arr)):
        if arr[min_index] > arr[j]: #더 작은 원소 발견 시
            min_index = j #j를 최솟값 인덱스로
    arr[i], arr[min_index] = arr[min_index], arr[i] #swap

print(arr)

👉 가장 작은 데이터를 앞으로 보내는 과정을 n-1번 반복하면 정렬이 완료

✨삽입 정렬

정렬된 부분과 정렬되지 않은 부분을 나누어 본다. 특정한 데이터가 정렬된 부분 중 적절한 위치를 찾는 과정을 반복.

arr = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]

for i in range(1, len(arr)):
    for j in range(i, 0, -1):
        if arr[j] < arr[j - 1]: #정렬된 리스트에서 왼쪽으로 이동
            arr[j], arr[j - 1] = arr[j - 1], arr[j] #swap = 왼쪽 이동
        else: #본인 자리에서 멈추기
            break

print(arr)

👉 이미 정렬된 상태의 리스트 안에서 데이터가 이동하므로 자기보다 작은 데이터를 만난다면 더이상 이동할 필요가 없으므로 그 자리에 삽입

✨퀵 정렬

기준값인 피벗을 설정한 후 큰 수와 작은 수를 비교 교환한 후 리스트를 반으로 나누는 즉 정렬 -> 나누기 -> 정렬 -> 나누기 과정을 반복하는 알고리즘이다. 병합정렬과 달리 추가적인 임시 리스트를 필요로 하지 않는다.

퀵 정렬 소스코드 1_비교 교환 횟수 중점

arr = [5, 7, 9, 0, 3, 1, 6, 2, 4, 8]

def quick_sort(arr, start, end):
    if start >= end:  # 원소가 1개인 경우 리턴(재귀 함수 종료 조건)
        return arr
    pivot = start
    left = start + 1
    right = end
    while left <= right:
        # 피벗보다 큰 값을 찾을 때까지
        while left <= end and arr[left] <= arr[pivot]:
            left += 1  # left 이동
        # 피벗보다 작은 값을 찾을 때까지
        while right > start and arr[right] >= arr[pivot]:
            right -= 1  # right 이동
        if left > right:  # 엇갈렸다면 작은 값을 피벗과 교체
            arr[right], arr[pivot] = arr[pivot], arr[right]
        else:  # 엇갈리지 않았다면 큰 값과 작은 값 교체
            arr[left], arr[right] = arr[right], arr[left]
    # 분할 이후 재귀 호출로 피벗 기준 왼, 오 리스트 정렬
    quick_sort(arr, start, right - 1)
    quick_sort(arr, right + 1, end)


quick_sort(arr, 0, len(arr) - 1)
print(arr)

퀵 정렬 소스코드 2_파이썬의 장점을 살린 코드(직관적)

arr = [5, 7, 9, 0, 3, 1, 6, 2, 4, 8]

def quick_sort(arr):
    if len(arr) <= 1: #원소가 하나 남았다면 리턴
        return arr
    pivot = arr[0] #피벗은 첫 번째 원소
    tail = arr[1:] #피벗을 제외한 리스트
    #조건에 맞게 나누며 정렬
    left_side = [x for x in tail if x <= pivot] #분할된 왼쪽 부분 리스트
    rigjt_side = [x for x in tail if x > pivot] #분할된 오른쪽 부분 리스트
    # 재귀 호출
    return quick_sort(left_side) + [pivot] + quick_sort(rigjt_side)

print(quick_sort(arr))

👉 left, right 처럼 따로 인덱스 값을 이동하며 비교하지 않고 반복문을 이용하며 두 부분 리스트로 나눠 정렬

✨계수 정렬

#모든 원소는 0 혹은 양의 정수라고 가정
arr = [5, 7, 9, 0, 2, 5, 0, 3, 1, 6, 2, 4, 8, 8, 8, 6]
#모든 범위를 표현하는 리스트 선언(모든 값은 0으로 초기화)
cnt = [0] * (max(arr)+1) #0이 있을 수 있으므로 가장 큰 수+1

for i in range(len(arr)):
    cnt[arr[i]] += 1 #각 데이터에 해당하는 인덱스 값 1 증가

for i in range(len(cnt)): #인덱스이 데이터 수 만큼 출력
    for j in range(cnt[i]):
        print(i, end='')

👉 계수 정렬은 0, 999999 두 수만 있는 경우 심각한 비효율성을 초래한다. 즉 항상 사용할 수 있는 정렬 방법은 아니고 동일한 값을 가지는 데이터가 여러 개 등장할 때 적합하다.

데이터의 크기가 한정, 데이터가 많이 중복인 상태일수록 유리

실전 문제

💻 위에서 아래로

n = int(input())
num_list = []
for _ in range(n):
    num_list.append(int(input()))

num_list.sort(reverse=True)

for i in num_list:
    print(i, end=' ')

파이썬 기본 정렬 라이브러리를 사용

💻 성적이 낮은 순서로 학생 출력하기

n = int(input())
arr = []
for _ in range(n):
    input_data = input().split() #이름, 점수 입력 받기
    arr.append(input_data[0], int(input_data[1])) #점수 데이터 형 변환

arr = sorted(arr, key=lambda student: student[1]) #key(점수) 기준으로 정렬

for student in arr: #이름 출력
    print(student[0], end=' ')

👉 학생 정보를 (이름, 점수)로 묶은 뒤 점수 데이터를 key로 오름차순 정렬

💻 두 배열의 원소 교체

n, k = map(int(input().split()))
a = list(map(int, input().split()))
b = list(map(int, input().split()))

a.sort() #오름차순 정렬
b.sort(reverse=True) #내림차순 정렬

for i in range(k):
    if[i] < b[i]: #b가 더 크다면 교환
        a[i], b[i] = b[i], a[i]
    else: #a의 원소가 더 크거나 같다면 탈출
        break

print(sum(a)) #a의 합 출력

👉a, b를 가각 오름차순, 내림차순으로 정렬하고 조건에 맞다면 k번 교환

해결 방법

k번째를 삭제할 때 그 이전의 원소를 리스트의 뒤로 보내며 이 과정을 반복하면 된다. 이 규칙을 생각하는 건 쉬웠는데 소스 코드로 옮길 때 많은 방법 중에서 고민했다.

원형 큐를 만들까... 그냥 큐를 하면 더 간단하겠네... 어떤 함수를 써야하나... 직접 원소를 뒤로 보내야 하나...

그래서 반복문으로 ✨원소를 직접 뒤로 보내는 방법과 ✨rotate()함수로 덱을 돌리는 방법 2가지를 써보았다.

제출

** 💡 원소를 직접 뒤로 보내기 **

import sys
from collections import deque
input = sys.stdin.readline

from collections import deque
n, k = map(int, input().split())
s = deque([])
#1~n으로 덱 생성
for i in range(1, n + 1):
    s.append(i)

print('<', end='')
#s가 존재하는 동안 반복
while s:
    for i in range(k - 1): #k 이전 원소들 뒤로 보내기
        s.append(s[0])
        s.popleft()
    print(s.popleft(), end='') # k번째 원소 삭제, 출력
    if s:
        print(', ', end='') #쉼표 출력

print('>')

💡 함수 사용

import sys
from collections import deque
input = sys.stdin.readline

n, k = map(int,input().split())
s = deque([x for x in range(1,n+1)]) #리스트컴프리헨션

removed = []
while circle:
    s.rotate(-(k-1)) #k이전 원소들을 뒤로 보내기
    removed.append(s.popleft()) #출력할 리스트에 삭제값 삽입
print(f'<{", ".join(map(str,removed))}>')

✨ .ratate() 함수 함수 안에 양수라면 뒤에 있던 게 앞으로, 음수는 앞에 있던 게 뒤로 이동한다.
rotate함수 더보기

나코더 기장 재민이는 동아리 회식을 준비하기 위해서 장부를 관리하는 중이다.

재현이는 재민이를 도와서 돈을 관리하는 중인데, 애석하게도 항상 정신없는 재현이는 돈을 실수로 잘못 부르는 사고를 치기 일쑤였다.

재현이는 잘못된 수를 부를 때마다 0을 외쳐서, 가장 최근에 재민이가 쓴 수를 지우게 시킨다.

재민이는 이렇게 모든 수를 받아 적은 후 그 수의 합을 알고 싶어 한다. 재민이를 도와주자!

해결 방법

이 문제는 0을 입력 받으면 후입선출을 하는 스택 문제이다. 스택 형태로 코드를 짜고 append(), pop() 함수를 조건에 맞게 작동되게 하면 해결된다. 숫자를 입력 받음과 동시에 정수가 0인지 판별하도록 했다.

제출

k = int(input())
num_list = []
for _ in range(k):
    num = int(input())
    if num == 0: #0이라면 최근 삽입 값 삭제
        num_list.pop()
    else:
        num_list.append(num) #0이 아니라면 삽입

print(sum(num_list))

탐색이란 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정이다. 그 중 DFS/BFS를 대표적인 알고리즘으로 꼽을 수 있는데 이를 이해하려면 스택, 큐, 재귀함수를 알아야한다.

스택, 큐

스택: 후입선출 *파이썬의 append()와 pop()함수로 삽입, 삭제

큐: 선입선출

from collection import deque
queue = deque()
queue.append(5)
queue.append(6)
queue.popleft()

👉파이썬에서는 collection 모듈에서 제공하는 deque 자료구조를 활용하자.

재귀함수

재귀함수 자기 자신을 다시 호출하는 함수이다. 이때 재귀함수 없이 해결할 수 있는 정료 조건을 꼭 명시해야 한다. 무한 루프에 빠지지 않게 하기 위해서이다.

✨재귀함수는 내부적으로 스택 자료구조와 동일하다. 따라서 스택 자료구조를 활용해야하는 상당수 알고리즘은 재귀 함수를 이용해서 표현할 수 있다.

• 코드가 점화식을 그대로 표현하여 직관적이다.

• 무한루프, 스택오버플로우를 주의해야 한다.

탐색 알고리즘 DFS/BFS

그래프 표현

프로그래밍에서 그래프는 인접 행렬, 인접 리스트 2가지 방식으로 표현할 수 있다.

🎉인접 행렬: 2차원 배열로 각 노드가 연결된 형태를 기록. 연결이 되어 있지 않은 노드끼리는 무한의 비용이라고 작성.

INF = 999999999 #무한의 비용 선언
graph = [
    [0, 7, 5]
    [7, 0, INF]
    [5, INF, 0]
]
print(graph)

🎉인접 리스트: 리스트로 그래프의 연결 관계를 표현.

• C++, JAVA의 경우 별도의 라이브러리를 제공하지만 Python에서는 기본 리스트 자료형이 append()와 메소드를 제공. 즉 단순히 2차원 리스트를 이용.

  # 행이 3개인 2차원 리스트로 인접 리스트 표현
  graph = [[] for _ in range(3)]
  # 노드 0에 연결된 노드 정보 저장(노드, 거리)
  graph[0].append((1, 7))
  graph[0].append((2, 5))
  # 노드 1에 연결된 노드 정보 저장(노드, 거리)
  graph[1].append((0, 7))
  # 노드 2에 연결된 노드 정보 저장(노드, 거리)
  graph[1].append((0, 5))
  print(graph)

💡위 두 방식은 어떤 차이가 있을까?

메모리 측면에서 인접 행렬 방식은 모든 관계를 저장, 인접 리스트는 연결된 정보만 저장 👉 특정한 노드의 연결 유무: 인접 행렬이 더 빠름 👉 특정한 노드와 연결된 모든 인접 노드를 순회: 인접 리스트가 더 빠름

DFS 깊이 우선 탐색

그래프에서 깊은 부분을 먼저 탐색하는 알고리즘

• 스택 자료구조에 기초한다는 점에서 구현이 간단
• 데이터가 n개인 경우 O(n)의 시간이 소요
• 최대한 멀리있는 노드를 우선으로 탐색

#DFS 메서드 정의
def dfs(graph, v, visited):
    #현재 노드를 방문 처리
    visited[v] = True
    print(v, end=' ')
    #현재 노드와 연결된 다른 노드를 재귀적으로 방문
    for i in graph[v]:
        if not visited[i]:
            dfs(graph, i, visited)

#각 노드가 연결된 정보를 리스트 자료형으로 표현(2차원 리스트)
graph = [
    [],
    [2, 3, 8],
    [1, 7],
    [1, 4, 5],
    [3, 5],
    [3, 4],
    [7],
    [2, 6, 8],
    [1, 7]
]

#각 노드가 방문된 정보를 리스트 자료형으로 표현(1차원 리스트)
visited = [False] * 9

#정의된 DFS 함수 호출
dfs(graph, 1, visited)

BFS 너비 우선 탐색

그래프에서 가까운 노드부터 탐색하는 알고리즘

• 큐 자료구조를 이용하여 인접한 노드를 반복적으로 큐에 넣음
• deque라이브러리 사용
• 일반적인 경우 수행시간은 DFS보다 좋은 편

from collections import deque

#BFS정의
def bfs(graph, start, visited):
    #큐 구현을 위해 덱 라이브러리 사용
    queue = deque([start])
    #현재 노드 방문 처리
    visited[start] = True
    #큐가 빌 때까지 반복
    while queue:
        #큐에서 하나의 원소를 뽑아 출력
        v = queue.popleft()
        print(v, end=' ')
        #해당 원소와 연결된, 아직 방문하지 않은 원소들을 큐에 삽입
        for i in graph[v]:
            if not visited[i]:
                queue.append(i)
                visited[i] = True

#각 노드가 연결된 정보를 리스트 자료형으로 표현(2차원 리스트)
graph = [
    [],
    [2, 3, 8],
    [1, 7],
    [1, 4, 5],
    [3, 5],
    [3, 4],
    [7],
    [2, 6, 8],
    [1, 7]
]

#각 노드가 방문된 정보를 리스트 자료형으로 표현(1차원 리스트)
visited = [False] * 9

#정의된 DFS 함수 호출
bfs(graph, 1, visited)

실전문제

✨음료수 얼려 먹기

n, m = map(int, input().split())
ice_graph = []
for _ in range(n):
    ice_graph.append(map(int, input()))

def dfs(x, y):
    #범위를 넘어가면 종료
    if x <= -1 or x >= n or y <= -1 or y >= m:
        return False
    if ice_graph[x][y] == 0: #방문하지 않았다면
        ice_graph[x][y] = 1 #방문 처리하고 상하좌우 재귀호출
        dfs(x+1, y)
        dfs(x-1, y)
        dfs(x, y+1)
        dfs(x, y-1)
    return False #이미 1이라면 종료

cnt = 0
#dfs 반복문으로 실행
for i in range(n):
    for j in range(m):
        if dfs(n, m) == True:
            cnt += 1

print(cnt)

모든 노드를 방문해야 하니 깊이 우선 탐색을 사용했다.

재귀 호출로 상하좌우를 탐색하고 모든 조건을 통과해 True를 리턴 받으면 cnt에 1을 더하여 마지막으로 총 cnt 값을 출력하는 코드이다.

✨미로 탈출

from collections import deque

n, m = map(int, input().split())
graph = []
for _ in range(n):
    graph.append(list(map(int, input())))

#4방향 정의
dx = [-1, 1, 0, 0]    
dy = [0, 0, -1, 1]

#BFS 소스코드
def bfs(x, y):
    queue = deque()
    queue.append((x, y)) #시작점 인큐
    #큐가 빌 때까지 반복
    while queue:
        x, y = queue.popleft() #x, y에 각각 1 대입
        for i in range(4): #4방향에 반복
            nx = x + dx[i]
            ny = y + dy[i]
            if nx < 0 or ny > 0 or nx >= n or ny >= m: #범위 밖이면 무시
                continue
            if graph[x][y] == 0: #0이면 무시
                continue
            if graph[x][y] == 1:
                graph[nx][ny] = graph[x][y] +1 #기존 x,y 좌표의 값에 1을 더한 값을 대입
                queue.append((nx, ny)) #인큐
    return graph[n-1][m-1] #반복문이 끝나면 n,m 좌표의 값을 리턴(인덱스는 0부터 시작이므로 -1)

print(bfs(0, 0)) 

이 문제는 최단 거리를 구해야 하므로 bfs 너비 우선 탐색을 사용했다.

다음 노드로 이동할 때 그 노드의 데이터 값을 +1하며 마지막 종점에 달했을 때 데이터 값을 리턴하면 이동한 횟수를 리턴하게 되는 것이다.

완전한 비동일계 대학에 다니다가 코로나 녀석의 영향으로 비대면 강의 + 대학의 장점인 다양한 활동의 기회가 사라짐 등을 이유로 휴학을 했다. o(=•ェ•=)m 대학 생활 시절 좋은 기회로 학부 동기들과 나갔던 대회에서 공과 학생의 아이디어를 보고 IT분야에 관심이 생겼고, 내가 원하는 가치를 만들어낼 수 있다는 성취감이 좋아 개발자라는 꿈이 생겼다.

이후 기술 박람회에 참가하거나 생전 처음 아두이노를 만져보고 여러 언어를 접하며 웹도 만들어보며 공부했지만 역시나 혼자 공부하면서 부족함을 아주아주 많이 느꼈다.

팀 프로젝트 경험도 쌓고 싶고 같은 공부를 하며 관련 주제로 얘기하는 그런 소속감을 원했달까...?😏 또한 컴퓨터에 관련해 기초 전공 지식부터 쌓고 싶었다..! 기초는 매우 중요하니까요.

하지만 나에게 주어진 시간은 6달.. 전공 지식이라곤 쥐뿔도 없는 상황에서 편입 시험까지 준비하는 것보다는 토익 + 전공 면접 전형으로 최대한 내 의지를 보여주자 생각했다. 전적 대학 성적이 4.3으로 나쁘지 않았고 스토리텔링을 잘 하면 비동일계지만 오히려 좋을 수도 있지 않을까란 자신감..이..있었다..🙄

그래서 경상대(면접, 토익), 금오공대(토익), 창원대(면접), 부경대(면접, 토익), 계명대(면접), 경남대, 동의대 를 적었다. 전적대학성적은 모든 대학이 포함

💻 편입 계획, 공부 순서

토익 -> 면접 질문 예상지 만들기 -> 예상지를 기반으로 전공 공부 -> 면접 연습

✨ 중요한 전공 과목: 자료구조, C언어

편입 면접은 본 대학의 1,2학년 과정 수료한 만큼의 실력이 있을까를 평가하지 않을까라는 내 추측으로 그러면 C언어로 자료구조 공부는 필수겠다 싶었다.

그리고 독편사 카페, 유튜브 등등으로 최애애대한 모든 면접 질문을 긁어 모으고 추가해서 질문지를 만든 후 채웠다.

📃책은 생능출판의 C언어로 쉽게 풀어쓴 자료구조를 회독했다. C언어 문법 간단히 공부 후 보는 걸 추천^.^ !! 자료구조, 알고리즘 정리 쏘 굿

비동일계다보니 최대한 많이 준비해서 아는 질문을 받도록 하자 싶어 예상 질문을 많이 준비했었다. 정작 받은 질문은 비슷비슷했지만 =￣ω￣= 편입 준비하며 얻은 게 많아서 이 1~2달의 공부가 정말.. 소중해..

반복 또 반복하며 내 것이 되도록 이해하는 게 중요! 달달 외우지 말고 코드를 직접 짜보며 이해..❤

!오류가 있을 수 있습니다! 👇👇

🎉 전공 면접 예상 질문

데이터구조와 알고리즘이란?

“알고리즘”은 어떤 문제를 해결하기 위해 컴퓨터가 수행해야 하는 것들입니다. 자연어, 흐름도, 의사코드, 프로그래밍 언어와 같은 방법으로 기술할 수 있습니다. 모든 명령어들의 집합이 알고리즘이 되는 것은 아니고 “0개 이상의 입력과 1개 이상의 출력이 있어야 한다. 종료되어야 한다. 모든 명령이 실행 가능해야 한다.”와 같은 몇 가지 규칙이 있습니다. ++종류는 정렬 알고리즘, 탐색 알고리즘 등이 있습니다.

“데이터구조”는 데이터를 정리하는 것입니다. 데이터를 어떻게 정리하느냐에 따라서 바로 속도에 영향을 주기 때문에 데이터구조의 종류는 정말 다양합니다. 어떤 데이터구조는 “정렬”, 또 다른 구조는 “검색”에 최적화 되어 있듯 어떤 작업에 어떤 데이터구조를 쓰는지가 중요하며 적절한 자료구조의 선택은 효율적인 알고리즘이 됩니다.

검색 알고리즘(C언어 구현 코드)에 대해?

어떤 알고리즘을 어떤 자료구조와 사용하느냐에 따라 시간복잡도, 효율성에 큰 영향을 미칩니다. 검색 알고리즘에는 이진검색 알고리즘(Binary Search)와 선형검색 알고리즘(Linear Search)이 있습니다.

선형검색 알고리즘은 0부터 순서대로 차근차근 찾는 방법입니다. 배열이 크고 찾는 요소가 배열의 마지막에 있다면 시간이 길어지게 됩니다. 이걸 선형 시간복잡도라고 합니다. 인풋이 많을수록 수행하는 시간 또한 증가한다는 뜻입니다.

이런 문제점을 해결한 게 이진검색 알고리즘입니다. 이진검색은 모든 배열에 쓸 수는 없고 정렬된 배열에서만 사용할 수 있습니다. 왜냐하면 배열의 처음과 끝, 집합의 전체 길이를 알아야 하기 때문입니다. ‘이진’은 반으로 쪼개는 것을 의미합니다. 정렬의 정중앙에서 우리 목표 숫자보다 큰지, 작은지 본 후 크다면 왼쪽으로 가는 것입니다. 10까지 있는 경우는 3번, 20까지 있는 경우는 4번 즉 배열의 크기가 2배가 되더라도 필요한 스텝은 1번 늘어나게 됩니다. 1만개의 데이터가 있는 경우 선형검색은 최대 1만번 스텝을 요구하지만 이진검색의 경우 최대 14번의 스텝을 요구합니다. 이렇게 큰 배열의 경우 이진검색이 효과적입니다. 이러한 이진검색의 탐색 능력과 연결리스트를 결합하면 이진 탐색 트리라는 자료구조로 자료의 입력, 삭제까지 효율적으로 할 수 있습니다.

+정렬된 데이터의 경우:　색인순차탐색, 보간 탐색

정렬 알고리즘(C언어 구현 코드)에 대해?

정렬이란 레코드들을 킷값의 순서로 재배열하는 것입니다. 지금까지 정렬 알고리즘이 개발되었지만 모든 경우에 최상의 성능을 보여주는 알고리즘은 존재하지 않습니다. 따라서 프로그램에 가장 효율적인 알고리즘을 선택해야 합니다.

단순하지만 비효율적인 방법엔 삽입 정렬, 선택 정렬, 버블 정렬 등이 있고 복잡하지만 효율적인 방법엔 퀵 정렬, 힙 정렬, 합병 정렬, 기수 정렬 등이 있습니다.

정렬 알고리즘에서 ** 안정성** 이란 동일한 킷값을 갖는 레코드가 여러 개 존재할 경우 이들의 상대적 위치가 정렬 후에도 바뀌지 않는 것을 의미합니다. 안정성이 요구되는 경우에는 삽입 정렬, 버블 정렬, 합병 정렬 등을 사용해야 합니다.

선택 정렬은 입력 배열에서 최소값을 찾은 다음 배열의 첫 번째 요소와 교환하는 과정을 반복하는 알고리즘입니다. 이 절차를 숫자 개수-1 만큼 되풀이하면 전체 숫자가 정렬됩니다. 즉 O(N^2)의 시간 복잡도를 가집니다. 선택 정렬의 장점은 이동 횟수가 미리 결정된다는 점입니다. 그러나 안정성을 만족하지 않는다는 단점이 있어 같은 값을 가진 레코드의 상대적 위치가 변경될 수 있습니다.

삽입 정렬은 두 번째 요소부터 시작하여 그 앞의 요소들과 비교하여 삽입할 위치를 지정한 후 요소들을 뒤로 옮기고 지정한 자리에 요소를 삽입하는 알고리즘입니다. 선택 정렬과 유사하게 배열을 정렬된 부분과 정렬되지 않은 부분으로 나누어서 사용합니다. 삽입정렬의 시간 복잡도는 입력 자료의 구조에 따라 달라집니다. 자료가 이미 정렬되어 있는 경우엔 O(N)이지만 입력 자료가 역순인 최악의 경우엔 O(N^2)의 시간 복잡도를 가집니다. 삽입 정렬은 안정적인 방법으로 레코드의 수가 작거나 대부분이 이미 정렬되어 있다면 효율적이라고 할 수 있습니다.

버블 정렬은 인접한 2개의 레코드를 비교하여 크기가 순서대로 되어있지 않으면 서로 교환하는 비교-교환 과정을 전체 숫자가 정렬될 때까지 반복하는 알고리즘입니다. 모든 싸이클마다 모든 레코드를 교환해야 합니다. 즉 버블 정렬의 시간 복잡도는 O(N^2)이고 순서에 맞지 않은 요소를 인접한 요소와 교환한다는 문제점이 있기에 단순성에 불구하고 거의 쓰이지 않습니다.

쉘 정렬은 삽입 정렬이 어느정도 정렬된 배열에 대해서는 빠른 것에 착안한 알고리즘입니다. 쉘 정렬은 전체 리스트를 한 번에 정렬하지 않기 때문에 삽입 정렬의 이웃한 위치로만 이동하는 단점을 보완했습니다. 즉 요소들이 최종 위치에 있을 가능성이 높아진다는 장점이 있다는 것입니다. 리스트를 연속적이지 않은 열러 개의 부분리스트로 분류하는데 여기서 부분리스트는 정렬해야 할 리스트의 K번째 요소를 추출한 것이고 그 K는 곧 간격이 됩니다. 각 부분리스트를 삽입 정렬을 이용해 정렬하는 과정을 반복하는데 각 회전마다 간격K은 절반으로 줄고 이 간격이 1이 될 때까지 반복합니다. 쉘 정렬의 시간 복잡도는 최악의 경우에는O(N^2)이지만 평균적인 경우에는 O(N^1.5)로 나타납니다.

합병 정렬은 분할 정복 알고리즘을 기반으로 합니다. 문제를 작은 2개의 문제로 분리 후 각각을 해결하여 모아서 원래의 문제를 해결하는 것인데 분리된 문제가 충분히 작지 않다면 분할 정복 방법을 다시 적용합니다. 안정적인 정렬 방법이라는 장점이 있고 레코드를 배열로 구성하면 임시 배열이 필요하다는 단점이 있습니다. 이 단점은 레코드를 연결리스트로 구성하여 링크 인덱스 값만 변경하는 방법으로 보완할 수 있습니다. 즉 연결리스트를 사용한다면 합병 정렬은 퀵 정렬보다 효율적일 수 있습니다. 최악, 평균, 최선의 경우 모두 O( )의 시간 복잡도를 가집니다.

퀵 정렬은 분할 정복 알고리즘의 하나로 빠른 속도를 자랑합니다. 합병 정렬과 달리 리스트를 비균등하게 분할한다는 특징이 있습니다. 분할 시 리스트 안의 한 요소를 선택하는데 이를 피벗이라고 합니다. 그리고 피벗을 중심으로 2개의 리스트로 나누는데 이때 partition함수를 사용합니다. 작은 요소는 왼쪽 큰 요소는 오른쪽 리스트로 옯겨지게 됩니다. 분활된 부분 리스트에 대해 순환호출을 이용하여 부분리스트의 크기가 0이나1이 될 때까지 정렬을 반복합니다. O( )로 속도가 빠르고 추가 메모리 공간을 필요로 하지 않는다는 장점이 있지만 정렬된 리스트에 대해서는 퀵 정렬의 불균형 분할에 의해 시간이 오히려 더 걸린다는 단점이 있습니다. 그래서 피벗 선택 시에 데이터의 중간값을 선택하여 리스트를 균등하게 분할 수 있게 하기도 합니다.

힙 정렬은 최대, 최소 힙 트리를 구성해 정렬하는 방법입니다. 내림차순 정렬을 위해서는 최대 힙 오름차순 정렬을 위해서는 최소 힙을 구성하면 됩니다. 내림차순을 기준으로 정렬해야 할 요소들로 완전 이진 트리 형태의 최대 힙을 만듭니다. 그 다음 요소를 힙에서 하나씩 꺼내 배열의 뒤에서부터 저장하는 것입니다. 그러면 배열 요소들은 값이 증가되는 순서로 정렬됩니다. 힙 트리의 높이는 완전 이진 트리이므로 log입니다. 즉 시간 복잡도 또한 O( )가 됩니다. 힙 정렬은 가장 큰 값, 작은 값 몇 개만 필요한 경우 유용한 알고리즘입니다.

기수 정렬은 입력 데이터에 대해 어떤 비교 연산도 하지 않고 데이터를 정렬하는 알고리즘입니다. 기수란 수의 자릿수를 의미합니다. 즉 자릿수를 비교하여 정렬합니다. 한 자리 정수들을 정렬한다고 가정할 때 십진수에서는 0~9까지 10개의 버킷을 만든 후 데이터를 각 자릿수의 값에 맞게 넣습니다. 이렇게 비교 연산은 하지 않고 버킷에 넣고 빼는 동작만 하게 됩니다. 여러 자리로 이루어진 경우 각 자릿수를 따로 사용하여 정렬하면 10개의 버킷으로 2자리수도 정렬할 수 있습니다. 이땐 낮은 자릿수부터 정렬한 다음 높은 자릿수를 정렬하면 됩니다. 각각의 버킷은 큐로 구현되어야 합니다. 즉 숫자를 집어 넣는 연산은 큐의 삽입연산, 숫자를 읽는 연산은 삭제 연산으로 대치합니다. 정렬에 기초한 방법들은 이론적 하한선 O( )를 깰 수 없는데 기수 정렬은 O(N)으로 비교적 빠른 알고리즘입니다. 비교 연산을 하지 않아 빠르고 안정성을 가진다는 단점이 있지만 추가적인 메모리 공간을 필요로 하며 데이터 타입이 한정적이라는 단점도 있습니다.

계수 정렬은 각 수가 몇 번 나오는지를 알고 이를 앞부터 순서대로 정렬하는 알고리즘입니다. 즉 정렬할 배열의 원소와 숫자의 수를 세고 누적시킨 후 그 값들을 정렬된 배열의 인덱스로 사용합니다. 기수 정렬처럼 원소 간의 비교를 하지 않는 알고리즘입니다. 다만 다음 조건을 만족하는 리스트에만 적용이 가능합니다. 1. 리스트 내의 모든 원소는 정수이어야 합니다. 즉 음수, 소수는 불가능. 2. 값의 범위가 메모리 사이즈를 넘는 것처럼 너무 크지 않아야 합니다. 조건이 생기는 이유는 배열의 인덱스를 사용하여 데이터를 저장하기 때문입니다. 배열의 인덱스는 양수만 존재하고 값이 너무 커지면 메모리 영역을 너무 많이 할당하여 문제가 생기기 때문입니다. 배열의 크기를 n, 가장 큰 수를 k라 할 때 n이 k보다 큰 경우 O(N)의 시간 복잡도로 효율적입니다. 그리고 비교 연산자를 사용하지 않으며 안정성을 가진다는 장점이 있습니다. 그러나 정렬할 때 추가적인 메모리가 필요한 점, 가장 큰 숫자에 영향을 받아 메모리 공간이 낭비될 수 있다는 점과 같은 단점이 있습니다.

재귀 알고리즘이란?

재귀 알고리즘이란 하나의 함수에서 자기 자신을 다시 호출하여 작업을 수행하는 알고리즘입니다. 재귀 호출은 자기가 자신을 계속해서 호출하므로, 끝없이 반복되게 됩니다. 따라서 함수 내에 재귀 호출을 중단하도록 조건이 변경될 명령문을 반드시 포함해야 합니다. 이를 지키지 않으면 무한루프에 빠져 에러를 발생시킬 것입니다. 그리고 함수를 명확하게 정의해야 합니다. 함수의 인자로 어떤 것을 받을지, 어디까지 계산 후 자기 자신에게 넘겨줄지를 의미합니다. 모든 재귀함수는 반복문으로도 구현할 수 있습니다. 재귀를 적절하게 사용하면 코드가 간결해진다는 장점이 있지만 수행 시간과 기억 공간의 측면에서는 비효율적인 경우가 많습니다. 무한 재귀호출의 위험성도 있습니다. 그래서 반복문으로 간단하게 해결 가능한 문제라면 반복문으로 구현하는 것도 좋은 방법입니다. 피보나치 수열, 이진 트리 알고리즘, 하노이 탑 등에서 재귀 알고리즘을 사용합니다. ++ 피보나치, 하노이탑 알고리즘(C언어 구현 코드)

자료구조?

배열 연결리스트 스택 큐 트리 힙 해시 테이블 그래프

ADT 추상적 자료구조란?

스택, 큐는 일종의 “규칙”입니다. 자료구조가 스택인지 큐인지 구분하기 위한 규칙이고 이런 것들을 “추상적 자료구조”라고 부릅니다. ADT는 자료구조의 한 형태인데 자료구조의 방법이 코드로 정의된 것이 아니라 그 구조의 행동 양식만 정의된 것입니다. 즉, 규칙들만 이해하면 스택, 큐형의 자료구조를 만들 수 있습니다. 추상형 자료 구조의 장점은 구현에 대한 세부 사항은 숨기고 인터페이스만을 제공함으로서 정보 은닉이 가능하다는 것, 핵심 기능을 미리 선언함으로 코드의 재사용성과 가독성을 증가시킨다는 것 그리고 내부 구현을 사용자에게 맡김으로서 사용의 유연함을 제공한다는 다형성이 있습니다.

스택, 큐, 추상적 자료구조란?

스택, 큐는 일종의 “규칙”입니다. 자료구조가 스택인지 큐인지 구분하기 위한 규칙이고 이런 것들을 “추상적 자료구조”라고 부릅니다. ADT는 자료구조의 한 형태인데 자료구조의 방법이 코드로 정의된 것이 아니라 그 구조의 행동 양식만 정의된 것입니다. 즉, 규칙들만 이해하면 스택, 큐형의 자료구조를 만들 수 있습니다.

스택과 큐는 순서를 가지는 선형 자료구조라는 공통점이 있습니다.

스택은 배열에서 요소를 추가하거나 삭제할 때 상단에서 차례로 할 수 있습니다. 즉 “LiFo” 후입선출이라고도 합니다. 스택의 함수를 몇가지 말해보자면 가장 위에 있는 항목을 삭제하는 pop(), 가장 위에 데이터를 쌓는 push(), 가장 위의 항목을 반환하는 top(), 스택이 비어 있을 때 true를 반환하는 isEmpty()가 있습니다. +배열, 연결리스트로 구현 시 차이점

큐는 줄을 서서 기다리는 것처럼 가장 먼저 추가된 요소가 가장 먼저 삭제됩니다. 삭제 연산만 수행되는 곳을 프론트, 삽입연산만 이루어지는 곳을 리어라고 합니다. 즉 “FiFo” 선입선출이라고도 합니다. 큐는 선형 큐, 원형 큐, 덱으로 구분할 수 있습니다. 선형 큐는 전단, 후단의 값이 초기값 -1에서 증가만 하기 때문에 배열의 앞부분이 비어 주기적으로 요소들을 이동시켜 줘야 하는데 이런 단점을 보완한 것이 원형 큐입니다. 원형큐에선 전단, 후단의 개념이 조금 달라집니다. 초기값은 0으로 같으나 전단은 큐의 첫 번째 요소의 하나 앞을, 후단은 마지막 요소를 가리킵니다. 즉 두 값이 같으면 원형 큐가 비어있다는 뜻이고 전단이 후단보다 하나 앞에 있다면 포화 상태를 뜻 합니다, 덱은 양쪽에서 모두 삽입, 삭제 연산이 가능한 구조입니다. 이런 특징 때문에 연결리스트로 구현시 스택이나 큐보다 더 복잡합니다. 하나의 노드에서 선행노드, 후행노드를 가리키는 포인터 변수를 가져야하기 때문입니다. 이런 구조를 이중 연결 리스트라고 합니다. +배열, 연결리스트로 구현 시 차이점

언제 큐를 쓰고, 스택을 쓰는지가 중요합니다. 뒤로가기 버튼을 누르면 스택을 사용한 것입니다. 왜냐하면 뒤로가기를 누른다는 것은 웹페이지 히스토리 스택의 맨 위에서 한 페이지를 가져오는 것이기 때문입니다. 그리고 후위 표기법을 계산할 때, 깊이 우선 탐색 등에 사용합니다. 큐는 프로그래머의 도구로서 폭넓게 사용됩니다. 컴퓨터의 CPU와 키보드, 모니터와 같은 주변기기 사이엔 속도 차이가 생기는데 CPU를 효율적으로 사용하기 위해 버퍼 역할을 하도록 큐를 사용합니다. 그리고 너비 우선 탐색을 구현할 때, 기수 정렬의 버킷 구현 시에도 사용합니다.

후위 표기식이란?(스택)

수식을 표기하는 방법에는 전위, 중위, 후위가 있습니다. 연산자의 위치를 기준으로 나누는데 후위 표기식은 연산자가 피연산자의 뒤에 있는 것입니다. 컴파일러는 주로 후위 표기식을 사용합니다. 프로그래머가 수식을 중위 표기법으로 작성하면 컴파일러는 이것을 후위 표기법으로 변환한 후 스택을 이용하여 계산합니다. 컴파일러에서 후위 표기법을 선호하는 이유는 괄호가 필요 없고 연산자의 우선순위를 생각할 필요가 없기 때문입니다. 이미 식 자체에 우선순위가 포함되어 있기 때문입니다. 후위 표기식을 스택을 이용하여 계산하는 방법은 우선 수식을 왼쪽에서 오른쪽으로 스캔하여 피연산자면 스택에 저장하고 연산자면 필요한 만큼의 피연산자를 스택에서 꺼내 계산 후 결과값을 스택에 저장하면 됩니다. 중위표기식을 후위표기식으로 바꾸는 방법은 우선 피연산자는 출력을 하고 연산자는 스택에 넣습니다. 그리고 스택의 탑이 자신보다 우선순위가 낮은 연산자를 만날 때까지 pop하고 자신을 담습니다. 여는 괄호를 만나면 닫는 괄호를 만날 때까지 스택에서 연산자를 빼고 두 괄호를 모두 삭제합니다.

배열

배열은 동일한 타입의 데이터를 저장하며 고정된 크기를 가진 자료구조입니다. 연속적인 메모리 공간이 할당되고 인덱싱이 되어 있어 인덱스 번호로 데이터에 빠르게 접근할 수 있습니다.

많은 자료를 읽어야 한다면 배열이 효율적이지만 검색, 추가, 삭제할 때는 다릅니다. 배열을 하나하나 다 찾아야 하기에 시간이 더 걸리기 때문입니다. 이렇게 순서대로 0부터 끝까지 차근차근 찾는 것을 선형 검색이라고 합니다.

리스트

배열로 구현된 리스트(Array List) 는 순차적인 메모리 공간이 할당되므로 리스트의 순차적 표현이라고도 합니다. 구현이 간단하고 속도가 빠르다는 장점이 있지만 리스트의 크기가 고정된다는 단점이 있습니다. 만약 데이터를 추가하고 싶은데 남은 공간이 없다면 문제가 발생하는 것입니다. 기존의 배열을 복사하여 더 큰 배열에 넣는 것은 CPU 시간을 낭비합니다. 또한 리스트의 중간에 있는 데이터의 삭제, 삽입은 기존의 데이터를 이동해야 합니다. 이런 점을 보완한 자료구조가 연결 리스트입니다.

연결 리스트(Linked list) 는 각 노드가 데이터와 포인터를 가지고 연결되어 있는 방식으로 데이터를 저장하는 자료구조입니다. 포인터는 다음 노드를 가리키고 이 포인터 변수의 주소도 따로 존재합니다. 첫 번째 노드를 알아야 전체의 노드에 접근할 수 있는데 첫 노드를 가리키는 변수를 헤드 포인터라고 합니다. 연결리스트는 크기가 제한되지 않고 중간에서 쉽게 삽입, 삭제를 할 수 있는 유연한 리스트를 구현할 수 있습니다. 하지만 구현이 복잡하고 임의의 항목을 추출하려고 할 땐 배열의 방법보다 오래 걸린다는 단점이 있습니다. 연결의 방향에 따라 단순 연결리스트, 원형 연결리스트, 이중 연결리스트로 나뉩니다.

단순 연결리스트는 하나의 방향으로만 연결 되어 있고 마지막 노드의 값은 NULL값을 가리킵니다.

원형 연결리스트는 마지막 노드가 첫 번째 값을 가리킨다는 특징이 있습니다. 하나의 노드에서 모든 노드로 접근이 가능하고 헤드 포인터가 마지막 노드를 가리키기 때문에 리스트의 끝에 노드를 삽입할 때 특히 용이합니다. 멀티 플레이어 게임이나 원형 큐를 만들 때 사용합니다.

이중 연결 리스트는 선행노드, 후행노드에 대한 양방향 즉 두 개의 링크를 가지는 리스트입니다. mp3 재생 프로그램처럼 양방향 검색이 가능하다는 장점이 있지만 공간을 많이 차지하고 코드가 복잡해진다는 단점이 있습니다. 원형 연결 리스트와 혼합하여 많이 사용하는데 데이터를 가지고 있지 않은 헤드 노드를 추가해 삽입, 삭제 알고리즘을 간편하게 하기도 합니다.

트리

트리는 계층적인 자료를 표현하는 데 적합한 자료구조입니다. 인간의 의사구조 결정을 표현하는 결정 트리처럼 인공지능의 문제에도 트리가 사용 됩니다. 트리는 방향성이 있는 비순환 그래프라는 특징이 있습니다. 즉 루프나 사이클이 없습니다. 이 외에도 루트에서 어떤 노드로 가는 길은 유일하다, 노드가 N개인 트리는 항상 N-1개의 간선을 지닌다 등의 특징이 있습니다. 트리는 크게 일반트리와 이진트리로 구분할 수 있습니다.

일반적인 트리에서 각 노드들은 서로 다른 개수의 자식 노드를 가지므로 따라서 링크필드의 개수가 달라집니다. 이 방법은 노드의 크기가 고정되지 않는다는 문제점이 있습니다.

이진트리는 모든 노드가 2개의 서브트리를 가지고 있는 트리를 의미합니다. 모든 노드의 차수가 2이하이며 서브트리는 왼쪽, 오른쪽으로 순서가 존재합니다. 그리고 일반 트리와는 달리 노드를 하나도 가지지 않을 수 있습니다. 즉 공백 노드도 자식 노드로 취급하는 것입니다. 이진트리는 포화 이진 트리, 완전 이진 트리 등으로 나눌 수 있습니다.

포화 이진 트리는 트리의 각 레벨에 노드가 꽉 차있는 이진트리를 의미합니다. 레벨 단위로 왼쪽에서 오른 쪽으로 각 노드에 번호를 붙일 수 있습니다.

완전 이진 트리는 이와 달리 마지막 레벨에서는 노드가 꽉 차있지 않아도 되지만 어왼쪽부터 순서대로 채워져 있는 이진 트리입니다. 포화 이진 트리는 항상 완전 이진 트리지만 그 역은 성립하지 않습니다. 이진트리는 배열 또는 포인터를 이용해 표현할 수 있습니다. 배열을 이용하는 방법은 포화 이진 트리나 완전 이진 트리의 경우 많이 사용합니다. 이진 트리의 깊이가 k일 때 2^k-1개의 공간을 연속적으로 할당한 다음, 트리의 번호대로 노드들을 저장하는 것입니다. 일반 이진 트리의 경우 기억 공간의 낭비가 심해진다는 단점이 있지만 인덱스만 알면 노드의 부모나 자식을 쉽게 알 수 있다는 장점이 있습니다. 링크를 이용한 방법은 트리의 노드가 구조체로 표현되고 각 노드가 포인터를 가집니다. 이진트리의 경우 하나의 노드는 1개의 데이터 필드와 2개의 포인터 필드를 갖고 포인터로 부모노드와 자식노드를 연결합니다. 즉 루트노드를 가리키는 포인터만 있으면 트리 안의 모든 노드에 접근할 수 있다는 점에서 연결 리스트와 유사한데 연결 리스트는 1차원적인 구조라면 링크법으로 표현된 이진 트리는 2차원적인 구조라 할 수 있습니다.

이진 트리 순회?

표준적인 방법에는 전위, 중위, 후위 3가지 방법이 있습니다. 이는 루트, 왼쪽 서브트리, 오른쪽 서브트리 중 루트를 언제 방문하느냐에 따라 구분됩니다. 그리고 모든 서브트리에 대해 같은 알고리즘을 반복합니다. 전위 순회(VLR)는 루트를 먼저 반복한 후 왼쪽 오른쪽 서브트리를 방문합니다. 즉, 중위 순회(LVR)는 왼쪽 서브트리, 루트, 오른쪽 서브트리 순서이며 후위 순회(LRV)는 마지막으로 루트를 방문하는 것입니다. 만약 자식 노드를 먼저 방문해야하는 상황이라면 후위 순회를 사용하여야 합니다. 예를 들어 디렉토리의 용량을 계산할 때인데, 하위 디렉토리를 먼저 계산해야 현재의 디렉토리 용량을 알 수 있기 때문입니다. 이 외에도 표준적인 순회 방법은 아니지만 레벨 순회처럼 각 노드를 레벨 순으로 검사하는 방법도 있습니다. 지금까지 순회 방법은 스택을 사용했지만 레벨 순회는 큐를 사용한다는 특징이 있습니다.

이진 탐색 트리?

이진 트리 기반의 탐색을 위한 자료구조입니다. 모든 원소는 유일한 키를 가지고 왼쪽 서브트리의 키들은 오른쪽 서브트리보다 작다는 특징이 있습니다. 이러한 성질을 이용하여 탐색을 효율적으로 할 수 있는 것입니다. 이진 탐색 트리에서 특정한 키 값을 찾기 위해서는 먼저 주어진 탐색키 값과 루트 노드의 값을 비교합니다. 비교한 결과에 따라 과정이 나뉘는데 첫째, 비교한 결과가 같으면 탐색이 성공저그로 끝납니다. 둘째, 주어진 키 값이 루트 노드의 킷값보다 작으면 탐색은 왼쪽 자식을 기준으로 다시 실행합니다. 셋째는 그 반대 상황입니다. 이런 이진 트리에서는 균형을 유지하는 것이 매우 중요합니다. 균형 트리가 아닐 경우 같은 정수의 개수를 비교해도 비교 횟수에 차이가 생기고 탐색의 시간 복잡도가 높아지게 되기 때문입니다.

우선순위 큐?

데이터들이 우선순위를 가지고 순위가 높은 데이터가 먼저 나가는 자료구조입니다. 우선순위 큐는 사건을 시각을 우선순위로 하는 시뮬레이션 시스템 등에서 사용됩니다. 이는 구현하는 가장 효율적인 방법은 히프입니다. 히프는 완전 이진 트리의 일종으로 우선순위 큐를 위해 만들어진 자료구조입니다. 히프트리에서는 이진 탐색 트리와 달리 중복된 값을 허용합니다. 그리고 데이터들은 느슨한 정렬 상태를 유지합니다. 히프의 목적은 삭제 연산때 가장 큰 값을 즉 루트 노드를 찾는 것으로 전체를 정렬할 필요가 없기 때문입니다. 히프트리에는 두 가지 종류가 있습니다. 최대 힙, 최소 힙인데 최대 힙은 부모 노드의 킷값이 자식 노드의 킷값보다 크거나 같은 완전 이진 트리를 뜻하고 반대로 최소 힙은 부모 노드의 킷값이 자식 노드의 킷값보다 작거나 같은 완전 이진 트리를 뜻합니다.

그래프

그래프는 지도처럼 객체 사이의 연결 관계를 표현할 수 있는 자료구조입니다. 즉 선형리스트나 트리의 구조로는 어려운 복잡한 구조를 표현할 수 있습니다. 그래프는 정점과 간선들의 유한 집합이라 할 수 있습니다. 많은 그래프의 종류가 있는데 간선의 종류에 따라 나눈 경우에는 양방향으로 연결하는 경우 무방향 그래프, 방향성이 존재하는 경우엔 방향 그래프라 부릅니다. 간선에 가중치를 할당하면 가중치 그래프 또는 네트워크라 하며 통신망 사용 등 응용 분야가 다양합니다. 무방향 그래프에 있는 모든 정점쌍에 대해 항상 경로가 존재한다면 연결 그래프, 아닐 시엔 비연결 그래프라 합니다. 여기서 트리는 그래프의 특수한 형태로서 사이클을 가지지 않은 연결 그래프임을 알 수 있습니다.

그래프는 2차원 배열을 이용하거나 연결 리스트를 이용하여 표현할 수 있습니다. 2차원 배열인 인접 행렬의 경우 불리언 행렬로 간선의 존재 여부에 따라 0, 1로 표현하는 것입니다. 무방향 그래프의 경우 행렬은 대칭을 이루게 된다. 각각의 정점 연결을 동시에 의미하기 때문입니다. 따라서 배열의 상위 삼각이나 하위 삼각만 저장하면 메모리를 아낄 수 있습니다. 인접 행렬로 표현할 땐 간선의 수와 상관 없이 정점의 제곱수만큼의 공간이 필요하기 때문에 희소 그래프의 경우 적합하지 않습니다. 모든 간선의 수를 알아내려면 전체를 조사해야 하므로 n^2번의 조사가 필요하다는 단점이 있습니다. 하지만 어떤 두 정점을 연결하는 간선의 존재 여부는 O(1)시간에 즉시 알 수 있습니다. 인접 리스트는 각각의 정점에 인접한 정점들을 연결 리스트로 표현한 것입니다. 각 연결 리스트는 헤더 노드를 가지고 있고 이 헤더 노더들은 하나의 배열로 구성되어 있습니다. 따라서 정점의 번호만 알면 이 번호를 배열의 인덱스로 하여 각 정점의 연결 리스트에 쉽게 접근할 수 있습니다. 노드의 인접한 노드를 쉽게 찾을 수 있지만 간선의 존재 여부와 정점의 차수를 알기 위해서 정점의 차수만큼 시간이 필요하다는 단점이 있습니다. 희소 그래프의 경우 효율적으로 사용할 수 있습니다.

그래프 탐색?

그래프의 탐색은 하나의 정점으로부터 시작하여 차례대로 모든 정점들을 한 번씩 방문하는 것입니다. 그래프의 탐색 방법은 깊이 우선 탐색(DFS), 넓이 우선 탐색(BFS)이 있습니다. 깊이 우선 탐색은 시작점에서 다음 분기로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법입니다. 트리를 탐색할 때 시작점에서 한 방향으로 쭉 가다 더 이상 갈 수 없게 되면 가장 가까운 갈림길로 돌아가서 탐색을 진행하는 방법과 유사합니다. 구현하는 방법으로는 인접 행렬, 인접 리스트로 자신을 호출하는 순환 알고리즘 표현 또는 명시적인 스텍을 사용하여 인접한 정점들을 스텍에 저장하였다가 다시 꺼내는 방법이 있습니다. 깊이 우선 탐색은 모든 노드를 방문하고자 하는 경우 선택합니다. 너비 우선 탐색은 시작 점으로부터 가까운 정점을 먼저 방문하는 기법입니다. 너비 우선 탐색을 위해서는 가까운 정점을 차례로 저장후 꺼낼 수 있는 자료구조인 큐가 필요합니다. 알고리즘은 큐에서 정점을 꺼내서 정점에 방문한 후 인접 정점들을 큐에 추가합니다. 이 과정을 큐가 공백 상태가 될 때까지 계속하며 깊이 우선 탐색과 달리 재귀적으로 동작하지 않는다는 특징이 있습니다. 이러한 특징으로 두 노드 사이의 최단 경로를 찾고 싶을 때 사용이 가능합니다. 이 두 탐색방법은 희소 그래프의 경우 인접 행렬보다 인접 리스트를 사용하는 게 효율적이라는 공통점이 있습니다. 인접 리스트로 표현 시 전체 수행 시간이 O(정점+간선)이고 인접 행렬로 표현 시 O(정점^2)시간이 걸리기 때문입니다. +C언어 구현 코드

신장 트리

신장 트리는 트리의 특수한 형태로 모든 정점들이 연결되어 있어야하고 사이클을 포함해서는 안 되는 트리입니다. 따라서 n개의 정점을 n-1개의 간선으로 연결하게 되고 하나의 그래프에는 많은 신장 트리가 존재할 수 있습니다. 최소 연결 그래프로 회사 내 모든 전화기를 가장 작은 케이블을 사용하여 연결하는 방법 등의 문제에 적용이 가능합니다. 하지만 단순히 간선의 수 보다는 간선의 가중치가 중요할 경우도 많습니다. 최소 비용 신장 트리는 간선의 가중치 합이 최소인 신장 트리를 말합니다. 즉 모든 정점을 가장 작은 수의 간선과 비용으로 연결하는 것입니다. 여행지들을 모두 연결하면서 최소 거리가 되도록 하는 문제의 경우에 활용할 수 있습니다. 최소 비용 신장 트리를 구하는 방법으로는 Kruskal과 Prim의 알고리즘이 대표적으로 사용되고 있습니다.

Kruskal의 MST알고리즘은 탐욕적인 방법을 통해 네트워크의 모든 정점을 최소비용으로 연결하는 최적안을 구합니다. 탐욕적인 방법이란 매 선택마다 가장 좋은 것을 선택하는 방법으로 이 선택이 모이고 모여서도 최적이라는 보증이 없기에 반드시 검증을 해야합니다. Kruskal의 알고리즘은 다행히 이 증명이 되어 있습니다. 먼저 그래프의 간선들을 가중치의 오름차순으로 정렬한 후 각 단게에서 사이클을 이루지 않는 최소 비용의 간선을 선택합니다. 그리고 해당 간선을 현재의 MST집합에 추가합니다. 만약 사이클을 형성하면 그 간선은 제외됩니다. 여기서 주의할 점은 다음 간선을 이미 선택된 간선들의 잡합에 추가할 때 사이클을 생성하는지 체크해야 한다는 것입니다. 추가할 간선의 양 끝 접점이 같은 집합에 있다면 사이클을 생성하게 되는데 union-find 알고리즘을 통해 검사할 수 있습니다. 이 알고리즘을 이용하면 Kruskal의 알고리즘의 시간 복잡도는 간선들을 정렬하는 시간에 좌우됩니다. 희소 그래프의 경우 적합하다는 특징이 있습니다.

Prim의 MST알고리즘은 시작 정점에서부터 출발하여 신장트리 집합을 확장해나가는 즉 Kruskal은 간선을 기반으로 하지만 Prim은 정점을 기반으로 하는 알고리즘입니다. 시작 단계에서는 시작 정점만이 집합에 포합됩니다. 인접한 정점들 중 가장 낮은 가중치의 간선에 연결된 정점을 선택하여 집합을 확장합니다. 이런 과정을 트리집합이 n-1개의 간선을 가질 때까지 반복하면 됩니다. 주 반복문이 정점의 수만큼, 내부 반복문도 정점의 수만큼 반복하므로 O(n^2)의 시간 복잡도를 가지며 간선이 많이 존재하는 경우는 Prim의 알고리즘이 적절합니다. Kruskal의 알고리즘은 이전 단계에서 만들어진 신장 트리와 상관 없이 무조건 최저 간선을 선택하는 방법이라면 Prim의 알고리즘은 이전 단계에서 만들어진 신장 트리를 확장한다는 것에서 차이가 있습니다. +C언어 구현 코드

해시 테이블

해시 테이블은 Key Value 시스템을 이용하여 자료를 정리합니다. 자바스크립트에선 object, 파이썬에선 dictionary, 고에서는 map 등 여러 프로그래밍 언어에 존재합니다. 해시 테이블을 이용한 탐색을 해싱이라고 하는데 해싱에서는 자료를 저장할 때 배열을 사용합니다. 배열에선 요소의 위치를 알고 있다면 매우 빠르게 자료를 삽입하거나 꺼낼 수 있습니다. 해시 테이블이 빠른 이유는 해시 함수입니다.

해시 함수?

저장하고 싶은 key를 인덱스로 바꾼 후 그곳에 value가 저장되도록 합니다. 좋은 해시 함수이기 위해선 충돌이 적어야 하고, 해시함수 값이 해시테이블의 주소 영역 내에서 고르게 분포되어야하고 계산이 빨라야한다는 조건이 있습니다. 해시 함수엔 여러 종류가 있습니다. 제산 함수는 나머지 연산자(mod)를 이용하여 주소를 계산하는 방법입니다. 보통 해시테이블의 크기로 나누며 헤시테이블의 크기는 주로 소수 즉 자신과 1만을 약수로 가지는 수로 선택합니다. 해시 주소를 고르게 분포하기 때문입니다. 폴딩 함수는 주로 키가 해시테이블의 크기보다 큰 경우 사용합니다. 예를 들어 키는 32비트 해시 테이블의 인덱스는 16비트인 경우입니다. 폴딩 함수는 대표적으로 두 가지 방법이 있습니다. 하나는 이동폴딩으로 키를 여러 부분으로 나눈 값들을 더해 해시 주소로 사용하는 것이고 다른 하나는 경계 폴딩으로 키의 이웃한 부분을 거꾸로 더해 해시 주소로 사용하는 것입니다. 폴딩하지 않고 킷값의 일부만을 주소로 사용한다면 겹칠 가능성이 생기기 때문에 사용합니다. 중간 제곱 함수는 킷값을 제곱한 다음 중간의 몇 비트를 선택해 해시 주소를 생성하는 함수입니다. 키의 거의 모든 문자와 관련있기 때문에 몇 개의 문자가 같은 다른 키가 다른 해싱 주소를 가질 확률이 높아집니다. 비트 추출 방법은 해시 테이블의 크기가 2^k일 때 키를 이진수로 간주해 임의의 위치의 k개 비트를 해시 주소로 사용하는 것입니다. 숫자 분석 방법은 숫자로 구성된 키에서 각각의 위치에 있는 수의 특징을 알고 있을 때 유리합니다. 숫자 중 편중되지 않는 수들을 조합하여 해시 주소로 사용하는 방법인데, 예를 들어 학번의 경우 입학년도를 나타내는 부분은 가급적 사용하지 않고 나머지 수를 조합하는 것입니다. 마지막으로 기수 변환법은 주어진 키의 값을 다른 진법으로 변환하여 얻은 결과 값을 주소로 사용하는 방법입니다. 여기서 초과하는 높은 자리수는 절단합니다.

충돌? 개방주소법과 체이닝?

서로 다른 key에 대하여 해시 함수가 동일한 주소를 준 경우를 충돌이라고 합니다. 이런 충돌이 버킷의 슬롯 수보다 많이 발생하게 되면 더 이상 항목을 저장할 수 없는 오버플로우가 발생하게 됩니다. 만약 버킷 1개 당 1개의 슬롯만 가진다면 충돌이 곧 오버플로우를 의미합니다. 충돌을 효과적으로 해결하는 방법엔 개방주소법과 체이닝이 있습니다. 개방 주소법은 충돌이 일어난 항목을 해시 테이블의 다른 위치에 저장하는 것. 즉 비어있는 버킷을 찾는 방법입니다. 이 과정을 조사라고하는데 여러가지 방법의 조사가 있습니다. 선형 조사법은 충돌이 발생했을 때 비어있는 공간이 나올 때까지 순차적으로 조사하는 방법입니다. 만약 테이블의 끝에 도달하게 되면 다시 테이블의 처음으로 돌아가고 조사의 시작점에 도달하면 테이블이 가득 찬 것으로 판단합니다. 선형 조사법의 단점은 특정 해시값이 주변에 채워지는 일차 군집화 문제에 취약하다는 것입니다. 해시값 1이 여러번 나오는 경우 데이터가 연속되게 저장될 가능성이 높아지고 해시값 2,3이 나왔을 때 저장하려는 공간에 데이터가 있어 충돌이 일어나게 된다는 것을 의미합니다. 제곱 조사법, 이차 조사법은 탐사하는 폭이 고정폭이 아닌 제곱으로 늘어나는 부분에서 선형 조사법과 차이가 있습니다. 데이터의 밀집도가 선형 조사법보다 낮게 때문에 연쇄적 충돌의 확률을 줄일 수 있습니다. 마지막으로 이중 해싱, 재해싱은 해시 함수를 이중으로 사용하는 조사법입니다. 하나는 최초 해시를 얻을 때 나머지 하나는 충돌이 일어난 경우 탐사 폭을 얻기 위해서 사용합니다. 이 방법은 다른 조사폭을 제공하기 때문에 골고루 저장될 확률이 높아집니다.

체이닝은 충돌 문제를 삭제, 삽입 연산이 용이한 연결리스트로 해결합니다. 해시테이블의 구조를 변경하여 각 버킷이 하나 이상의 값을 저장할 수 있게 하는데 즉 한 번도 사용되지 않은 위치가 있어야만 탐색이 빨리 끝나는 선형조사법의 단점을 보완한 것입니다. 버킷 내에서 항목을 찾을 땐 연결리스트를 순차 탐색합니다.

이러한 이유 때문에 해시 테이블이 항상 상수 시간 즉 O(1)인 것은 아닙니다.(충돌이 있을 수 있고 그 경우 선형 검색을 해야함) 그래도 전반적인 평균의 경우에는 O(1)의 시간복잡도를 가집니다.

시간복잡도란?

알고리즘이 얼마나 빠르고 느린지 측정하는 방법입니다. 실제 시간을 측정하는 게 아니라 알고리즘을 이루고 있는 연산이 몇 번 수행되는지를 측정하는 것입니다. 빅오표기법은 함수의 상한값을 나타내 시간 복잡도를 효율적으로 표시합니다.

인덱스0 값 출력처럼 인풋이 10개든 100개라도 1번의 함수 실행 후 끝나는 경우 이 함수의 시간복잡도는 상수 시간이라고 할 수 있고 빅오표기법으로는 O(1)이라고 합니다.

이진검색처럼 인풋을 절반으로 나눠서 진행하는 경우 O(logN)의 시간복잡도를 가집니다. 인풋이 2배 커져도 스텝은 1번 증가하는 것입니다.

선형검색처럼 N개의 인풋에 N개의 스텝이 필요한 경우는 O(N)의 시간복잡도를 가집니다.

중첩 반복이 있는 경우 2차 시간이 발생하는데 이때의 시간복잡도는 인풋 N의 제곱이 됩니다. 즉 O(N^2)입니다.

많이 쓰이는 빅오 표기법을 순서대로 나열하자면 ++

Parameter와 Argument의 차이

매개변수(Parameter)는 함수와 메서드의 입력 변수 명이고 전달인자(Argument)는 함수와 메서드의 입력 값입니다.

C언어와 C++언어의 차이점

C언어는 절차지향 언어지만 C++은 객제지향 언어라는 차이점이 있습니다. 절차 지향 언어는 순차적으로 처리하여 프로그램 전체가 유기적으로 연결되어 있는 반면 객체지향 언어는 객체로 데이터와 메소드를 만들어 묶어 구현하는 방식입니다.

C언어에서는 같은 이름을 가진 함수가 존재할 수 없지만, C++에서는 가능합니다.(오버로딩, 오버라이딩).

C언어와 달리 C++에서는 namespace 즉 선언적 영역을 통해 이름 충돌 문제를 해결합니다.

C언어에서는 변수, 함수를 초기에 작성해야 하지만 C++에서는 중간에 어디서든 선언이 가능합니다.

C언어에서 표준 입출력은 scanf, printf이지만 C++에서는 cin, cout입니다. 그리고 동적 할당의 경우 C언어는 malloc, C++은 new입니다.

클래스(class)와 구조체(struct)의 차이점

클래스와 구조체는 연관있는 데이터를 하나로 묶는다는 기본 개념은 동일합니다. 구조체란 하나의 구조로 묶일 수 있는 데이터, 즉 변수들의 집합입니다. 클래스는 변수와 메소드들까지 함께 묶어둔 집합니다. 개발자가 중요하게 고려해야 할 성능개선을 위해선 이 둘의 차이점을 알고있는 것이 중요합니다.

구조체는 언제 생기고 사라질지 컴파일 단계에서 알 수 있기 때문에 메모리의 stack 공간에 할당되고, 클래스는 참조가 어디서 어떻게 될지 모르기 때문에 heap 공간에 할당합니다. Stack에서는 pop, push라는 하나의 명령어로 할당, 해제가 이루어지지만 Heap은 참조 계산도 해줘야 하므로 Stack보다 복잡합니다.

C에서도 함수포인터를 이용해 구조체를 클래스화 시킬수 있습니다.

객체지향(Object Oriented Programming), 절차지향(Procedural Programming)

절차지향,구조적 프로그래밍(C)은 초창기에 많이 사용한 방법으로 순차적 프로그래밍이라고도 합니다. 해야 할 작업을 순서대로 코딩합니다. 함수 단위로 구성되며 기능별로 묶어놓은 특징이 있습니다.컴퓨터의 처리구조와 비슷해 빠르다는 장점이 있지만 유지보수, 디버깅이 어렵다는 단점이 있습니다.

객체지향 프로그래밍(Java, C++, C#) 의 구성요소는 클래스와 객체입니다. 클래스를 활용하여 각각의 기능별로 구성이 가능하며, 이를 나중에 하나로 합쳐서 프로그램의 완성이 가능합니다. 객체지향 프로그래밍은 개발하려는 것을 기능별로 묶어 모듈화를 함으로써 같은 기능을 중복으로 연산하지 않거나 모듈을 재활용하기 때문에 유지보수에 유리합니다. 하지만 어떤 모듈에 있는 기능 하나만 필요하더라도 모듈 전체를 가져와야 하기에 프로그램 사이즈가 커질 수 있고 처리속도나 설계에 걸리는 시간적 측면에서 불이익이 있을 수 있습니다. 객체 지향의 중요한 특징은 캡슐화, 추상화, 다형성, 상속입니다.

즉 절차지향은 데이터 중심, 객체지향은 기능 중심이라 할 수 있습니다.

*단어 정리 1.캡슐화: 데이터와 알고리즘 코드가 하나의 묶음으로 정리된 것. 2.매소드: 메시지에 따라 실행시킬 프로시저로서 객체지향 언어에서 사용되는 것. 3.상속: 이미 작성된 클래스를 이어 받아서 새로운 클래스를 생성하는 기법으로 위에서 말한 기존 코드를 재활용해서 사용하는 것. 4.다형성: 하나의 이름(방법)으로 많은 상황에 대처하는 기법입니다. 개념적으로 동일한 작업을 하는 함수들에 똑같은 이름을 부여할 수 있으므로 코드가 더 간단.

프로세스와 스레드의 차이점

프로세스는 메모리 상에서 실행중인 프로그램을 말하며, 스레드는 이 프로세스 안에서 실행되는 흐름의 단위를 말합니다. 프로세스는 독립적인 공간(Code, Data, Stack, Heap의 구조)을 할당받아 사용하지만 스레드는 Stack만 따로 할당받고 Code, Data, Heap 영역은 같은 프로세스 내 다른 스레드들과 공유한다는 차이점이 있습니다.

스레드를 생성하는 방법과 장단점

자바에서 스레드를 생성하는 방법은 두 가지가 있습니다. 하나는 Thread클래스를 상속받아 run메소드를 오버라이딩 하는 것, 다른 하나는 Runnable 인터페이스를 구현하여 run 메소드를 정의하는 것입니다. 이 두 방법으로 만든 스레드는 run 메서드 코드의 실행의 부분에선 동일합니다. 다만 구현과정에서만 차이가 납니다. 객체지향 프로그래밍에서 상속은 부모의 기능을 물려받아 재사용하거나, 재정의를 하고 새로운 기능들은 추가하여 확장하는 것을 의미합니다. 하지만 자바의 다중상속이 불가능점을 생각하면 Thread 클래스의 run 메소드 하나때문에 상속기능을 사용하는 것은 비효율적입니다. 이를 해결하기 위해서 스레드 생성 시 반드시 구현해야 하는 run 메소드를 Thread 클래스와 분리하고 구현을 강제하는 인터페이스를 사용하는 것입니다. 이것이 바로 Runnable 인터페이스입니다. 만약, Thread 클래스의 또 다른 기능을 확장하거나 재정의를 해야할 경우라면 Runnable 인터페이스 대신 Thread 클래스를 상속하는게 더 효과적일 수 있습니다.

동기화(Synchronization)란 무엇이며 어떤 경우에 사용

동기화란 프로세스 또는 스레드들이 수행되는 시점을 조절하여 서로가 알고 있는 정보가 일치하는 것을 의미합니다. 예를 들어 P1이라는 프로세스가 A라는 값을 이용하여 어떤 문제를 해결하고자 하는데 그 사이에 P2라는 프로세스가 A의 값을 바꿔버린다면 프로그램은 우리가 원하는 값을 반환하지 않습니다. 이렇게 프로세스나 스레드가 동기화 없이 접근하는 것을 경쟁 상태라고하며, 이런 문제를 해결하는 것. 즉, 서로의 정보를 일치시키는 것을 동기화라고 합니다.
멀티 스레드에서 하나의 자료에 접근할 때 동기화를 사용합니다. (멀티 스레드란 하나의 프로세스 내에서 둘 이상의 스레드가 동시에 작업을 하는 것을 의미합니다.) 예를 들면 은행계좌에 있는 돈에 대해 동시에 출금 요청이 가능하다면 출금이 동시에 일어날 수 있기에 동기화를 하여 작업이 일어나는 중에는 다른 한쪽에서의 접근을 막아주어야 합니다.

포인터란?

포인터는 메모리의 주소값을 저장하는 변수입니다. 프로그램을 짜다 보면 어느 변수에 저장한 값을 여러 곳에 써야할 때가 있습니다. C언어에서 어느 함수에 변수가 인자로 주어질 때는 그 값이 복사되어 넘어갑니다. 즉, 메모리의 다른 어딘가에 그 크기만큼 중복된 값이 차지된다는 것입니다. 이렇게 메모리를 낭비하지 않고 주소만 보내줄 수 있도록 하는 것이 포인터입니다. 포인터를 이용하여 call by reference를 구현할 수 있습니다. 포인터 연산자는 해당 변수의 주소를 추출하는 주소연산자(&) 그리고 포인터가 가리키는 장소에 값을 저장하는 참조 연산자()가 있습니다. 참조 연산자는 포인터의 이름이나 주소 앞에 사용합니다. 포인터를 선언한 후 참조 연산자()를 사용하기 전에 포인터는 반드시 먼저 초기화되어야 합니다. 그렇지 않으면 의도하지 않은 메모리의 값을 변경하게 되기 때문입니다. 포인터는 값을 증가, 감소하는 등의 제한된 연산만을 할 수 있습니다. 포인터끼리의 덧셈, 곱셈은 아무런 의미가 없으며 포인터끼리의 뺄셈은 두 포인터 사이의 상대적 거리를 나타냅니다. 다양한 포인터의 종류로는 이중 포인터, void포인터, 함수 포인터, 널 포인터 등이 있습니다. 이중 포인터는 포인터 변수를 카리키는 포인터로 참조 연산자를 두 번 사용하여 표현합니다. void 포인터는 데이터 타입을 명시하지 않은 포인터입니다. 변수, 함수 등 어떠한 값도 가리킬 수 있지만 연산이나 참조와 같은 작업은 불가능합니다. 그러니 반드시 사용하고자 하는 타입으로 명시적 타입 변환을 해야합니다. 다음은 함수 포인터인데 프로그램에서 정의된 함수는 프로그램이 실행될 때 모두 메인 메모리에 올라가게 됩니다. 이때 함수의 이름은 메모리에 올라간 함수의 시작 주소를 가리키는 포인터 상수입니다. 이걸 함수 포인터라고 합니다. 함수를 또다른 함수의 인수로 전달할 때 유용하게 사용됩니다. 마지막 널 포인터는 0이나 NULL을 대입해 초기화한 포인터로 아무것도 가리키지 않는 포인터라는 뜻입니다.

Call by reference와 Call by value 차이점

함수에 인수를 전달하는 방법에는 크게 2가지가 있습니다. 값에 의한 전달과 참조에 의한 전달입니다. 값에 의한 전달은 인수로 전달되는 변수가 가지고 있는 값을 함수 내의 매개변수에 복사하는 방식입니다. 이렇게 복사된 값으로 초기화된 매개변수는 인수로 전달된 변수와 별개의 변수이고 함수 내에서 매개변수의 조작은 인수로 전달되는 변수에 영향을 주지 않습니다. 참조에 의한 전달은 해당 변수의 주소값을 전달합니다. 여기서 참조라는 개념이 포인터를 뜻합니다. 즉 함수의 매개변수에 인수로 전달된 변수의 원래 주소값을 저장하는 것입니다. 이 방식을 사용하면 인수로 전달된 변수의 값을 함수 내에서 변경할 수 있게 됩니다. 즉 C언어의 scanf함수호출도 call by reference 형태의 함수호출에 해당합니다.

Overloading과 Overriding의 차이점

Overloading 은 같은 이름을 가진 매소드를 여러개 정의하는 것을 의미합니다. 단 매개변수의 개수나 타입이 달라야합니다. 리턴 타입은 영향을 주지 않습니다. Overriding은 상속에서 나온 개념으로 상위 클래스의 매소드를 하위 클래스가 재정의 하는 것을 의미합니다. 매소드의 이름은 물론이고 파라미터의 개수, 타입도 동일해야합니다. 주로 상의 클래스의 동작을 하위 클래스에서 변경하기 위해 사용됩니다. 즉 오버로딩(Overloading)은 기존에 없던 새로운 메서드를 정의하는 것이고, 오버라이딩(Overriding)은 상속 받은 메서드의 내용만 변경 하는 것이다.

상속이란?

상속이란 부모 클래스와 자식 클래스 사이에서 기존의 클래스를 토대로 새로운 클래스를 만드는 방법입니다. C++에서 상속은 :(콜론)을 사용해 정의하며 정의된 클래스의 속성과 매소드를 가져옵니다. (JAVA에서는 extends) 상속은 추상화, 캡슐화와 더불어 객체 지향 프로그래밍을 구성하는 중요한 특징 중 하나입니다. 상속은 사용자에게 코드의 재활용성을 제공하며, 클래스 간의 계층적 관계를 구성함으로써 다형성의 문법적 토대를 마련합니다.

가상함수와 순수가상함수의 차이점

C++에서 가상 함수(virtual function)는 파생 클래스에서 재정의할 것으로 기대하는 멤버 함수를 의미합니다. 따라서 가상 함수는 반드시 재정의해야만 하는 함수가 아닌, 재정의가 가능한 함수를 가리킵니다. 이와는 달리 순수 가상 함수(pure virtual function)란 파생 클래스에서 반드시 재정의해야 하는 멤버 함수를 의미합니다. 이러한 순수 가상 함수는 일반적으로 함수의 동작을 정의하는 본체를 가지고 있지 않습니다. 따라서 파생 클래스에서 재정의하지 않으면 사용할 수 없습니다. 이는 함수만 있고 본체가 없다는 의미로 함수 선언부 끝에 "=0"을 추가합니다.

Abstract Class(추상 클래스)란?

C++에서는 하나 이상의 순수 가상 함수를 포함하는 클래스를 추상 클래스(abstract class)라고 합니다. 이러한 추상 클래스는 객체 지향 프로그래밍에서 중요한 특징인 다형성을 가진 함수의 집합을 정의할 수 있게 해줍니다. 즉, 반드시 사용되어야 하는 멤버 함수를 추상 클래스에 순수 가상 함수로 선언해 놓으면, 이 클래스로부터 파생된 모든 클래스에서는 이 가상 함수를 반드시 재정의해야 합니다. 추상 클래스는 먼저 상속을 통해 파생 클래스를 만들고, 만든 파생 클래스에서 순수 가상 함수를 모두 오버라이딩하고 나서야 비로소 파생 클래스의 인스턴스를 생성할 수 있게 됩니다. 하지만 추상 클래스 타입의 포인터와 참조는 바로 사용할 수 있습니다.

*인스턴스: 객체 지향 프로그래밍(OOP)에서 클래스(class)에 소속된 개별적인 객체를 말한다.

Interface(인터페이스)란?

자식 클래스가 여러 부모 클래스를 상속받을 수 있다면, 다양한 동작을 수행할 수 있다는 장점을 가지게 될 것입니다. 하지만 클래스를 이용하여 다중 상속을 할 경우 메소드 출처의 모호성 등 여러 가지 문제가 발생할 수 있어 자바에서는 클래스를 통한 다중 상속은 지원하지 않습니다. 하지만 다중 상속의 이점을 버릴 수는 없기에 자바에서는 인터페이스라는 것을 통해 다중 상속을 지원하고 있습니다. 인터페이스(interface)란 다른 클래스를 작성할 때 기본이 되는 틀을 제공하면서, 다른 클래스 사이의 중간 매개 역할까지 담당하는 일종의 추상 클래스를 의미합니다. 클래스와 클래스 간의 관계를 인터페이스로 연결하면, 클래스마다 독립적인 프로그래밍이 가능하다는 장점이 있습니다. 자바에서 추상 클래스는 추상 메소드뿐만 아니라 생성자, 필드, 일반 메소드도 포함할 수 있습니다. 하지만 인터페이스(interface)는 오로지 추상 메소드와 상수만을 포함할 수 있습니다.

다형성이란?

다형성(polymorphism)이란 하나의 객체가 여러 가지 타입을 가질 수 있는 것을 의미합니다. 다르게 표현하자면 서로 다른 객체가 동일한 메시지에 대하여 서로 다른 방법으로 응답할 수 있는 기능. 즉, 같은 메서드 호출에 대해 서로 다른 방법으로 응답을 하게 되는 것입니다. 다형성은 상속, 추상화와 더불어 객체 지향 프로그래밍을 구성하는 중요한 특징 중 하나입니다. 변화에 유연한 소프트웨어를 만들기 위해서 객체 지향 패러다임을 사용하는 것이라면, 그러한 목적 달성에 중요한 역할을 “다형성”이 해내기 때문입니다. 다형성을 활용하면 기능을 확장하거나, 객체를 변경해야할 때 타입 변경 없이 객체 주입만으로 수정이 일어나게 할 수 있습니다. 또한 상속을 사용한다면 중복되는 코드까지 제거할 수 있으므로 더욱 객체 지향 설계와 가까워질 수 있습니다.

(다형성을 구현하는 방법에는 오버로딩, 오버라이딩, 함수형 인터페이스 등이 있습니다.) *함수형 인터페이스(Functional Interface)란, 람다식을 사용하기 위한 API로 자바에서 제공하는 인터페이스에 구현할 메소드가 하나 뿐인 인터페이스를 의미한다.

Java의 특징

자바(Java)는 C++과는 달리 처음부터 객체 지향 언어로 개발된 프로그래밍 언어입니다. 객체지향개념의 특징인 캡슐화, 상속, 다형성이 잘 적용되어 있는 언어이며 또한, 자바는 자바 가상 머신(JVM)을 사용하여 운영체제에 독립적으로 동작할 수 있습니다. 자바 가상 머신은 가비지 컬렉터(garbage collector)를 이용하여 더는 사용하지 않는 메모리를 자동으로 회수해 줍니다. 즉 자바는 자동 메모리 관리 등을 지원하며 다른 언어베 비해 안정성이 높습니다. 그리고 자바는 연산자 오버로딩을 금지하고 제네릭을 도입함으로서 코드의 가독성을 높였다는 특징이 있습니다. 기본 자료형을 제외한 모든 요소들이 객체로 표현 가능하며 멀티쓰레드를 지원합니다.

람다 표현식이란?

Java8 버전에서 주목한 특징으로 람다 표현식(lambda expression)이란 간단히 말해 메소드를 하나의 식으로 표현한 것입니다. 즉, 식별자 없이 실행할 수 있는 함수 표현식을 의미하며, 따라서 익명 함수(anonymous function)라고도 부릅니다. 메소드를 이렇게 람다 표현식으로 표현하면 클래스를 만들고 객체를 생성하지 않아도 메소드를 사용할 수 있습니다. 또한, 람다 표현식은 메소드의 매개변수로 전달될 수도 있고, 메소드의 결괏값으로 반환될 수도 있습니다. 이러한 람다 표현식은 기존의 불필요한 코드를 줄여주고, 작성된 코드의 가독성을 높이는 데 그 목적이 있습니다.

C언어가 무엇을 하는 언어인가?

C언어는 시스템 프로그래밍에 가장 잘 어울리는 언어입니다. 응용 프로그래밍에서도 많이 사용되며 절차지향적 언어입니다.

컴파일러가 무슨 역할을 하는가?

컴파일이란 어떤 언어의 코드를 다른 언어로 바꿔주는 과정입니다. 그리고 이 과정을 자동으로 수행해주는 소프트웨어가 컴파일러입니다. C,C++ 등으로 작성하는 코드는 컴퓨터가 이해할 수 없습니다. 따라서 우리가 작성한 코드를 컴퓨터가 이해할 수 있게 0, 1로 이루어진 기계어로 번역하는 과정이 필요합니다. 전체 코드를 스캔하는 과정에서 모든 오류를 한꺼번에 출력해주기 때문에 실행 전에 오류를 알 수 있는 점과 초기 스캔시간이 오래 걸리지만 한번 실행 파일이 만들어지고 나면 빠르다는 장점이 있습니다. 컴파일러와 반대로 프로그램 실행 시 한 번에 한 문장씩 번역하는 것을 인터프리터라고 합니다. 대표적인 언어로 파이썬, 루비가 있으며 한 문장씩 번역하므로 실행 시간이 느리다는 단점이 있으나 보안적인 관점에서는 도움이 되며 컴파일러와 같은 오브젝트 코드 생성과정이 없기 때문에 메모리 효율이 좋다는 장점이 있습니다.

C언어의 기본 구성

C언어는 헤더파일, 메인함수가 기본적인 틀이며 주석으로 컴파일러가 무시하는 코드의 이해를 돕는 설명을 작성합니다. main함수는 프로그램의 시작점입니다. 즉 항상 하나의 메인함수만 있어야 하며 제일 처음 호출되고 리턴에 의해 종료됩니다. C언어에서 함수는 사용되기 전에 원형이 선언되어야 합니다. 이런 다양한 정보를 담고 있는 파일을 헤더 파일이라고 합니다. 헤더 파일은 #include 선행처리 지시자를 사용하여 다른 파일에 포함시킬 수 있습니다. C언어 주석의 장점은 프로그램 내의 어디에나 올 수 있다는 점입니다. 여러줄 주석 안에 한줄 주석 삽입은 가능하나 여러줄 주석 안에 여러줄 주석 중첩 삽입은 불가합니다.

printf 함수의 기능, 서식 문자란?

사용자가 프로그램과 대화하기 위해 사용하는 함수를 입출력 함수라고 합니다. printf, scanf함수는 그 중 가장 많이 사용되는 대표적인 입출력 함수입니다. printf()함수는 여러 종류의 데이터를 어떤 서식에 맞춰 출력할지 서식 지정자를 통해 직접 지정할 수 있습니다. C언어에서 사용되는 대표적인 서식 지정자는 하나의 문자 %c, 문자열 %s, 부호 있는 10진 정수 %d(부호 없 %u), 고정 소수점 실수 %f 등이 있습니다. 여러 개의 서식자를 동시에 사용하여 여러 개의 데이터에 각각 다른 서식을 지정래 출력할 수 있습니다.

scanf 함수 기능, &

사용자가 프로그램과 대화하기 위해 사용하는 함수를 입출력 함수라고 합니다. printf, scanf함수는 그 중 가장 많이 사용되는 대표적인 입출력 함수입니다. scanf()함수는 C언어의 표준 입력 함수로 사용자로부터 다양한 서식에 맞춰 입력받을 수 있게 해줍니다. 여기서 &기호는 주소 연산자로 입력 받은 데이터를 뒤에 나오는 변수 즉 메모리 공간에 저장하라는 의미입니다. 여기서 만약 문자열(%s)을 집어넣을 경우엔 문자열 자체(변수가 포인터거나 배열 일때)가 주소이므로 안써도 됩니다. printf() 함수와 달리 scanf() 함수로 double형 실수를 입력받을 때는 반드시 '%lf' 서식 지정자를 사용해야 정확한 값으로 입력받을 수 있습니다.

변수

변수란 데이터를 저장하기 위해 이름을 할당받은 메모리 공간을 의미합니다. 즉 데이터를 저장할 수 있는 메모리 공간을 의미하며 값은 변경될 수 있습니다. C언어에서 숫자 관련 변수는 정수형과 실수형으로 구분할 수 있습니다. 정수형 변수는 char형, int형, long형 변수로, 실수형 변수는 float형, double형 변수로 나눌 수 있습니다. 또한 데이터가 저장된 메모리의 주소를 저장하는 포인터 변수, 관련된 정보를 한 번에 묶어서 처리하는 사용자 정의 구조체 변수도 있습니다. 변수의 이름을 생성할 때 몇가지 규칙이 있습니다. 이름은 영문자, 숫자, 언더스코어로만 구성되며 숫자로 시작할 수 없습니다. 이름 사이에 공백을 포함할 수 없으며 C언어에서 미리 정의된 키워드는 사용할 수 없습니다. 변수는 기본적으로 메모리의 주소를 기억하는 역할을 합니다. 변수를 참조할 때는 메모리 주소를 참조하는 것이 아닌 해당 주소에 있는 데이터를 참조하게 됩니다. 따라서 변수는 메모리의 주소뿐만 아니라 저장된 데이터의 길이와 형태에 관한 정보도 같이 기억해야 합니다. 변수를 선언하는 방법은 크게 2가지가 있습니다. 변수의 선언만 하는 것, 변수의 선언과 동시에 초기화를 하는 것입니다. 또한 선언하고자 하는 변수들의 타입이 같다면 동시에 선언할 수 있습니다.

변수의 유효범위

지역 변수, 전역 변수, 정적 변수, 레지스터 변수란? 변수 선언에 있어 주의사항 C언어에서는 변수의 선언 위치에 따라 해당 변수의 유효 범위, 메모리 반환 시기 등이 달라집니다. 지역 변수(local variable)란 블록(중괄호) 내에서 선언된 변수를 의미합니다. 변수가 선언된 블록 내에서만 유효하며 블록이 종료되면 메모리에서 사라집니다. 지역 변수는 메모리상 스택 영역에 저장되며 초기화하지 않으면 의미 없는 값으로 초기화 됩니다. 함수의 매개변수 또한 함수 내에서 정의되는 지역 변수입니다. 한 블록 내에서 같은 이름의 변수를 또다시 선언하면 오류가 발생합니다. 전역 변수(global variable)는 함수의 외부에서 선언된 변수입니다. 프로그램의 어디에서나 접근할 수 있으며 프로그램이 종료되어야 메모리에서 사라집니다. 전역 변수는 메모리상의 데이터 영역에 저장되며 직접 초기화하지 않아도 0으로 자동 초기화됩니다. 전역 변수와 같은 이름으로 지역 변수를 선언하는 것은 좋지 않습니다. 블록 내에서 선언된 지역 변수는 같은 이름의 전역 변수를 덮어쓰기 때문입니다. 정적 변수(static variable)란 static키워드로 선언한 변수를 의미합니다. 프로그램이 종료되기 전까지 메모리가 소멸되지 않는 변수입니다. 즉 함수를 벗어나도 변수가 사라지지 않고 유지됩니다. 초기화 시엔 상수로 해야하며 초깃값을 지정하지 않으면 디폴트값 0으로 자동 초기화됩니다. 여기까지는 전역 변수와 동일하지만 차이점은 초기화가 딱 한 번 진행된다는 것입니다. 정적 변수는 프로그램이 시작될 때 생성, 종료 시 사라지며 함수의 매개변수로 사용할 수 없습니다. 메모리 할 당 공간은 데이터 영역입니다. 정적 변수는 사용번위에 따라 정적 지역변수, 정적 전역변수로 나뉘며 정적 지역변수는 중괄호 내부에서만 사용할 수 있고 한 번 초기화 되면 이후에 함수 호출 시 값이 초기화를 무시합니다. 정적 지역변수는 자신이 선언된 소스 파일에서만 사용할 수 있고 외부에서는 가져다 쓸 수 없습니다.

레지스터 변수(register variable)란 지역 변수를 선언할 때 register 키워드를 붙여 선언한 변수를 말합니다. 이렇게 선언된 레지스터 변수는 CPU의 레지스터 메모리에 저장되어 빠르게 접근할 수 있게 됩니다. 하지만 컴퓨터의 레지스터는 매우 작은 크기의 메모리이므로, 이 영역에 변수를 선언하기 힘든 경우도 많습니다. 그럴 때 C 컴파일러는 해당 변수를 그냥 지역변수로 선언하게 됩니다.

상수

상수(constant)란 변수와 마찬가지로 데이터를 저장할 수 있는 메모리 공간을 의미합니다. 하지만 상수가 변수와 다른 점은 프로그램이 실행되는 동안 상수에 저장된 데이터는 변경할 수 없다는 점입니다. 상수는 표현 방식에 따라 리터럴 상수와 심볼릭 상수로 나눌 수 있습니다. 리터럴 상수는 변수와 달리 메모리 공간을 가리키는 이름을 가지고 있지 않습니다. 하지만 적절한 메모리 공간을 할당받아야 하기에 타입을 가집니다. 정수형, 실수형, 문자형 리터럴 상수로 구분됩니다. 심볼릭 상수는 변수처럼 이름을 가지고 있는 상수입니다. 반드시 선언과 동시에 초기화되어야 합니다. 이는 const키워드를 사용하거나 매크로를 이용하여 선언할 수 있습니다.

상수도 메모리상에 저장?

상수란 변할 가능성을 없앤 수라고 할 수 있습니다. 1234처럼글자 그대로 의미가 있어서 이름이없는 상수를 리터럴 상수라고 하는데 이러한 상수도 마찬가지로 메모리 공간의 어딘가에 저장됩니다. 다만 그 위치가 조금 다를 뿐입니다. 메모리 공간에는 ‘상수 공간’이라는 특별한 공간이 있으며 이 공간에 존재하는 모든 데이터는 프로그램이 실행할 때 메모리 상 입력된 뒤로는 수정이 불가능 합니다.

기본 자료형의 종류와 특징

C언어에서 타입이란 해당 데이터가 메모리에 어떻게 저장되고 처리할지 명시적으로 알려주는 역할을 합니다. C언어는 기본 타입을 미리 작성하여 제공하고 있습니다. 기본 타입은 크게 정수형, 실수형, 문자형으로 나눌 수 있습니다. 정수형 데이터에 unsigned 키워드를 추가하면, 부호를 나타내는 최상위 비트(MSB, Most Significant Bit)까지도 크기를 나타내는 데 사용할 수 있습니다. 이러한 unsigned 정수는 음수를 표현할 수는 없게 되지만, 0을 포함한 양의 정수는 두 배 더 많이 표현할 수 있게 됩니다. 음의 정수까지도 표현할 수 있는 signed 키워드는 모든 타입에서 기본적으로 생략하여 사용할 수 있습니다. 각각에 할당되는 메모리의 크기 순서로short(2bite), int(4), long(8)가 있습니다. 오버플로우가 발생하지 않기 위해 반드시 자신이 사용하고자 하는 데이터의 최대 크기를 고려해야 합니다. 오버플로우(overflow)란 해당 타입이 표현할 수 있는 최대 범위보다 큰 수를 저장할 때 발생하는 현상을 가리킵니다. 언더플로우(underflow)란 해당 타입이 표현할 수 있는 최소 범위보다 작은 수를 저장할 때 발생하는 현상을 가리킵니다. 실수형 타입으로는 float(4), double(8)이 있습니다. 실수형 데이터의 타입을 결정할 때는 표현 범위 이외에도 유효 자릿수를 반드시 고려해야 합니다. float은 소수 부분 6자리까지 double은 소수 부분 15자리까지 오차 없이 표현할 수 있습니다. C언어에서 문자형의 경우 컴퓨터는 2진수밖에 인식하지 못하므로, 문자도 숫자로 표현해야 컴퓨터가 인식할 수 있습니다. 그래서 아스키 코드를 많이 사용합니다. 아스키코드(ASCII)는 영문 대소문자를 사용하는 7비트의 문자 인코딩 방식입니다. 즉 128개의 문자를 표현할 수 있습니다. 문자형 타입으로는 char로 1바이트, unsigned char 2바이트의 메모리 크기를 할당 받습니다. 데이터의 표현방식과 메모리의 효율성 차이 때문에 이렇게 여러가지의 데이터 타입이 있는 것, 최상위 비트(MSB, Most Significant Bit)란 1바이트를 구성하는 8개의 비트 중 최고값을 갖는 비트를 의미.

타입변환(자동 형 변환, 강제(명시) 형 변환)

C언어에서 다른 타입끼리의 연산은 우선 피연산자들을 모두 같은 타입으로 만든 후에 수행됩니다. 이처럼 하나의 타입을 다른 타입으로 바꾸는 행위를 타입 변환(type conversion)이라고 합니다. 표현 범위가 좁은 타입에서 표현 범위가 더 넓은 타입으로의 타입 변환은 큰 문제가 되지 않습니다. 하지만 반대의 경우인 표현 범위가 좁은 타입으로의 타입 변환에서는 데이터의 손실이 발생합니다. 묵시적 타입 변환(자동 타입 변환, implicit type conversion)은 데이터 타입을 자동으로 변환해주는 것을 의미하며 대입 연산자를 기준으로 오른쪽에서 왼쪽으로 자동 형 변환됩니다. 메모리 크기가 작은 자료형에서 큰 자료형으로 즉 컴파일러가 자동으로 수행하는 타입 변환은 언제나 데이터의 손실이 최소화되는 방향으로 이루어집니다. 따라서 C 컴파일러는 다음과 같은 순서대로 자동 타입 변환을 수행하게 됩니다. char 형 → short 형 → int 형 → long 형 → float 형 → double 형 → long double 형 명시적 타입 변환(강제 타입 변환, explicit type conversion)으로 개발자가 직접 형 변환을 요청하는 것을 의미합니다. 변환하고자 하는 데이터의 앞에 괄호를 추가하고, 그 안에 변환할 타입을 적으면 됩니다. C언어에서는 이 괄호(())를 타입 캐스트(type cast) 연산자라고 합니다. 굳이 강제적으로 하는 이유는 데이터 손실을 최소화하기 위해서입니다. 큰 자료형에 있던 데이터가 작은 자료형에 모두 들어간다면 데이터 손실이 일어나게 됩니다. 강제 변환 시 데이터 손실의 여부에 따라 비교하여 설명하겠습니다. 손실이 없는 경우 즉 작은 자료형에서 큰 자료형으로 전환되는 경우를 확장 변환, 프로모션이라고 합니다. 반대로 큰 자료형에서 작은 자료형으로 전환되어 데이터 손실이 발생하는 경우 축소 변환, 디모션이라고 합니다.

int형 정수 연산이 빠른 이유는?

메모리 크기 1바이트를 차지하는 char형이 있음에도 불구하고 일반적으로 정수형 데이터를int형을 사용합니다. 이유는 정수형 자료 중에서도 int형을 CPU가 가장 빠르게 처리하기 때문입니다. 그 이유는 현재 개발된 대부분의 컴퓨터들은 32비트(4바이트) 이상의 시스템이기 때문입니다. 따라서 정수 데이터를 char형 변수에 저장할 경우CPU가 32비트로 바꿔 연산을 수행 즉 형 변환을하기에 시간이 더 걸리게 됩니다. 반대로 속도가 느리더라도 영상이나 음악파일처럼 메모리 공간을 잘 활용해야 한다면 char, short가 더 유리할 수 있습니다.

다양한 종류의 연산자는 어떤 것이 있고, 증가 및 감소 연산자가 무엇인가?

연산자란 프로그램의 산술, 연산식을 표현하고 처리하기 위해 제공되는 다양한 기호를 의미합니다. 연산자의 종류로는 산술 연산자, 대입 연산자, 증감 연산자, 비교 연산자, 논리 연산자, 비트 연산자, 삼항 연산자 등이 있습니다. 산술 연산자는 사칙연산을 다루며 모두 두 개의 값을 필요로 하는 이항 연산자입니다. 대입 연산자는 피연산자들의 결합 방향이 오른쪽에서 왼쪽인 이항 연산자입니다. 증감 연산자는 단항 연산자로 피연산자를 1씩 증가, 감소시킬 때 사용합니다. ++x이면 먼저 값을 1증가시킨 후 해당 연산을 진행하고, x++이면 먼저 해당 연산을 수행하고 나서 값을 1 증가시킵니다. 비교 연산자는 피연산자 사이의 상대적인 크기를 비교하며 논리 연산자(and, or, not)는 주어진 논리식을 판단하여 참, 거짓을 결정합니다. 비트 연산자는 비트 단위로 논리 연산을 하거나 비트를 왼오른쪽로 이동시킬 때 사용합니다. 삼항 연산자는 C언어만의 독특한 연산자입니다. C언어에서도 유일하게 피연산자를 세 개나 가집니다. (조건식 ? 반환값1 : 반환값2) ?앞의 조건식에 따라 결과값이 참이면 반환값1, 거짓이면 반환값2를 반환합니다. 이때 반환값에는 값뿐만 아니라 수식, 함수 호출 등 여러 명령문이 올 수 있습니다. 이는 if/else 문 대신 사용할 수 있으며 코드를 더 간결하게 작성할 수 있도록 도와줍니다. sizeof연산자는 단항 연산자로 피연산자의 크기를 바이트 단위로 반환합니다. 변수나 상수가 피연산자로 전달되면 해당하는 타입의 크기를 반환해줍니다. 이를 통해 사용하는 컴퓨터 환경에서의 타입 크기를 알아볼 수 있습니다. +포인터 연산자

비트 단위 연산의 종류

컴퓨터는 모든 데이터를 비트 단위로 표현하고 처리합니다. 현재 하드웨어의 발달로 비트 단위까지 생각하지 않더라도 충분히 빠른 프로그램을 작성할 수 있으나 하드웨어 관련 프로그래밍이나 제한된 자원을 가진 시스템을 위한 프로그램에서는 비트 단위 연산이 자주 사용되고 있습니다. 이를 통해 사용되는 메모리 공간을 줄이거나 성능의 향상을 기대할 수 있기 때문입니다. ~(비트 NOT 연산): 비트를 1이면 0으로, 0이면 1로 반전함. &(비트 AND 연산): 대응되는 비트가 모두 1이면 1을 반환함. |(비트 OR 연산): 대응되는 비트 중에서 하나라도 1이면 1을 반환함. ^(비트 XOR 연산): 대응되는 비트가 서로 다르면 1을 반환함. <<, >>(left, right shift 연산): 지정한 수만큼 비트들을 전부 왼,오쪽으로 이동시킴.

C언어에서 true와 false는 어떻게 표현하나?

컴퓨터에서 참(true)은 보통 1로 표현되고, 거짓(false)은 0으로 표현됩니다. 하지만 C언어에서는 음수를 포함해 0이 아닌 모든 수가 참(true)으로 취급됩니다.

2진수와 16진수는 무엇인가? - 계산법 공부하기(8진수도)

2진수는 주로 컴퓨터에서 사용하는 0과 1로 표현하는 하는 수입니다. 컴퓨터에서 모든 데이터의 표현 및 연산은 2진수로 처리하기 때문에 2진수를 이해해야 C언어를 보다 정확하게 이해한다고 할 수 있다. 16진수는 09, AF로 표현하는 수이다. 2진수로 데이터를 표현하면 길이가 길어지기 때문에 표현하기에나 사람이 한눈에 파악하기 어려운 면이 있는데, 16진수는 보다 간결해지고 이해하기 수월하는 장점이 있습니다. HTML에서 색상을 표현할 때도 사용합니다. 네트워크에선 16진수를 자주 사용하는데, 이는 16진수가 4bit임으로 1byte를 16진수 2개처럼 표현하기 용이하기 때문입니다.

정수와 실수가 컴퓨터에 의해서 표현되는 방법은?

컴퓨터에서 정수를 표현하는 방법은 크게 부호없는 정수와 부호있는 정수로 나누어 생각할 수 있습니다. 부호없는 정수를 표현할 때에는 단지 해당 정수 크기의 절댓값을 2진수로 변환하여 표현하면 됩니다. 하지만 문제는 부호있는 정수에서 음수를 표현하는 방법에 있습니다.컴퓨터에서 음수를 표현하는 방법은 다음과 같이 다양합니다. 부호 비트와 절댓값 방법, 1의 보수법, 2의 보수법 부호 비트와 절댓값 방법은 최상위 1비트로 부호를 표현하고, 나머지 비트로 해당 정수의 절댓값을 표현하는 방법입니다. 이 방법을 사용하면 최상위의 1비트가 부호를 표현하기 위해 사용되어 표현할 수 있는 절댓값의 범위는 절반으로 줄어듭니다. 그러나 음수를 표현할 수 있으므로, 총 표현할 수 있는 크기는 거의 비슷해집니다. 하지만 이 방법으로 음수를 표현하면 +0과 -0이 따로 존재하게 됩니다. 1의 보수법은 해당 양수의 모든 비트를 반전하여 음수를 표현하는 방법입니다. 이 방법을 사용하면 음수를 비트 NOT 연산만으로 표현할 수 있어서 연산이 매우 간단해집니다. 하지만 1의 보수법은 부호 비트와 절댓값 방법과 같이 +0과 -0이 따로 존재하는 문제점을 가집니다. 2의 보수법은 해당 양수의 모든 비트를 반전한 1의 보수에 1을 더하여 음수를 표현하는 방법입니다. 이 방법은 앞서 살펴본 방법이 모두 두 개의 0을 가지는 문제점(+0과 -0)을 해결하기 위해 고안되었습니다. 이 방법을 사용하면 -0은 2의 보수를 구하는 과정에서 최상위 비트를 초과한 오버플로우가 발생하여 +0이 됩니다. 따라서 2의 보수법에서는 단 하나의 0만이 존재하게 됩니다. 이 때문에 현재 대부분의 시스템에서는 모두 2의 보수법으로 음수를 표현하고 있습니다.

컴퓨터에서 실수를 표현하는 방법은 정수에 비해 훨씬 복잡합니다. 왜냐하면 컴퓨터에서는 실수를 정수와 마찬가지로 2진수로만 표현해야 하기 때문입니다. 첫째는 고정 소수점 방식입니다. 실수는 보통 정수부와 소수부로 나눌 수 있습니다. 따라서 실수를 표현하는 가장 간단한 방식은 소수부의 자릿수를 미리 정해 놓고, 고정된 자릿수로 소수를 표현하는 것입니다. 하지만 이 방식은 정수부와 소수부의 자릿수가 크지 않으므로, 표현할 수 있는 범위가 매우 적다는 단점이 있습니다. 부동 소수점 방식은 실수를 가수부와 지수부로 나누어 표현하는 방식입니다. 부동 소수점 방식은 수식을 사용하여 매우 큰 실수까지도 표현할 수 있게 됩니다. 하지만 부동 소수점 방식에 의한 실수의 표현은 항상 오차가 존재한다는 단점을 가지고 있습니다. 부동 소수점 방식에서의 오차는 앞서 살펴본 공식에 의해 발생합니다. 이 공식을 사용하면 표현할 수 있는 범위는 늘어나지만, 10진수를 정확하게 표현할 수는 없게 되기 때문입니다. 따라서 컴퓨터에서 실수를 표현하는 방법은 정확한 표현이 아닌 언제나 근사치를 표현할 뿐임을 항상 명심해야 합니다.

실수를 표현하는 데 있어서 오차가 발생하는 이유

부동소수점 가수부와 지수부를 사용하게되면 표현할 수 있는 범위는 넓어지지만 거의 오류가 없을 만큼 아주 가까운 근사치를 통해 표현을 하기 때문에 오차가 발생합니다. 순환소수나 무한소수의 경우 가수부가 표현하는 비트수를 넘어가면 손실되는 부분이 생기기 떄문입니다.

서식 문자 %lf와 %f

%f는 float형태의 실수로 입력한다는 뜻입니다. %lf에서 lf란 long float의 줄임말이고 double형의 실수로 입력한다는 뜻입니다. 각각 4바이트 8바이트로 차이가 있습니다. 즉 값을 scanf()로 입력받을 때도 차이가 있습니다. float형에 저장할 것이라면 %f로 받고 double형에 저장할 것이라면 %lf로 받아야 합니다. 하지만 값을 printf()로 출력할 땐 %f로 출력해도 둘 다 이상없이 출력이 가능합니다.

switch문

int형으로 승격할 수 있는 값만이 사용될 수 있습니다. 즉 다른 조건문보다 사용할 수 있는 상황이 적은 편입니다. 가독성이 좋으며 속도가 빠른 편입니다. 마지막으로 삼항 연산자에 의한 조건문이 있습니다. 삼항 연산자는 C언어만의 독특한 연산자입니다. C언어에서도 유일하게 피연산자를 세 개나 가집니다. (조건식 ? 반환값1 : 반환값2) ?앞의 조건식에 따라 결과값이 참이면 반환값1, 거짓이면 반환값2를 반환합니다. 이때 반환값에는 값뿐만 아니라 수식, 함수 호출 등 여러 명령문이 올 수 있습니다. 이는 if/else 문 대신 사용할 수 있으며 코드를 더 간결하게 작성할 수 있도록 도와줍니다.

루프의 제어 continue문, break문

continue문과 break문은 일반적인 루프의 흐름을 사용자가 직접 제어할 수 있게 도와줍니다. continue문은 루프 내에서 사용하여 해당 루프의 나머지 부분을 건너뛰고 바로 다음 조건식의 판단으로 넘어가게 합니다. 반복문 내에서 특정 조건에 대해 예외 처리를 하고자 할 때 많이 사용합니다. 예를 들어 1부터 100까지 정수 중에서 3의 배수를 제외하고 출력하고자 할 때 반복문 속 조건문에 3의 배수인 경우 continue문을 쓸 수 있습니다. break문은 루프 내에서 사용하여 해당 반복문을 완전히 종료시킨 뒤, 반복문 바로 다음에 위치한 명령문을 실행합니다. 즉 루프 내에서 반복문을 완전히 빠져나가고 싶을 때 사용합니다.

goto문? 왜 불필요한 문법인지

goto문은 프로그램의 흐름을 지정된 레이블(위치)로 무조건 변경시키는 명령문입니다. 다른 제어문과는 달리 아무런 조건 없이 흐름을 옮겨줍니다. 따라서 가장 손쉽게 사용할 수 있지만 흐름을 복잡하게 만들기도 합니다. C언어는 절차지향적 언어로 프로그램의 흐름이 복잡해지는 것은 큰 문제가 되기 때문에 현재는 디버깅 이외에는 거의 사용되지 않습니다.

메모리의 구조

프로그램이 실행되기 위해서는 메모리에 로드되어야 하고 변수들을 저장할 메모리도 필요합니다. 따라서 컴퓨터의 운영체제는 다양한 메모리 공간을 제공하고 있습니다. 코드 영역, 데이터 영역, 힙 영역, 스택 영역입니다. 코드 영역은 실행할 프로그램의 코드가 저장괴는 영역으로 CPU는 코드 영역에 저장된 명령어를 하나씩 가져와 처리합니다. 데이터 영역은 전역 변수와 정적 변수가 저장되는 영역입니다. 프로그램의 시작과 함께 할당되며 프로그램이 동료되면 소멸합니다. 힙 영역은 사용자가 직접 관리할 수 있는 그래야만 하는 메모리 영역입니다. 사용자에 의해 메모리 공간이 동적으로 할당, 해제됩니다. 힙 영역은 메모리의 낮은 주소에서 높은 주소의 방향으로 할당죕니다. 스택 영역은 함수의 호출과 관계되는 지역 변수 매개 변수가 저장되는 영역입니다. 함수의 호출과 함께 할당되며 호출이 완료되면 소멸합니다. 스택 영역은 푸시 동작으로 데이터를 저장하고 팝 동작으로 데이터를 인출하며 후입선출 방식으로 늦게 저장된 데이터가 가장 먼저 인출됩니다. 스택 영역은 메모리의 높은 주소에서 낮은 주소의 방향으로 할당됩니다.

스택 프레임(stack frame)

메모리의 스택(stack) 영역은 함수의 호출과 관계되는 지역 변수와 매개변수가 저장되는 영역입니다.스택 영역은 함수의 호출과 함께 할당되며, 함수의 호출이 완료되면 소멸합니다. 함수가 호출되면 스택에는 함수의 매개변수, 호출이 끝난 뒤 돌아갈 반환 주소값, 함수에서 선언된 지역 변수 등이 저장됩니다. 이렇게 스택 영역에 차례대로 저장되는 함수의 호출 정보를 스택 프레임(stack frame)이라고 합니다. 이러한 스택 프레임 덕분에 함수의 호출이 모두 끝난 뒤에, 해당 함수가 호출되기 이전 상태로 되돌아갈 수 있습니다.

메모리의 동적 할당(dynamic allocation)

데이터 영역과 스택 영역에 할당되는 메모리의 크기는 컴파일 타임에 미리 결정됩니다. 하지만 힙 영역의 크기는 프로그램이 실행되는 도중인 런 타임에 사용자가 직접 결정하게 됩니다. 이렇게 런 타임에 메모리를 할당받는 것을 메모리의 동적 할당이라고 합니다. malloc() 함수는 프로그램이 실행 중일 때 사용자가 직접 힙 영역에 메모리를 할당할 수 있게 해줍니다. 힙 영역에 할당할 수 있는 적당한 블록이 없을 때에는 널 포인터를 반환합니다. 주소값을 반환받기 때문에 힙 영역에 할당된 메모리 공간으로 접근하려면 포인터를 사용해야 합니다. free() 함수는 힙 영역에 할당받은 메모리 공간을 다시 운영체제로 반환해 주는 함수입니다. 용한 메모리를 해제해 주지 않으면, 메모리가 부족해지는 현상이 발생할 수 있습니다. calloc() 함수는 malloc() 함수와 마찬가지로 힙 영역에 메모리를 동적으로 할당해주는 함수입니다. 이 함수가 malloc() 함수와 다른 점은 할당하고자 하는 메모리의 크기를 두 개의 인수로 나누어 전달받는 점입니다. 또한, calloc() 함수는 메모리를 할당받은 후에 해당 메모리의 모든 비트값을 전부 0으로 초기화해 줍니다. realloc() 함수는 이미 할당된 메모리의 크기를 바꾸어 재할당할 때 사용하는 함수입니다. 만약 기존의 메모리 위치에 충분한 공간이 있다면 바로 이어서 추가 메모리 공간을 할당해 줍니다. 하지만 기존의 메모리 위치에 충분한 공간이 없으면 메모리의 다른 공간에 기존의 데이터를 복사한 후, 이어서 추가 메모리 공간을 할당하게 됩니다.

포인터에도 타입이 있는 이유

포인터 타입을 정의할 때는 기존에 정의된 데이터 타입 뒤에 * (Asterisk)애스터리스크 를 붙이면 됩니다. 모든 포인터 타입의 변수에는 주소값이 저장되기 때문에 포인터 변수가 차지하는 메모리 크기는 모두 같습니다. 사람이 본다면 포인터들이 가리키고 있는 변수가 어떤 데이터 타입인지 알 수 있지만 컴퓨터는 모릅니다. 코드를 실행하기 위해선 메모리 할당이 필요하고 포인터가 가리키는 변수의 타입을 알아야 하기에 포인터에 타입을 두어 컴퓨터가 알게 하는 것입니다.

배열 포인터와 포인터 배열의 차이점

포인터 배열이란 배열 요소로 포인터 변수를 가지는 배열을 의미합니다. 즉, 포인터 변수를 저장할 수 있는 배열을 의미합니다. 배열 포인터란 배열을 가리킬 수 있는 포인터를 의미합니다. 배열 이름이 있는데도 따로 배열 포인터를 정의하여 사용하는 이유는 2차원 이상의 배열을 가리킬 때 포인터를 통해 배열과 같은 인덱싱을 할 수 있도록 하기 위함입니다. 즉, 포인터를 배열처럼 사용하기 위해서 배열 포인터를 정의하여 사용합니다. 따라서 배열 포인터는 1차원 배열에서는 아무런 의미가 없으며, 2차원 이상의 배열에서만 의미를 가집니다.

1. int (*pArr)[3]; - 배열 포인터
2. int* pArr[3]; - 포인터 배열

포인터 상수와 상수 포인터

포인터와 배열은 매우 긴밀한 관계를 맺고 있으며, 어떤 부분에서는 서로를 대체할 수도 있습니다. 배열의 이름은 그 값을 변경할 수 없는 상수라는 점을 제외하면 포인터와 같습니다. 따라서 배열의 이름은 포인터 상수(constant pointer)입니다. 즉 포인터 상수(constant pointer)란 포인터 변수가 가리키고 있는 주소 값을 변경할 수 없는 포인터를 의미하며, 상수 포인터(pointer to constant)란 상수를 가르키는 포인터를 의미합니다.

💡 인성 면접 예상 질문

경상대는 자소서, 학업 계획서를 제출하기에 그 서류를 바탕으로 꼬리 질문을 예상해서 준비했습니다. 카이스트에서 주관한 대회의 수상 경력을 첫 문장으로 적었기에 👉 어떤 아이템인지 간단히, 컴공과와 접점 찾아 어필

자기소개, 학업계획, 개인 프로젝트 경험, 사용해본 언어, 내 관심 주제에 대한 개념이해(블록체인에 빠져있을 시기라) 등등 준비했습니다.

나는 내 경험을 쭉 나열하고 각각 내가 한 일, 느낀점을 적었던 게 도움이 됐다. 면접 안그래도 긴장 덩어린데 술술 나오려면 머리에 잘 정리가 되어있어야 한달까?..?

이전 학교에서의 경험들(대회, 팀플), 기술 박람회, 자동 분류기 제작, 웹 front-end 개발, 백준 문제로 알고리즘 공부, 앞으로 하고 싶은 것, 그걸 위해 지금 하고있는 공부 등등 작은 거 전부 챙기자...!

✨면접 질문, 느낀점

학과 교수님들의 연구실, 논문 이름이라도 보고 가서 언급했더니 면접 볼 때 교수님 두 분이 마주보고 웃어주셨던 게 기억나네요. 진짜 교수님의 웃음 하나하나가 소중합니다..❤ 창원대 면접이 첫 면접이라서 너어어어무 염소마냥 떨었더니 너무 후회가 크게 남아서 두 번째 면접부터는 정말 하나도 안 떨었어요. 신기하네 이걸 조절하고...

전공 질문 부경대의 폰노이만 질문 빼고 전부 위에 있어서 막힘 없이 잘 대답했스빈다.... 폰노이만.... 역시 시간을 만들어서라도 더더 공부해가야한다.

창원대 면접 전 문제 푸는 시간 10분 주고 종이에 적어 들어갈 수 있다. 택 1해서 설명하는 방식이다.

1. 자기소개, 지원동기
2. 선택한 문항에 대해 답변
3. 그 대회는 어떤 대회?
4. 좋아하는 언어?
5. 어떤 프로젝트 해봤나?
6. 만약 천만 개의 데이터가 있다면 어떤 정렬 알고리즘 사용?
7. 마지막으로 하고 싶은 말?

계명대

1. 자기소개, 지원동기
2. 대회는 어떤 대회?
3. 아 과가 많이 다르네요?
4. 사용해본 언어?
5. 원하는 진로 방향?
6. 따로 강의를 들으며 공부했나?
7. 2년 이상 걸릴 수도 있는데 괜찮나?
8. 만약 봉사할 기회가 생긴다면 어떤 걸 하고 싶나?

부경대 면접 전 10분 간 문제를 읽을 수 있고 따로 필기는X

1. 지원 동기, 학업 계획, 진로 방향
2. 빅데이터, 인공지능, 메타버스 등 요즘 트렌트 중 관심 분야에 대해 개념 설명, 장단점, 단점 보완 방법 설명
3. 폰노이만 구조와 하버드 구조에 대해
4. 연결리스트란? 배열과 연결리스트의 차이
5. 무슨 언어 써봤나?
6. 독학했나?
7. 비전공자인데 자료구조 혼자 공부한 건가?
8. 백준 문제 풀었다고 했는데 어느정도 풀었나?

경상대

1. 재귀 함수에 대해
2. 스택과 큐에 대해
3. 배열과 연결리스트에 대해
4. 자소서에 적힌 대회는 어떤 아이디어로 나갔나?
5. 그러면 원래 비동일계?
6. 편입을 지원한 이유?
7. 프로젝트 경험?
8. 무슨 공부를 해봤나?
9. 독학했나?

📃 기록

최초합, 추합, 예비탈락 등 많은 성적을 아주 골고루 받았다. 면접볼 때 떨면 내 손해 ㅇㅇ 떨지 말고 편하게 꾸밈 없이 말하기✨ 있어보이는 대답보단 정말 내가 알고 관심있는 걸 말하는 게 중요한 것 같았다. 어떻게든 대답하고 각 문항을 연결지어 설명하니 문맥이 더 부드러웠다. 예를 들어 경상대의 경우 2ㅡ3 번을 연결지어 스택과 큐를 배열과 연결리스트로 구현 시 차이점과 장단점 등을 설명했었다. 이게 정답은 아닐 수 있지만 내가 자신감 있게 말하는 게 중요타!!!

등록은 장학생으로 뽑힌 경상대✨💕 부모님이 면접마다 휴가내셔서 운전하시느라 너무 고생하셨는데 감사드리고 새로운 길 어렵게 결정한 만큼 열심히 하겠습니다.(o゜▽゜)o☆

그룹 단어란 단어에 존재하는 모든 문자에 대해서, 각 문자가 연속해서 나타나는 경우만을 말한다. 예를 들면, ccazzzzbb는 c, a, z, b가 모두 연속해서 나타나고, kin도 k, i, n이 연속해서 나타나기 때문에 그룹 단어이지만, aabbbccb는 b가 떨어져서 나타나기 때문에 그룹 단어가 아니다.

단어 N개를 입력으로 받아 그룹 단어의 개수를 출력하는 프로그램을 작성하시오.

해결 방법

첫 문자부터 자신을 제외한 문자열의 첫 문자와 비교하여 같다면 제외하고 다른 문자를 만났으면 그 문자열에서 자신의 문자와 같은 값이 있는지 확인하면 된다.

이때 count()함수로 새 문자열에 해당 문자가 있는지 카운트하고 그 값이 1이상이라면 error +1 을 해준다. -> error가 0이어야만 출력 카운트 +1

제출

```python n = int(input()) cnt = 0

for _ in range(n): word = input() error = 0 for i in range(len(word)-1): #인덱스 범위: 0~단어길이-1 if word[i] != word[i+1]: #연속된 문자가 다를 때 n_word = word[i+1:] #해당 문자를 제외한 새 문자 생성 if 0 < n_word.count(word[i]): #새 문자에 해당 문자가 있다면 error += 1 #에러 체크 if error == 0: #에러가 0이라면 카운트 cnt += 1

print(cnt)```

👉 문자열에 인덱스를 주기 위해 len(word) - 1 을 해준다. 👉 설명은 소스코드에 (. ❛ ᴗ ❛.)

구현이란 머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정이다. 대체로 사소한 조건이 많아 코드로 구현하기 까다로우며 _문법을 정확히 숙지하지 못했거나 라이브러리 사용이 부족_하다면 구현 유형의 문제를 풀 때 불리하다.

✨ C/C++ 사용 시 변수의 표현 범위에 주의 ✨ 파이썬은 다른 언어에 비해 복잡함이 적은 편이지만 데이터 처리량이 많을 때는 꼭 메모리 제한을 고려

예제

🔒상하좌우

import sys
input = sys.stdin.readline
#입력값 받기
n = int(input())
move_list = input().split()
x, y = 1, 1 #초기 좌표(1,1)
#방향벡터 정의
dx = [0, 0, -1, 1]
dy = [-1, 1, 0, 0]
move_type = ['L', 'R', 'U', 'D']
#좌표 이동 반복문
for i in move_list:
    for j in range(len(move_type)):
        if i == move_type[j]:
            nx = x + dx[j]
            ny = y + dy[j]
            #범위 조건: n넘으면 코드 실행 건너뛰기
            if nx < 1 or nx > n or ny < 1 or ny > n:
                continue
            x, y = nx, ny #좌표 이동

print(x, y)

방향벡터를 이용해

for j in range(len(move_type)):
        if i == move_type[j]:

💡 0부터 move_type의 길이 만큼을 j값이 돌며 반복문을 수행하도록 해주고 i값과 같다면 좌표를 이동한다.

이런 문제는 일련의 명령에 따라서 개체를 차례대로 이동시킨다는 점에서 시뮬레이션유형으로 분류되며 구현이 중요한 대표적인 문제 유형이다.

🔒시각

h = int(input())
cnt = 0

for i in range(h+1): #0~h
    for m in range(60): #0~59
        for s in range(60):
            if '3' in str(i) + str(m) + str(s):
                cnt += 1

print(cnt)

이 문제는 3중 반복문을 돌리면 해결된다. 그리고 조건문으로 3이 포함되면 카운트해주며 결과를 출력한다.

실전 문제

🔒왕실의 나이트

data = input()
cnt = 0
#행과 열로 나누기
row = int(data[1])
column = int(ord(data[0])) - int(ord('a')) + 1
#이동가능한 8가지 방향
move = [(1, 2), (1, -2), (-1, 2), (-1, -2), (2, 1), (2, -1), (-2, 1), (-2, -1)]
#이동이 가능하다면 카운트
for i in move:
    nRow = row + i[0]
    nColum = column + i[1]
    if nRow <= 8 and nColum <= 8 and nRow >= 1 and nColum >= 1:
        cnt +=1
#출력
print(cnt)

✨ord(): 하나의 문자에 대한 아스키 코드(ASCII Code) 정수 값을 반환

column = int(ord(data[0])) - int(ord('a')) + 1

이 코드는 문자를 아스키 코드 정수 값을 반환받고 인덱스로 사용하기 위해 a의 아스키 코드값을 뺀 후 1을 더해주는 것이다. 본 문제의 인덱스는 1부터 시작하기 때문에 1을 더해줘야 한다.

이전 문제와 다른 성격으로 이동할 방향을 기록했다. 이번 소스코드에선 move 리스트 내에 이동 가능한 8가지 방향을 원소로 넣고 반복문으로 i가 돌며 범위 내라면 카운트한다.

🔒게임 개발

n, m = map(int, input().split())
#리스트컴프리헨션으로 n*m 맵 생성(방문한 곳인지 기록)
d = [[0] * m for _ in range(n)]
x, y, direction = map(int, input().split())
d[x][y] = 1 #현재 위치 방문 처리

#전체 리스트 입력 받기
arr = []
for i in range(n):
    arr.append(list(map(int, input().split())))

#북, 동, 남, 서 방향 정의
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]

#왼쪽 회전 함수: 반복적으로 쓰임
def t_left():
    global direction
    direction -= 1
    if direction == -1: #북쪽이라면
        direction = 3 #서쪽 방향값인 3을 대입

#시뮬레이션 시작
cnt = 1 #초기 위치 포함
turn_cnt = 0
while True:
    t_left() #왼쪽으로 돌기
    nx = x + dx[direction] #바라보는 방향으로 이동
    ny = y + dy[direction]
    # 회전 후 정면에 가지 않은 칸이 있다면
    if d[nx][ny] == 0 and arr[nx][ny] == 0:
        d[nx][ny] = 1 #방문처리
        x = nx #이동
        y = ny
        cnt += 1
        turn_cnt = 0
        continue
    else: #회전 후 정면에 가지 않은 칸이 없거나 바다라면
        turn_cnt += 1
    # 4방향 전부 갈 수 없을 때
    if turn_cnt == 4:
        nx = x - dx[direction]
        ny = y - dy[direction]
        if arr[nx][ny] == 0: #후진이 가능하면 후진
            x = nx
            y = ny
        else: #후진하는 곳이 바다라면 반복문 탈출
            break
        turn_cnt = 0

print(cnt)

차원 좌표, 왼오른쪽으로 기준점의 방향 이동 등 까다로운 조건이 있어 소스코드로 옮기는 과정이 다소 까다로웠다.

문제를 읽으면 보이는 특징

💡왼쪽으로 도는 과정을 자주 사용한다.

그래서 왼쪽으로 도는 t_left 함수를 만들어 주어진 조건에 맞게 북쪽(0)에서 -1을 하면 -1이므로 서쪽(3)의 값인 3을 대입해줘야 한다.

💡방문한 곳은 1로 변경하는 d리스트를 따로 선언했다.

💡네 방향 전부 가본 곳이라는 문제의 조건을 코드로 표현하기 위해 turn_cnt 변수로 4번이 차면(4방향으로 다 돌았음) 다음 동작을 하도록 했다.

💡t_left 함수에서 global 키워드를 사용했는데 direction 정수형 변수가 함수 밖에서 선언된 전역변수이기 때문이다.

코딩도장 전역 변수 👉 변수에 대해 자세한 설명이 있숨다

메모

백준에서 몇몇 구현 문제를 풀었는데 해결책은 쉽게 떠오르지만 코드로 옮기는 게 쉽지,,,아니하다,,, 자주 반복해서 접해야겠음

옛날 옛적에 수학이 항상 큰 골칫거리였던 나라가 있었다. 이 나라의 국왕 김지민은 다음과 같은 문제를 내고 큰 상금을 걸었다.

길이가 N인 정수 배열 A와 B가 있다. 다음과 같이 함수 S를 정의하자.

S = A[0] × B[0] + ... + A[N-1] × B[N-1]

S의 값을 가장 작게 만들기 위해 A의 수를 재배열하자. 단, B에 있는 수는 재배열하면 안 된다.

S의 최솟값을 출력하는 프로그램을 작성하시오.

해결 방법

a리스트의 최솟값 * b리스트의 최댓값을 반복하면 해결된다! 그러면 각각 오름차순, 내림차순 정렬 후 풀면 간단하겠지만 b는 재배열하면 안 된다는 조건이..!있다..!

💡그러면 정렬이 아닌 min(), max() 함수로 각각의 최소, 최댓값을 뽑고 pop연산을 한다면 되겠군

위 과정을 n번 반복해주면 풀리는 문제이다.

제출

n = int(input())
a_list = list(map(int, input().split()))
b_list = list(map(int, input().split()))
ans = 0
cnt = 0

while True:
    if cnt == n:
        break
    ans += min(a_list) * max(b_list)
    a_list.remove(min(a_list))
    b_list.remove(max(b_list))
    cnt += 1

print(ans)

메모

위처럼 while문 속 break 제어문을 사용하지 않고 for문으로 n번 반복해도 된다. 근데 왜 요즘 while문이 자꾸 쓰고싶지 저런 모양 코드가 좋니..? (. ❛ ᴗ ❛.)

그리디 알고리즘이란 탐욕적인 방법으로 _현재 상황에서 최선의 선택_을 하는 것이다. 매 순간 가장 좋은 것을 택하며 나중에 미칠 영향은 생각하지 않는다. 이 유형의 문제는 암기를 떠나 창의력, 즉 문제를 풀기 위한 아이디어를 떠올릴 수 있는 능력을 요구한다.

대표적인 연습 문제로 '거스름돈' 문제가 있다. 이 문제는 가장 큰 화폐의 단위부터 거슬러 주며 최소의 동전만 사용하는 게 해결책이다.

그리디 알고리즘의 정당성

거스름돈 문제에서 그리디 알고리즘으로 최적의 해를 찾을 수 있는 이유는 ✨큰 단위가 작은 단위의 배수이기 때문이다.

작은 단위를 여러번 반복하지 말고 큰 단위로 해결한 후 작은 단위를 이용하거나, 큰 단위로 해결할 수 있도록 작은 단위를 최소한으로 이용한 후 큰 단위를 이용하는 것이다.

대부분의 그리디 알고리즘 문제는 이처럼 문제 풀이를 위한 최소한의 아이디어를 떠올리고 이것이 정당한지 검토할 수 있어야 답을 도출할 수 있다.

실전 문제

💡큰 수의 법칙

n, m, k = map(int, input().split())
numList = list(map(int, input().split()))
numList.sort(reverse=True)
#가장 큰 수가 더해지는 횟수
cnt = int(m/(k+1)) * k
cnt += m % (k+1) #m이 k+1로 로 나누어 떨어지지 않는다면

ans = 0
ans += cnt * numList[0] #큰 수 더하기
ans += (m-cnt) * numList[1] #두 번째로 큰 수 더하기

print(ans)

이 문제는 합이 최대인 m길이의 리스트를 만들면 된다. 가장 큰 수 k번 + 두 번째로 큰 수 1번 -> 이 수열이 반복되는 게 중요하다.

✨(가장 큰 수가 더해지는 횟수 * 가장 큰 수) + ((m - 가장 큰 수가 더해지는 횟수) * 두 번째로 큰 수)를 구하면 정답이다.

88885888858 에서 마지막 1개의 8처럼 m이 k+1로 나누어 떨어지지 않을 때도 고려하여 cnt % (k+1)를 더하는 것이다.

💡숫자 카드 게임

n, m = map(int, input().split())
ans = 0

for _ in range(n):
    cardList = list(map(int, input().split()))
    minCard = min(cardList)  # 입력 받으면서 최솟값 빼내기
    ans = max(ans, minCard)  # 둘 중 더 큰 값을 대입

print(ans)

✨행을 입력 받을 때 최솟값을 뽑아 그 중 최댓값을 구하면 된다.

ans에 행의 최솟값을 대입하고, 다음 리스트를 입력 받으면 그 리스트의 최솟값과 비교하여 더 큰 값을 대입하는 방식이다.

💡1이 될 때까지

n, k = map(int, input().split())
cnt = 0

while True:
    target = (n//k)*k #k의 배수로 만들기
    cnt += (n-target) #target과 n의 차이만큼 카운트(1빼는 연산 카운트)
    n = target #n을 k의 배수로 만들기 위해

    if n < k: #더 이상 나눌 수 없을 때 탈출
        break

    cnt += 1 #나눌 수 있다면 나누고 카운트
    n //= k #n값 변경

cnt += (n-1) #남은 수에서 1씩 빼기
print(cnt)

💡거스름돈과 비슷하면서 다른 문제라고 느껴졌다. 이 문제는 n이 k의 배수가 될 때까지 1씩 빼는 과정을 반복해야 한다.

즉, 거스름 돈은 큰 금액만큼 빼고 작은 금액을 빼면 그만이지만 이 문제는 빼고 나누고 빼고 나누고를 반복하는 경우가 생기는 것이다. (이 포인트에서 방황했거든 내가(￣y▽,￣)╭ )

위 코드는 배수로 만들기 위해 1을 빼는 과정을 반복하지 않고 한 번에 빼기 위해 나머지 연산자를 이용했다. 나머지만큼 1씩 뺀다면(카운트 한다면) 보다 효율적인 코드가 된다.

1. 배수 만들기(1씩 빼는 연산)
2. n < k라면 탈출
3. 아니라면 k로 나누는 연산

이 과정을 반복한 후 2번에서 탈출한 수, 남은 수에서 1씩 빼는 연산을 1이 될 때까지 해주면 된다.

무한히 큰 배열에 다음과 같이 분수들이 적혀있다.

1/1 1/2 1/3 1/4 1/5 … 2/1 2/2 2/3 2/4 … … 3/1 3/2 3/3 … … … 4/1 4/2 … … … … 5/1 … … … … … … … … … … … 이와 같이 나열된 분수들을 1/1 → 1/2 → 2/1 → 3/1 → 2/2 → … 과 같은 지그재그 순서로 차례대로 1번, 2번, 3번, 4번, 5번, … 분수라고 하자.

X가 주어졌을 때, X번째 분수를 구하는 프로그램을 작성하시오.

해결 방법

1. 몇 번째 라인인지 찾기
2. 라인 내에서 몇 번째인지 찾기
3. 라인이 짝수냐 홀수냐에 따라 규칙을 적용해 출력

이 문제는 지그재그의 규칙을 찾으면 풀 수 있다. 지그재그의 한 라인내 분수의 수는 1, 2, 3, 4로 늘어나며 라인이 짝수 번이면 분자가 1씩 늘어나지만 짝수 번이면 1씩 줄어든다. 숫자를 나열해보면 찾을 수 있음!🙌

while inputN > max: 
    line += 1 
    max += line
gap = max - inputN

gap으로 분모와 분자를 구할 수 있어서 위와같은 과정이 필요하다.

나는 최댓값 자체를 공식으로 구해서 input값과의 차를 이용해 해결하려 했지만 오히려 복잡해지더라...✨ 그래서 아래처럼 했다 챗지피티최고

제출

inputN = int(input()) #입력받기

line = 0 #사선 라인
max = 0 #그 라인에서 마지막 분수가 모든 분수 중 몇번째인지
while inputN > max: #사선 라인 구하기
    line += 1 #line이 1,2,3으로 늘어나면서 최대 번호도 그만큼씩 늘어남
    max += line
gap = max - inputN #라인 내에서 몇번째 분수인지 구하기

if line % 2 == 0: #사선 라인이 짝수번
    top = line - gap 
    under = gap + 1
else:
    top = gap + 1 #사선 라인이 홀수번
    under = line - gap

print(f'{top}/{under}')

메모

레전드 삽질했던 문제지만 이런 규칙 문제가 재밌긴 해 😂♥

베르트랑 공준은 임의의 자연수 n에 대하여, n보다 크고, 2n보다 작거나 같은 소수는 적어도 하나 존재한다는 내용을 담고 있다. 예를 들어, 10보다 크고, 20보다 작거나 같은 소수는 4개가 있다. (11, 13, 17, 19) 또, 14보다 크고, 28보다 작거나 같은 소수는 3개가 있다. (17,19, 23) 자연수 n이 주어졌을 때, n보다 크고, 2n보다 작거나 같은 소수의 개수를 구하는 프로그램을 작성하시오.

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 케이스는 n을 포함하는 한 줄로 이루어져 있다. 입력의 마지막에는 0이 주어진다.

각 테스트 케이스에 대해서, n보다 크고, 2n보다 작거나 같은 소수의 개수를 출력한다.

해결 방법

이전 글에서 했던 에라토스테네스의 체 를 이용해 풀면 된다.

범위가 n~2n이라는 점, 0 입력시 종료되는 점만 달라서 그 부분을 수정해주면 해결된다.

제출

import math

#입력, 출력 반복문
while True:
    n = int(input())
    if n == 0: #0입력 시 끝
        break
    #0이 아니면 소수 개수 카운트
    arr = [True for _ in range(2*n +1)]
    arr[0], arr[1] = False, False

    for i in range(2,int(math.sqrt(2*n))+1): #2부터 n의 제곱근까지
        if arr[i]: #i가 남은 수인 경우
            for j in range(i*2,2*n+1,i):
                arr[j] = False #배수는 False처리

    cnt = 0

    for k in range (n+1,(2*n)+1):
        if arr[k]:
            cnt += 1
    print(cnt)

메모

반복해서 익히자 ლ(╹◡╹ლ)

M이상 N이하의 소수를 모두 출력하는 프로그램을 작성하시오. 첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다. 한 줄에 하나씩, 증가하는 순서대로 소수를 출력한다.

해결 방법

소수를 판별하는 방법은 크게 아래 3가지가 있다.

1. 간단한 방법
2. 제곱근
3. 에라토스테네스의 체

간단한 방법 👉2~n-1까지 전부 나눠보기

def prime(n):
    for i in range(2,n):
        if n % i == 0:
            return False
        return True

2부터 n-1까지 전부 나눠보며 나머지가 0이라면 즉, 나누어 떨어진다면 약수가 있다는 뜻이므로 해당 수는 소수가 아니게 된다.

>_**제곱근**_
👉n의 _**약수 계산 범위를 줄이는**_ 방법
👉몫과 나누는 값의 대칭을 이용해 제곱근 까지만 약수 검사를 한다.
>>```python
import math
def prime(n):
    for i in range(2,int(math.sqrt(n))+1):
        if n % 1 == 0:
            return False
    return True

에라토스테네스의 체 👉여러 수에 대해 소수 판별의 해야 하는 상황에 사용 가능 👉에라토스테네스의 체에 대해

아래 제출 코드 참고

제출

💡제곱근 이용 코드

시간: 5324ms

import math
m,n=map(int,input().split())

for i in range(m,n+1): #n부터 m까지 반복
    if i==1: #1은 소수가 아니므로
        continue #제외
    for j in range(2,int(math.sqrt(i))+1): #제곱근까지
        if i%j==0: #나누어 떨어지면 약수가 존재하므로
            break #다음 i로
    else:
        print(i) #약수가 없다면 출력

💡에라토스테네스의 체 이용 코드

시간: 284ms

m,n=map(int,input().split())

arr = [True]*(n+1) #리스트 생성
arr[0] = False
arr[1] = False

for i in range(2,int(n**0.5)+1): #2부터 n의 제곱근까지
    if arr[i]: #i가 남은 수인 경우
        for j in range(i*2,n+1,i): #range(start, stop, step)
            arr[j] = False

#소수 출력            
for i in range(m,n+1):
    if arr[i]:
        print(i)

👉range(i*2,n+1,i) range에 step값까지 적는 코드는 처음 써봤다. i*2부터 n까지 i를 간격으로 전부 False처리하는 것으로 약수가 있는 수를 제거하는 것이다.

메모

어떤 알고리즘을 쓰냐에 따라 시간 차이가 이렇게 난다(o′┏▽┓｀o) 한 문제를 여러 방법으로 풀어보는 연습을 꾸준히 하자.

하루에 한 번 산을 넘어가는 떡 장사 할머니는 호랑이에게 떡을 주어야 산을 넘어갈 수 있는데, 욕심 많은 호랑이는 어제 받은 떡의 개수와 그저께 받은 떡의 개수를 더한 만큼의 떡을 받아야만 할머니를 무사히 보내 준다고 한다.

예를 들어 첫째 날에 떡을 1개 주었고, 둘째 날에는 떡을 2개 주었다면 셋째 날에는 1+2=3개, 넷째 날에는 2+3=5개, 다섯째 날에는 3+5=8개, 여섯째 날에는 5+8=13개를 주어야만 무사히 산을 넘어갈 수 있다.

우리는 산을 무사히 넘어온 할머니에게 오늘 호랑이에게 몇 개의 떡을 주었는지, 그리고 오늘이 호랑이를 만나 떡을 준지 며칠이 되었는지를 알아내었다. 할머니가 호랑이를 만나서 무사히 넘어온 D째 날에 준 떡의 개수가 K개임을 알 때, 여러분은 할머니가 호랑이를 처음 만난 날에 준 떡의 개수 A, 그리고 그 다음 날에 호랑이에게 준 떡의 개수 B를 계산하는 프로그램을 작성하시오. 이 문제에서는 항상 1 ≤ A ≤ B 이다.

예를 들어 여섯 번째 날에 산을 무사히 넘어온 할머니가 호랑이에게 준 떡이 모두 41개라면, 호랑이를 만난 첫 날에 준 떡의 수는 2개, 둘째 날에 준 떡의 수는 7개이다. 즉 셋째 날에는 9개, 넷째 날에는 16개, 다섯째 날에는 25개, 여섯째 날에는 41개이다. 따라서 A=2, B=7 이 된다. 단 어떤 경우에는 답이 되는 A, B가 하나 이상일 때도 있는데 이 경우에는 그 중 하나만 구해서 출력하면 된다.

해결 방법

이 문제 점화식은 피보나치 수열에서 끌어왔다.

💡그러다 만난 문제점 이건 초기 a,b 값을 모르잖아...?

👉그래서 a, b를 각각 1,1로 초기설정 한 다음 원하는 k값이 안 나오면 a, b 값을 조정해주는 방법을 사용했다.

제출

#할머니가 넘어온 날, 그 날에 준 떡의 개수
d,k = map(int,input().split())

d_list = [0 for i in range(d)] #떡 개수 저장할 리스트
d_list[0],d_list[1] = 1,1 #a,b값 1,1로 초기화

while(True):
    for i in range(2, d):
        d_list[i] = d_list[i-1]+d_list[i-2]

    #a값을 1씩 올리며 맞는 a,b 값 찾기
    if d_list[-1] == k:
        print(d_list[0], d_list[1],sep='\n')
        break

    elif d_list[-1] > k:
        d_list[0] += 1
        d_list[1] = d_list[0]
    else:
        d_list[1] += 1

메모

아놔 문제 똑바로 안 읽고 d, k값 따로 입력 받아서 이유 모르는 오답처리 10번 먹었다.ㅋ.

눈이..있으면.....문제..를...잘..좀..읽자...✍(◔◡◔)

인하은행에는 ATM이 1대밖에 없다. 지금 이 ATM앞에 N명의 사람들이 줄을 서있다. 사람은 1번부터 N번까지 번호가 매겨져 있으며, i번 사람이 돈을 인출하는데 걸리는 시간은 Pi분이다. 줄을 [2, 5, 1, 4, 3] 순서로 줄을 서면, 2번 사람은 1분만에, 5번 사람은 1+2 = 3분, 1번 사람은 1+2+3 = 6분, 4번 사람은 1+2+3+3 = 9분, 3번 사람은 1+2+3+3+4 = 13분이 걸리게 된다. 각 사람이 돈을 인출하는데 필요한 시간의 합은 1+3+6+9+13 = 32분이다. 이 방법보다 더 필요한 시간의 합을 최소로 만들 수는 없다.

줄을 서 있는 사람의 수 N과 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어졌을 때, 각 사람이 돈을 인출하는데 필요한 시간의 합의 최솟값을 구하는 프로그램을 작성하시오.

해결 방법

1. 대기 시간 리스트 오름 차순 정렬

뒤에 서있는 사람은 앞 사람의 모든 소요 시간을 더하게 된다. 그러므로 소요시간이 긴 사람이 뒤에 서있어야 최소 시간을 구할 수 있다.

2. 반복문으로 대기 시간의 합 구하기

2번째 사람은 1번째 사람의 시간 + 2번째 사람의 시간만큼 기다리고 3번째 사람은 1+2+3번째 사람의 시간을 기다린다.

즉, 2중 반복문으로 i, j를 이용하여 이들의 합을 구한다.

제출

import sys 
input = sys.stdin.readline

n = int(input()) #총 몇 명
time_list = list(map(int,input().split())) #시간 리스트

time_list.sort() #오름차순 정렬
cnt = 0

for i in range(n): #n까지 순서대로
    for j in range(i+1): #이전 사람들의 시간과 본인(i)의 시간 합
        cnt += time_list[j]

print(cnt)

메모

.sort()를 .sort라고 적고 런타임에러 5번 봤다★,°:.☆(￣▽￣)/$:.°★ 。이런 실수... 적당히 하자 젭알

독일 로또는 {1, 2, ..., 49}에서 수 6개를 고른다. 로또 번호를 선택하는데 사용되는 가장 유명한 전략은 49가지 수 중 k(k>6)개의 수를 골라 집합 S를 만든 다음 그 수만 가지고 번호를 선택하는 것이다. 예를 들어, k=8, S={1,2,3,5,8,13,21,34}인 경우 이 집합 S에서 수를 고를 수 있는 경우의 수는 총 28가지이다. ([1,2,3,5,8,13], [1,2,3,5,8,21], [1,2,3,5,8,34], [1,2,3,5,13,21], ..., [3,5,8,13,21,34]) 집합 S와 k가 주어졌을 때, 수를 고르는 모든 방법을 구하는 프로그램을 작성하시오.

해결 방법

파이썬에서 조합을 구하는 방법 중 기본 라이브러리인 itertools를 사용했다. 파이썬 공식 문서

💡조합형 이터레이터

_두개 이상_의 리스트에서의 조합

✨product(p, q)

_하나의 리스트_에서 r길이의 조합

✨permutations(p, r) 순열: (A,B)와 (A,B)는 다르다. 모든 가능한 순서로 반복 요소 없는 결과.

✨combinations(p, r) 조합: (A,B)와 (A,B)는 같다. 정렬된 순서로 반복 요소 없는 결과.

제출

from itertools import combinations
import sys 
input = sys.stdin.readline

while True:
    num_list = list(map(int,input().split()))
    k = num_list[0] #num_list이 첫 요소는 k
    s = num_list[1:] #num_list에서 첫 요소 빼고 s에 저장

    if k == 0: #가 0이면 조합X
        break
    else:
        a_list = list(combinations(s,6))
        for i in a_list:
            for j in range(len(i)):
                print(i[j], end=' ')
            print() #줄 바꿈
        print() #줄 바꿈

상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 봉지는 3킬로그램 봉지와 5킬로그램 봉지가 있다. 상근이는 귀찮기 때문에, 최대한 적은 봉지를 들고 가려고 한다. 예를 들어, 18킬로그램 설탕을 배달해야 할 때 5킬로그램 3개와 3킬로그램 1개를 배달하면, 더 적은 개수의 봉지를 배달할 수 있다. N킬로그램 배달해야 할 때, 봉지 몇 개를 가져가면 되는지 그 수를 구하는 프로그램을 작성하시오.

첫째 줄에 N이 주어진다. (3 ≤ N ≤ 5000) 상근이가 배달하는 봉지의 최소 개수를 출력한다. 만약, 정확하게 N킬로그램을 만들 수 없다면 -1을 출력한다.

해결 방법

💡 5의 배수가 될 때까지 3씩 빼다가 5의 배수가 되면 5로 나눈 몫을 카운트한다.

제출

n = int(input())
cnt = 0

while n >= 0: #n이 0이상일 동안   
    if n % 5 == 0: #n이 5의 배수라면
        cnt += n // 5 #n을 5로 나눈 몫만큼 카운트
        print(cnt)
        break
    else: #n이 5의 배수가 아니라면(배수가 될 때까지 반복)
        n -= 3 #3뻬고
        cnt += 1 # 카운트 +1
else: 
    print(-1)

☝ while 반복문으로 n이 0 이상이라면 동작하도록 한다.

☝ 코드별 설명은 주석으로 (∩^o^)⊃━☆

이석원은 조규현과 백승환에게 상대편 마린(류재명)의 위치를 계산하라는 명령을 내렸다. 조규현과 백승환은 각각 자신의 터렛 위치에서 현재 적까지의 거리를 계산했다.

조규현의 좌표 (x1, y1)와 백승환의 좌표 (x2, y2)가 주어지고, 조규현이 계산한 류재명과의 거리 r1과 백승환이 계산한 류재명과의 거리 r2가 주어졌을 때, 류재명이 있을 수 있는 좌표의 수를 출력하는 프로그램을 작성하시오.

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 이루어져 있다.

한 줄에 x1, y1, r1, x2, y2, r2가 주어진다. x1, y1, x2, y2는 -10,000보다 크거나 같고, 10,000보다 작거나 같은 정수이고, r1, r2는 10,000보다 작거나 같은 자연수이다.

각 테스트 케이스마다 류재명이 있을 수 있는 위치의 수를 출력한다. 만약 류재명이 있을 수 있는 위치의 개수가 무한대일 경우에는 -1을 출력한다.

해결 방법

이 문제는 보자마자 아 이건 원 써야한다.

조규현, 백승환의 좌표를 각 원의 중점으로, r1, r2를 각 원의 반지름으로 보고 정점이 생기는 케이스를 나눠 조건문으로 문제를 해결하면 된다.

r1 + r2(두 반지름의 합)과 (x1,x2),(x2,y2)(두 중점의 거리) 를 비교하면 정점이 몇 개 생기는 지 알 수 있다.

제출

import math

n = int(input()) #케이스의 수
for _ in range(n):
    x1, y1, r1, x2, y2, r2 = list(map(int,input().split())) #리스트 입력받기

    #두 중점 사이의 거리
    dis = math.sqrt((x1-x2)**2 + (y1-y2)**2)

    if dis == 0: #두 원의 중심이 같고
        if r1 == r2: #두 원의 반지름이 같으면
            print(-1) #-1 출력
        else: #중심은 같으나 반지름이 다른 경우 = 원 안에 원
            print(0) #0출력
    else: #두 원의 중심이 다르고
        if r1+r2 == dis or abs(r2-r1) == dis: #dis와 반지름의 합이 같다면
            print(1) #1출력
        elif (abs(r1-r2) < dis) and (dis < (r1+r2)): #dis가 반지름의 합보다 작다면
            print(2) #2출력
        else:
            print(0) #중심이 다르고 dis가 반지름의 합보다 크다면 두 원의 접점이 없다

👉문제에서 정점이 무한대인 경우는 -1 을 출력하라 했으니 두 원이 같으면 -1을 출력한다.

👉sqrt, abs 사용 이유는 코딩 도장-두 점 사이 거리 구하기 참고 ☜(⌒▽⌒)☞ ✨

메모

문제 다 잘 풀었는데 자꾸 컴파일 에러 떠서 보니까 들여쓰기가 이상했다.. 내 잘못인가 리플릿 잘못인가 (╯‵□′)╯︵