티스토리

Seoromin's DataScience

검색하기

블로그 홈

Seoromin's DataScience

seoromin.tistory.com/m

데이터 사이언스 님의 블로그입니다.

구독자: 1

방명록 방문하기

주요 글 목록

[이것이취업을위한코딩테스트다] chap09 - 최단 경로 알고리즘 최단 경로 알고리즘 가장 짧은 경로를 찾는 알고리즘으로 다음과 같은 다양한 문제 상황에 쓰인다. 1) 한 지점에서 다른 한 지점까지의 최단 경로 2) 한 지점에서 다른 모든 지점까지의 최단 경로 3) 모든 지점에서 다른 모든 지점까지의 최단 경로 각 지점은 그래프에서 노드로 표현, 연결된 선은 간선으로 표현한다. 다익스트라 최단 경로 알고리즘 특정한 노드에서 출발하여 다른 모든 노드로 가는 최단경로 계산으로, 음의 간선이 없을 때 정상적으로 동작한다. 그리디 알고리즘으로, 매 상황에서 가장 비용이 적은 노드를 선택해 과정을 반복한다. 동작 과정 1) 출발 노드를 설정한다. 2) 최단 거리 테이블을 초기화한다. 3) 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택한다. 4) 해당 노드를 거쳐.. 공감수 0 댓글수 0 2022. 3. 2.
[이것이 취업을 위한 코딩테스트다] chap08 - 다이나믹 프로그래밍 다이나믹 프로그래밍 다이나믹 프로그래밍은 최적의 해를 구하기에 연산 속오데 한계가 있고, 메모리 공간을 사용할 수 있는 데이터 개수도 한정적일 때 중복되는 연산을 줄이면서 공간을 최대한으로 활용하기 위해 탄생되었다. 동적 계획법이라고도 하며, 2가지 방식(탑다운과 보텀업)이 있으며 메모이제이션 기법이 주료 사용된다. 위와 같이 피보나치 수열이 있을 때 아래와 같이 점화식을 나타날 수 있다. 반복되는 값이 있을 때, 점화식을 통해 나타내고 이 점화식을 코드로 구현하면 다이나믹 프로그래밍 유형을 풀 수 있다. 피보나치 수열을 이진 탐색 트리로 구현했을 때, 위와 같이 동일한 함수가 반복적으로 호출되는 것을 알 수 있다. 불필요한 연산을 수행함으로써 연산 속도가 느려지고 메모리 공간을 많이 차지하는 단점이 있.. 공감수 0 댓글수 0 2022. 2. 23.
[이것이취업을위한코딩테스트다] chap07 - 이진 탐색 이진 탐색 이진 탐색은 배열 내부의 데이터가 정렬되어 있어야 사용할 수 있는 알고리즘이다. 시작점, 끝점, 중간점을 활용하여 찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적을 비교해 범위를 절반씩 좁혀가며 탐색하는 과정이다. 위와 같이 맨 처음 원소를 시작점, 마지막 원소를 끝점, 총 개수에서 2를 나눈 값을(소수점은 버린다) 중간점으로 둔다. 위와 같이 반씩 줄여가며 비교하다가 찾으려는 값과 중간점에 위치한 데이터가 같을 시 탐색을 종료한다. 절반씩 데이터가 줄어든다는 점으로 시간 복잡도는 O(logN)이다. 코딩 테스트에서의 이진 탐색 이진 탐색은 코딩 테스트에서 단골로 나오는 문제이고, 폭넓게 적용되기 때문에 난이도가 높고 구현할 코드량이 많아 실수하기 쉽다. 그래서 이진 탐색 코드를 암기하고.. 공감수 0 댓글수 0 2022. 2. 23.
[이것이취업을위한코딩테스트다] 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번 만큼.. 공감수 0 댓글수 0 2022. 2. 17.
[이것이취업을위한코딩테스트다] 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형태로 받.. 공감수 0 댓글수 0 2022. 2. 17.
[이것이취업을위한코딩테스트다] 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)를 통해 내림차순 정렬하여 구현할 수 있다. 공감수 0 댓글수 0 2022. 2. 17.
[이것이코딩테스트다] chap06 정렬 - 이론 정렬 - 데이터를 특정한 기준에 따라서 순서대로 나열하는 것 선택 정렬 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸고, 그 다음 작은 데이터를 선택해 앞에서 두 번째 데이터와 바꾸는 과정. 즉 '가장 작은 것을 선택'한다는 의미에서 선택 정렬(Selection Sort) 위와 같이 바꿀 데이터를 제외하고 뒤에 있는 데이터 중에서 가장 작은 하나를 골라, 바꾼 데이터와 교환하는 형식이다. 위와 같이 현재 값을 min_index로 초기화하고, 그 뒤 값들과 비교해가며 min_index값보다 작으면 교환해주는 형태이다. 시간복잡도는 N-1번만큼 가장 작은 수를 찾아 맨 앞으로 보낸다. 또한 매번 가장 작은 수를 찾기 위해 비교 연산을 수행하는데, n + (n-1) + (n-2) + ... + 2로 .. 공감수 0 댓글수 0 2022. 2. 17.
[이것이취업을위한코딩테스트다] chap05 - 미로 탈출 미로 탈출 N X M크기의 직사각형 형태의 미로가 있다. 최초 위치는 (1,1)이고 미로의 출구는 (N,M)이며 한 번에 한 칸씩 이동할 수 있다. 괴물이 있는 부분은 0, 없는 부분은 1로 괴물을 피해 탈출하기 위해 움직여야 하는 최소 개수를 구하시오. 칸을 셀 때는 시작 칸과 마지막 칸을 모두 포함해서 계산한다. 코드 # 미로 탈출 from collections import deque n, m = map(int, input().split()) graph = [] for i in range(n): graph.append(list(map(int, input()))) dx = [-1, 1, 0, 0] dy = [0, 0, -1, 1] def bfs(x, y): queue = deque() queue.app.. 공감수 0 댓글수 0 2022. 2. 16.
[이것이취업을위한코딩테스트다] Chap05 - 음료수 얼려 먹기 DFS/BFS 실전문제 - 음료수 얼려먹기 위와 같이 N X M 크기의 얼음 틀이 있다. 구멍이 뚫려 있는 부분은 0, 칸막이가 존재하는 부분은 1로 표시된다. 구멍이 뚫려 있는 부분끼리 상,하,좌,우로 붙어 있는 경우 서로 연결되어 있는 것으로 간주한다. 이 때 얼음 틀의 모양이 주어졌을 때 생성되는 총 아이스크림의 개수를 구하는 프로그램을 작성하시오. 위와 같은 얼음 틀 예시에서는 아이스크림이 총 3개 생성된다. 입력조건, 출력조건, 입력예시는 다음과 같다. n, m = map(int, input().split()) graph = [] for i in range(n): graph.append(list(map(int, input()))) def dfs(x, y): if x = n or y = m: re.. 공감수 0 댓글수 0 2022. 2. 16.
[이것이취업을위한코딩테스트다] chap05 - DFS/BFS 이론 탐색(Search) - 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정 자료구조(Data Structure) - 데이터를 표현하고 관리하고 처리하기 위한 구조 스택과 큐는 자료구조 기초 개념으로 '삽입(Push)'과 '삭제(Pop)'라는 두 핵심적인 함수로 구성된다. 또한 오버플로와 언더플로라는 데이터의 크기를 벗어난 상태에서 연산을 수행했을 때 나타나는 문제들도 고려해야 한다. 스택(Stack) 선입후출(First In Last Out)구조로, 박스처럼 먼저 들어온 데이터가 나중에 출력되는 형태이다. 위와 같이 삽입과 삭제를 반복하고, 삭제 시 가장 나중에 들어온 데이터가 삭제되는 구조이다. python 코드로 구현 시 위와 같이 [::-1]를 통해 리스트를 뒤집어서 구현할 수 있다. append(.. 공감수 1 댓글수 1 2022. 2. 16.
[이코테 chapter3] 그리디 그리디 알고리즘(탐욕법) : 현재 상황에서 지금 당장 좋은 것만 고르는 방법. 매 순간 가장 좋아 보이는 것을 선택하며, 현재의 선택이 나중에 미칠 영향에 대해서는 고려하지 않는다. 다른 유형에 비해 알고리즘의 사용 방법을 정확히 알고 있어야 하지 않아도 됨. 예시) 그리디 알고리즘이란? 사진과 같은 노드가 있을 때, 루트 노드로부터 시작하여 거쳐 가는 노드 값의 합을 최대로 만들고자 한다. 그럼 다음과 같이 5 + 7 + 9로 진행하여 21이 되는 것이 최적의 루트이다. 하지만 그리디 알고리즘을 활용해 매 상황(현재 위치)에서 가장 큰 값만 반환을 하게 된다면 5 -> 10 -> 4로 된다. 이는 최적의 해인 21보다는 낮은 값이다. 즉 그리디 알고리즘은 최적의 해를 보장할 수 없을 때가 많아, 그리디.. 공감수 0 댓글수 0 2022. 2. 9.

문의안내

티스토리
로그인
고객센터

티스토리는 카카오에서 사랑을 담아 만듭니다.