[TIL][240725] Search, Retrieve, 2차원 배열, CS 개념

어떤 문제가 있었나?

스쿼드 세션에서 첫 알고리즘 문제를 풀지 못했다. 행렬 덧셈 문제였는데 빨리 풀어야 한다는 생각에 슈도 코드 작성도 하지 않고 무작정 vscode부터 실행했고, 행렬을 직접 구현하려니 너무 막막했다. 알고리즘 강의를 많이 못 들었어도 코드카타 열심히 풀고 개념 정리도 했는데 안 풀리니 조금은 좌절했다.

---

무엇을 시도했나?

세션에서 풀이 내용을 집중해서 보고 스스로 다시 풀어봐야겠단 생각이 들었다. 풀이를 보고 다시 푸는 것임에도 불구하고 풀이가 어려웠다. 행렬에 대해서 다시 공부하고, 문제를 정확히 이해한 다음, 슈도 코드를 작성해 봤다. 잘 안 써본 map, join, spit()을 써보려고 노력해 봤다.

---

어떻게 해결됐는가?

세션을 통해서 이미 로직을 알고 있는 상태라 천천히 코드를 작성해 봤다. 중간중간 print()를 이용하여 과정을 체크했다. 튜터님은 코드를 하나하나 풀어쓰는 것도 좋다고 했지만, map을 거의 안써봤기 때문에 오히려 map을 이용해봤다. 

'''
<행렬 덧셈>
행렬의 크기 입력
A, B 행렬 구현
두 행렬 더하기
우리가 아는 행렬 모양 출력
'''
# 행렬 만들기
N, M = map(int, input().split())
# print(N, M)
a_matrix = []
for i in range(N):
    row = list(map(int, input().split()))
    # print(row)
    # # [1, 1, 1]
    # # [2, 2, 2]
    # # [0, 1, 0]
    a_matrix.append(row)
# print(a_matrix)  # [[1, 1, 1], [2, 2, 2], [0, 1, 0]]

b_matrix = []
for i in range(N):
    row = list(map(int, input().split()))
    # print(row)
    # # [3, 3, 3]
    # # [4, 4, 4]
    # # [5, 5, 100]
    b_matrix.append(row)
# print(b_matrix)  # [[3, 3, 3], [4, 4, 4], [5, 5, 100]]

# 두 행렬 A, B 더한 값 구하기
sum_matrix = []
for i in range(N):
    sum_temp = []
    for j in range(M):
        sum_row = a_matrix[i][j] + b_matrix[i][j]
        # print(sum_row)  # 4 4 4 6 6 6 5 6 100
        sum_temp.append(sum_row)
    # print(sum_temp)
    # # [4, 4, 4]
    # # [6, 6, 6]
    # # [5, 6, 100]
    sum_matrix.append(sum_temp)
# print(sum_matrix)  # [[4, 4, 4], [6, 6, 6], [5, 6, 100]]

# 행렬 모양 만들기
for i in sum_matrix:
    result = " ".join(map(str, i))
    print(result)

중간 중간 print() 출력을 해보고 주석으로 달아놨더니 로직 이해하기가 수월했다. 마지막 행렬 모양 만들기는 풀이와 다른 방식으로 풀어봤다.

---

새로 알게 된 점은 무엇인가?

Search & Retrieve

Search: 검색하다

• get an index from an element
• 인덱스를 알고 있지 않으므로 보통 특정 원소(요소)의 인덱스를 찾는 과정 (값으로 인덱스를 찾을 수 있다.)

Retrieve: 검색하다(가져오다)

• get an element from an index
• 이미 인덱스(위치)를 알고 있으므로 특정 인덱스나 위치에서 해당하는 원소(요소)를 가져오는 과정

선형탐색 linear search in an unsorted array

• exhaustive search: 모든 경우를 탐색하는 방법(순열, 조합, 중복순열)
• sequential search: 찾고자 하는 키값을 대조하여 첫 번째 원소부터 끝까지 하나씩 탐색
• visit the elements in the array from the first position until we find the key element.

def linear_search(array, key):
    for idx in range(len(array)):
        if array[idx] == key:
            return idx
    return -1

#예시
arr = [10, 24, 35, 47, 53, 67, 89]
key = 47
result = linear_search(arr, key)
if result != -1:
    print(f"The element {key} is present in the array")
else:
    print(f"{key} not found")

이진탐색 binary search in a sorted array

• 정렬(sorting)된 배열에서만 가능

def binary_search(arr, target):
    left = 0
    right = len(arr) - 1

    while left <= right:
        mid = left + (right - left) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1

# 예시
arr = [10, 24, 35, 47, 53, 67, 89]
target = 47
result = binary_search(arr, key)
if result != -1:
    print(f"{target} found at index {result}")
else:
    print(f"{target} not found")

분할 정복 기법 divide & conquer

• selet the middle fo the array and divide the array by itself
• 큰 문제를 작은 문제들로 쪼개서 작은 문제들을 해결하는 것으로 큰 문제를 해결하는 방법
• Solve a problem of n inputs by splitting the input into k subsets(하위 집합) three steps of divided & conquer
  • divide: Breaking a problem into subproblem
  • conquer: Recursively solving these subproblems ➡️ 재귀 함수로 풀이 가능
  • combine(optional): Appropriately combining their answers
• EX) 이분 탐색, 병합 정렬(merge sort), 퀵 소트(quick sort), 토너먼트

➡️ 알고리즘 공부는 모든 영역이 연결되어 있기 때문에 step by step으로 할 수 없다. 

 

2차원 배열

• 우리가 이미 알던 행렬 matrix이고 모든 알고리즘의 기초가 되는 기본기이다.

2차 배열

반드시 알아야 하는 CS 용어 정리

• 프로세스: 실행 중인 프로그램
• 프로세싱: 프로그램이 실행 중인 것
• 멀티태스킹: 하나의 시스템이나 cpu가 여러 작업을 수행하는 것
  - 동시에 처리되는 것은 아니지만 시분할 방식을 통해 동시에 처리하는 것처럼 보인다.
• 멀티프로세싱: 두 개 이상의 프로세스가 동시에 실행되는 것
  - 여러 개의 cpu가 여러 작업을 동시에 수행함
• 멀티스레드: 하나의 프로세스가 여러 작업 단위를 가지며 작업을 수행하는 것
  - 크롬 하나로 여러 사이트를 사용하는 것
• 스케쥴링: 작업에 필요한 자원을 언제 누가 어떻게 사용할지 결정해 주는 것
• 커널: 하드웨어와 응용 프로그램 사이에서 인터페이스 역할을 수행하기 위한 핵심 부분
• 터미널: 사용자와 컴퓨터 간에 상호작용을 제공하는 인터페이스
• CUI(Character User Interface): 사용자가 문자를 통해 명령을 수행하는 것을 의미
• GUI(Graphic User Interface): 사용자가 그래픽을 통해 명령을 수행하는 것을 의미

---

무엇을 느꼈고 내일은 무엇을 할까?

너무 어려워서 12시간이 부족하다고 느껴질 만큼 공부할게 많았다. 내일은 조금 일찍 공부를 시작해야겠다. 스쿼드 알고리즘 숙제, 코드카타 2문제, 알고리즘 강의 수강... 바쁘다 바빠!