Data Structure & Algorithm/문제풀이 & 코딩테스트 검색 결과

해당 글 11건
[이것이취업을위한코딩테스트다] chap09 - 최단 경로 알고리즘

최단 경로 알고리즘 가장 짧은 경로를 찾는 알고리즘으로 다음과 같은 다양한 문제 상황에 쓰인다. 1) 한 지점에서 다른 한 지점까지의 최단 경로 2) 한 지점에서 다른 모든 지점까지의 최단 경로 3) 모든 지점에서 다른 모든 지점까지의 최단 경로 각 지점은 그래프에서 노드로 표현, 연결된 선은 간선으로 표현한다. 다익스트라 최단 경로 알고리즘 특정한 노드에서 출발하여 다른 모든 노드로 가는 최단경로 계산으로, 음의 간선이 없을 때 정상적으로 동작한다. 그리디 알고리즘으로, 매 상황에서 가장 비용이 적은 노드를 선택해 과정을 반복한다. 동작 과정 1) 출발 노드를 설정한다. 2) 최단 거리 테이블을 초기화한다. 3) 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택한다. 4) 해당 노드를 거쳐..
Data Structure & Algorithm/문제풀이 & 코딩테스트 2022. 3. 2. 22:30
[이것이 취업을 위한 코딩테스트다] chap08 - 다이나믹 프로그래밍

다이나믹 프로그래밍 다이나믹 프로그래밍은 최적의 해를 구하기에 연산 속오데 한계가 있고, 메모리 공간을 사용할 수 있는 데이터 개수도 한정적일 때 중복되는 연산을 줄이면서 공간을 최대한으로 활용하기 위해 탄생되었다. 동적 계획법이라고도 하며, 2가지 방식(탑다운과 보텀업)이 있으며 메모이제이션 기법이 주료 사용된다. 위와 같이 피보나치 수열이 있을 때 아래와 같이 점화식을 나타날 수 있다. 반복되는 값이 있을 때, 점화식을 통해 나타내고 이 점화식을 코드로 구현하면 다이나믹 프로그래밍 유형을 풀 수 있다. 피보나치 수열을 이진 탐색 트리로 구현했을 때, 위와 같이 동일한 함수가 반복적으로 호출되는 것을 알 수 있다. 불필요한 연산을 수행함으로써 연산 속도가 느려지고 메모리 공간을 많이 차지하는 단점이 있..
Data Structure & Algorithm/문제풀이 & 코딩테스트 2022. 2. 23. 18:36
[이것이취업을위한코딩테스트다] chap07 - 이진 탐색

이진 탐색 이진 탐색은 배열 내부의 데이터가 정렬되어 있어야 사용할 수 있는 알고리즘이다. 시작점, 끝점, 중간점을 활용하여 찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적을 비교해 범위를 절반씩 좁혀가며 탐색하는 과정이다. 위와 같이 맨 처음 원소를 시작점, 마지막 원소를 끝점, 총 개수에서 2를 나눈 값을(소수점은 버린다) 중간점으로 둔다. 위와 같이 반씩 줄여가며 비교하다가 찾으려는 값과 중간점에 위치한 데이터가 같을 시 탐색을 종료한다. 절반씩 데이터가 줄어든다는 점으로 시간 복잡도는 O(logN)이다. 코딩 테스트에서의 이진 탐색 이진 탐색은 코딩 테스트에서 단골로 나오는 문제이고, 폭넓게 적용되기 때문에 난이도가 높고 구현할 코드량이 많아 실수하기 쉽다. 그래서 이진 탐색 코드를 암기하고..
Data Structure & Algorithm/문제풀이 & 코딩테스트 2022. 2. 23. 18:26
[이것이취업을위한코딩테스트다] chap06 - 두 배열의 원소 교체

두 배열의 원소 교체 두 배열을 입력으로 받아 A와 B배열의 원소들을 K번 만큼 교환해서 A의 합이 최대가 되도록 한다. 코드 n, k = map(int, input().split()) arr_A = list(map(int, input().split())) arr_B = list(map(int, input().split())) arr_A.sort() arr_B.sort(reverse=True) for i in range(k): if arr_A[i] < arr_B[i]: arr_A[i], arr_B[i] = arr_B[i], arr_A[i] else: break sum(arr_A) 문제 풀이 A의 배열을 최대가 될 수 있도록 교환하려면 먼저 A배열은 오름차순, B배열을 내림차순 정렬한다. 그 후 K번 만큼..
Data Structure & Algorithm/문제풀이 & 코딩테스트 2022. 2. 17. 13:20
[이것이취업을위한코딩테스트다] chap06 - 성적이 낮은 순서로 학생 출력하기

문제 학생 이름과 성적을 입력받아, 학생의 이름을 성적이 낮은 순서대로 출력하는 문제이다. 코드 # 성적이 낮은 순서로 학생 출력하기 def grade_ascending(arr): temp = sorted(arr, key=lambda student:student[1]) for student in temp: print(student[0], end=' ') n = int(input()) arr = [] for i in range(n): input_data = input().split() arr.append((input_data[0], int(input_data[1]))) grade_ascending(arr) 해설 sorted()함수안에 key=lambda를 활용해 정렬을 진행한다. 정보를 tuple형태로 받..
Data Structure & Algorithm/문제풀이 & 코딩테스트 2022. 2. 17. 11:10
[이것이취업을위한코딩테스트다] chap06 - 위에서아래로

위에서 아래로 수열을 큰 수부터 작은 순서로 정렬하는 프로그램을 만드시오. N개의 수열을 입력받아 내림차순 정렬하는 프로그램을 작성하는 문제이다. # 위에서 아래로 def descending(arr): arr.sort(reverse=True) for elem in arr: print(elem, end=' ') n = int(input()) temp = [] for i in range(n): num = int(input()) temp.append(num) descending(temp) 위와 같이 sort(reverse=True)를 통해 내림차순 정렬하여 구현할 수 있다.
Data Structure & Algorithm/문제풀이 & 코딩테스트 2022. 2. 17. 10:55