근성프로그래머 이준형

서로소 집합 공통 원소가 없는 두 집합을 의미한다. 서로소 집합 자료구조란 서로소 부분 집합을로 나누어진 원소들의 데이터를 처리하기 위한 자료구조이다. 1. union(합집합) 연산을 확인하여, 서로 연결된 두 노드 A, B를 확인한다. I. A와 B의 루트 노드 A', B'를 각각 찾는다. II. A'를 B'의 부모 노드로 설정한다(B'가 A'를 가리키도록 한다.) 2. 모든 union(합집합) 연산을 처리할 때까지 1번 과정을 반복한다. Step 0. 초기 단계에서는 가장 먼저 노드의 개수(V) 크기의 부모 테이블을 초기화한다. 이때 모든 원소가 자기 자신을 부모로 가지도록 설정한다. 현재 원소의 개수가 6이므로, 초기 단계에서는 총 6개의 트리가 존재하는 것과 같다. 노드 번호 1 2 3 4 5 6..

책 리뷰/이것이 취업을 위한 코딩테스트다 2024. 1. 9. 13:44

최단 경로 알고리즘은 말 그대로 가장 짧은 경로를 찾는 알고리즘이다. 이 책에서는 다익스트라, 프로이드 워셜 알고리즘이 빈도수가 높아 그 두개의 유형을 다룬다. 다익스트라 최단 경로 알고리즘 그래프에서 여러 개의 노드가 있을 때, 특정한 노드에서 출발하여 다른 노드로 가는 각각의 최단 경로를 구해주는 방법. 음의 간선이 없을 때 정상적으로 동작. 음의 간선이란 0보다 작은 값을 가지는 간선을 의미. 원리는 다음과 같다. 1. 출발 노드를 설정한다. 2. 최단 거리 테이블을 초기화한다. 3. 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택한다. 4. 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블을 갱신한다. 5. 위 과정에서 3과 4번을 반복한다. 1차원 리스트에 저장..

책 리뷰/이것이 취업을 위한 코딩테스트다 2024. 1. 5. 14:25

알고리즘 강의 시간에 배웠던 프로그래밍 기법이다. 탑다운과 바텀업 방식이 있고, 이것을 위해 사용하는 메모이제이션 기법이 있다. 수학자들은 점화식을 사용해서 수열의 항이 이어지는 형태를 간결하게 표현한다. 우리는 점화식을 이용해 현재의 항을 이전의 항에 대한 식으로 표현할 수 있다. 프로그래밍에서는 점화식에 사용되는 수열을 배열이나 리스트로 표현할 수 있다. 다이나믹 프로그래밍은 아래의 조건을 만족해야 사용할 수 있다. 1. 큰 문제를 작은 문제로 나눌 수 있다. 2. 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다. 피보나치 수열은 이러한 조건을 만족하는 대표 문제이다. 메모이제이션은 한 번 구한 결과를 메모리 공간에 메모해두고 같은 식을 다시 호출하면 메모한 결과를 그대로 가져오는 ..

책 리뷰/이것이 취업을 위한 코딩테스트다 2024. 1. 4. 12:42

순차 탐색(Sequential Search) 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 차례대로 확인하는 방법이다. 프로그래밍언어를 배우는데 많이 실습 해봤을 탐색이다. 이진 탐색(Binary Search) 찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교해서 원하는 데이터를 찾는 방법 시간 복잡도 : O(logN) 재귀함수로 구현하는 방법과 반복문으로 구현하는 방법이있다. 먼저 재귀함수로 구현하는 방법이다. # 재귀 함수로 구현한 이진 탐색 소스코드 def binary_search(array, target, start, end): if start > end: return None mid = (start + end) // 2 # 찾은 경우 반환 if array[m..

책 리뷰/이것이 취업을 위한 코딩테스트다 2024. 1. 3. 12:58

정렬이란 데이터를 특정한 기준에 따라서 순서대로 나열하는 것을 말한다. 본 책에서는 선택, 삽입, 퀵, 계수 정렬을 다루고, 파이썬의 정렬 라이브러리를 다룬다. 1. 선택 정렬 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸고, 그 다음 작은 데이터를 선택해 앞에서 두 번째 데이터와 바꾸는 과정을 반복하는것. 가장 작은 것을 선택한다는 의미에서 선택정렬이라고 한다. 시간복잡도는 O(N^2)이다. array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8] for i in range(len(array)): min_index = i for j in range(i + 1, len(array)): if array[min_index] > array[j]: min_index = j array[i],..

책 리뷰/이것이 취업을 위한 코딩테스트다 2024. 1. 2. 12:56

꼭 필요한 자료구조 기초 탐색(Search) : 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정을 의미한다. 자료구조(Data Structure) : 데이터를 표현하고 관리하고 처리하기 위한 구조 스택 : 선입후출 구조(First In Last Out) 또는 후입선출 구조(Last In First Out)라고 한다. 파이썬에서는 list를 통해 append로 삽입, pop을 통해 삭제를 할 수 있다. # 스택 stack = [] stack.append(5) stack.append(2) stack.append(3) stack.append(7) stack.pop() stack.append(1) stack.append(4) stack.pop() print(stack) print(stack[::-1]) 큐 ..

책 리뷰/이것이 취업을 위한 코딩테스트다 2023. 12. 27. 14:09

이 책에서는 완전 탐색, 시뮬레이션 유형을 모두 '구현' 유형으로 묶어서 다루고 있다. 완전탐색은 모든 경우의 수를 주저 없이 다 계산하는 해결방법이다. 시뮬레이션은 문제에서 제시한 알고리즘을 한 단계식 차례대로 직접 수행하는 해결방법이다. 코딩테스트나 여러 구현문제를 풀면서 느꼈던 점은 자료구조가 있으면 수행시간을 단축시킬 수 있는 장점이 있지만, 구현문제는 순수 피지컬 싸움이란것을 많이 느꼈다. 해당 책에서도 별도의 이론이 없다. 예제 4-1 상하좌우 유저의 시작좌표는 (1,1)이고 주어진 명령(R, L, U, D)을 통해서 이동된 좌표를 구하는 문제이다. 아래는 내가 작성한 코드이지만, 책의 저자는 더 깔끔하게 코드를 작성했다. L, R, U, D에 따른 이동 방향을 list를 통해 나타냈다. BF..

책 리뷰/이것이 취업을 위한 코딩테스트다 2023. 12. 26. 13:35

그리디 알고리즘은 현재 상황에서 지금 당장 좋은 것만 고르는 방법이다. 나중에 미칠 영향에 대해서는 고려하지 않는다. 여러 개의 데이터를 빠르게 정렬해야 하는 문제는 정렬 라이브러리 사용 방법을 알아야한다. 문제에서 '가장 큰 순서대로', '가장 작은 순서대로' 라는 기준을 알게 모르게 제시해준다. 예제 3-1 거스름돈 거스름돈으로 500원, 100원, 50원, 10원 짜리 동전이 무한히 존재할 떄, 손님에게 거슬러 줘야 할 돈의 동전의 최소 갯수를 구하라. 이 예제를 처음 접근했을 때에는 동전의 갯수가 최소여야 하므로 화폐단위가 큰 순서부터 나누기, 나머지 연산을 하면 되겠다는 생각을 했다. 아래 예시는 1,260원을 받았을 때이다. def solution(n): answer = 0 coins = [5..

책 리뷰/이것이 취업을 위한 코딩테스트다 2023. 12. 23. 18:39