Coding Test/Python29

• 

  [알고리즘] 최단 경로 (Shortest Path) : Dijkstra (다익스트라), Floyd-Warshall (플로이드 워셜) 본 정리내용은 '이것이 취업을 위한 코딩 테스트다 with 파이썬' 교재를 참고 했습니다. 독학하는 용도로 글을 작성하는 것이고, 혹여나 잘못된 부분이 있다면 댓글 써주시면 감사하겠습니다. 최단 경로 알고리즘 최단 경로 알고리즘은 가장 짧은 경로를 찾는 알고리즘을 의미함. '길 찾기' 문제라고도 불린다. 다양한 문제 상황 한 지점에서 다른 한 지점까지의 최단 경로 한 지점에서 다른 모든 지점까지의 최단 경로 모든 지점에서 다른 모든 지점까지의 최단 경로 각 지점은 그래프에서 노드로 표현 지점 간 연결된 도로는 그래프에서 간선으로 표현 코딩 테스트에서는 최단 경로를 모두 출력하는 문제보다는 단순히 최단 거리를 출력하도록 요구하는 문제가 많이 출제됨. 최단 경로 알고리즘 : 다익스트라 최단 경로 알고리즘, .. Coding Test/Python 2021. 10. 11.

• 

  [알고리즘] 다이나믹 프로그래밍 (Dynamic Programming) 본 정리내용은 '이것이 취업을 위한 코딩 테스트다 with 파이썬' 교재를 참고 했습니다. 독학하는 용도로 글을 작성하는 것이고, 혹여나 잘못된 부분이 있다면 댓글 써주시면 감사하겠습니다. 다이나믹 프로그래밍 다이나믹 프로그래밍은 메모리를 적절히 사용하여 수행 시간 효율성을 비약적으로 향상시키는 방법이다. 이미 계산된 결과(작은 문제)는 별도의 메모리 영역에 저장하여 다시 계산하지 않도록 한다. 다이나믹 프로그래밍의 구현은 일반적으로 두 가지 방식(탐다운과 보텀업)으로 구성된다. 다이나믹 프로그래밍은 동적 계획법이라고도 부른다. 일반적인 프로그래밍 분야에서의 동적(Dynamic)이란? 자료구조에서 동적 할당 (Dynamic Allocation)은 '프로그램이 실행되는 도중에 실행에 필요한 메모리를 할당하.. Coding Test/Python 2021. 8. 22.

• 

  [알고리즘] 이진 탐색 (Binary Search), 트리 자료구조 본 정리내용은 '이것이 취업을 위한 코딩 테스트다 with 파이썬' 교재를 참고 했습니다. 독학하는 용도로 글을 작성하는 것이고, 혹여나 잘못된 부분이 있다면 댓글 써주시면 감사하겠습니다. 순차 탐색 (Sequential Search) : 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 차례대로 확인하는 방법 보통 정렬되지 않은 리스트에서 데이터를 찾아야 할 때 사용한다. 리스트 내에 데이터가 아무리 많아도 시간만 충분하다면 항상 원하는 원소(데이터)를 찾을 수 있다. 리스트에 특정 값의 원소가 있는지 체크할 때 순차 탐색으로 원소를 확인한다. 리스트 자료형에서 특정한 값을 가지는 원소의 개수를 세는 count() 메서드를 이용할 때도 순차 탐색으로 원소를 확인한다. # 순차 탐색.. Coding Test/Python 2021. 8. 15.

• 

  [알고리즘] 정렬 (선택 정렬, 삽입 정렬, 퀵 정렬, 계수 정렬, 정렬 라이브러리) 본 정리내용은 '이것이 취업을 위한 코딩 테스트다 with 파이썬' 교재를 참고 했습니다. 독학하는 용도로 글을 작성하는 것이고, 혹여나 잘못된 부분이 있다면 댓글 써주시면 감사하겠습니다. 정렬 (Sorting) : 데이터를 특정한 기준에 따라 순서대로 나열하는 것 일반적으로 문제 상황에 따라서 적절한 정렬 알고리즘이 공식처럼 사용된다. 정렬 알고리즘으로 데이터를 정렬하면 이진 탐색 (Binary Search)이 가능해진다. 정렬 알고리즘은 이진 탐색의 전처리 과정이다. 선택 정렬 (Selection Sort) 처리되지 않은 데이터 중에서 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸는 것을 반복한다. 회색 카드 : 현재 정렬되지 않은 데이터 중에서 가장 작은 데이터 하늘색 카드 : 이미 정렬된.. Coding Test/Python 2021. 8. 13.

• 

  [알고리즘] 탐색 알고리즘 DFS/BFS 본 정리내용은 '이것이 취업을 위한 코딩 테스트다 with 파이썬' 교재를 참고 했습니다. 독학하는 용도로 글을 작성하는 것이고, 혹여나 잘못된 부분이 있다면 댓글 써주시면 감사하겠습니다. 그래프(Graph)의 기본 구조 그래프는 노드(Node)(또는 정점(Vertex))와 간선(Edge)로 표현 된다. 그래프 탐색이란 하나의 노드를 시작으로 다수의 노드를 방문하는 것을 말한다. 두 노드가 간선으로 연결되어 있다면 '두 노드는 인접하다(Adjacent)'라고 표현한다. 인접 행렬(Adjacency Matrix) : 2차원 배열로 그래프의 연결 관계를 표현하는 방식 위와 같이 연결된 그래프를 인접 행렬로 표현할 때 파이썬에서는 2차원 리스트로 구현할 수 있다. 연결이 되어 있지 않은 노드끼리는 무한(Inf.. Coding Test/Python 2021. 8. 12.

• 

  [알고리즘] 자료구조 기초 (스택, 큐, 재귀함수) 본 정리내용은 '이것이 취업을 위한 코딩 테스트다 with 파이썬' 교재를 참고 했습니다. 독학하는 용도로 글을 작성하는 것이고, 혹여나 잘못된 부분이 있다면 댓글 써주시면 감사하겠습니다. 탐색 (Search) : 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정 프로그래밍에서는 그래프, 트리 등의 자료구조 안에서 탐색을 하는 문제를 자주 다룬다. 대표적인 탐색 알고리즘 : DFS, BFS DFS/BFS는 코딩 테스트에서 매우 자주 등장하는 유형이므로 반드시 숙지해야함. 자료구조 (Data Structure) : 데이터를 표현하고 관리하고 처리하기 위한 구조 삽입 (Push) : 데이터를 삽입한다. 삭제 (Pop) : 데이터를 삭제한다. 오버플로우 (Overflow) : 특정한 자료구조가 수용할 수 있.. Coding Test/Python 2021. 8. 12.

• 

  [알고리즘] 구현 (Implementation) 본 정리내용은 '이것이 취업을 위한 코딩 테스트다 with 파이썬' 교재를 참고 했습니다. 독학하는 용도로 글을 작성하는 것이고, 혹여나 잘못된 부분이 있다면 댓글 써주시면 감사하겠습니다. 구현 (Implementation) : 머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정 흔히 알고리즘 대회에서 구현 유형의 문제란 무엇을 의미할까? 풀이를 떠올리는 것은 쉽지만 소스코드로 옮기기 어려운 문제를 지칭한다. 완전 탐색 : 모든 경우의 수를 주저 없이 다 계산하는 해결 방법 시뮬레이션 : 문제에서 제시한 알고리즘을 한 단계씩 차례대로 직접 수행해야는 문제 유형 구현 유형의 예시 알고리즘은 간단한데 코드가 지나칠 만큼 길어지는 문제 실수 연산을 다루고, 특정 소수점 자리까지 출력해야 하는 문제 문자열을 특정한.. Coding Test/Python 2021. 8. 11.

• 

  [알고리즘] 그리디 (Greedy) 본 정리내용은 '이것이 취업을 위한 코딩 테스트다 with 파이썬' 교재를 참고 했습니다. 독학하는 용도로 글을 작성하는 것이고, 혹여나 잘못된 부분이 있다면 댓글 써주시면 감사하겠습니다. 그리디 (Greedy) : 탐욕법; 현재 상황에서 지금 당장 좋은 것만 고르는 방법 매 순간 가장 좋아보이는 것을 선택하며, 현재의 선택이 나중에 미칠 영향에 대해서는 고려하지 않는다. 일반적인 그리디 알고리즘은 문제를 풀기 위한 최소한의 아이디어를 떠올릴 수 있는 능력을 요구한다. 그리디 해법은 그 정당성 분석이 중요하다. 단순히 가장 좋아 보이는 것을 반복적으로 선택해도 최적의 해를 구할 수 있는지 검토. 일반적인 상황에서 그리디 알고리즘은 최적의 해를 보장할 수 없을 때가 많다. 하지만 코딩 테스트에서의 대부분의.. Coding Test/Python 2021. 8. 10.

• 

  [Python 문법] 자주 사용되는 표준 라이브러리 [실전에서 유용한 표준 라이브러리] 내장 함수 : 기본 입출력 함수부터 정렬 함수까지 기본적인 함수들을 제공합니다. 파이썬 프로그램을 작성할 때 없어서는 안 되는 필수적인 기능을 포함하고 있습니다. itertools : 파이썬에서 반복되는 형태의 데이터를 처리하기 위한 유용한 기능들을 제공합니다. 특히 순열과 조합 라이브러리는 코딩 테스트에서 자주 사용됩니다. heapq : 힙(Heap) 자료구조를 제공합니다. 일반적으로 우선순위 큐 기능을 구현하기 위해 사용됩니다. (e.g. 다익스트라) bisect : 이진 탐색 (Binary Search) 기능을 제공합니다. collections : 덱(deque), 카운터(Counter) 등의 유용한 자료구조를 포함합니다. math : 필수적인 수학적 기능을 제공.. Coding Test/Python 2021. 8. 9.

• 

  [Python 문법] 함수와 람다 표현식 [함수] 함수(Function)란 특정한 작업을 하나의 단위로 묶어 놓은 것을 의미합니다. 함수를 사용하면 불필요한 소스코드의 반복을 줄일 수 있습니다. [함수의 종류] 내장 함수 : 파이썬이 기본적으로 제공하는 함수 사용자 정의 함수 : 개발자가 직접 정의하여 사용할 수 있는 함수 [함수 정의하기] 프로그램에는 똑같은 코드가 반복적으로 사용되어야 할 때가 많습니다. 함수를 사용하면 소스코드의 길이를 줄일 수 있습니다. 매개변수 : 함수 내부에서 사용할 변수 반환 값 : 함수에서 처리 된 결과를 반환 def add(a, b): return a + b print(add(3, 7)) def add(a, b): print('함수의 결과:', a + b) add(3, 7) [실행 결과] [파라미터 지정하기] 파.. Coding Test/Python 2021. 8. 9.

• 

  [Python 문법] 반복문 [반복문] 특정한 소스코드를 반복적으로 실행하고자 할 때 사용하는 문법입니다. 파이썬에서는 while문과 for문이 있는데, 어떤 것을 사용해도 상관 없습니다. 다만 코딩 테스트에서의 실제 사용 예시를 확인해 보면, for문이 더 간결한 경우가 많습니다. i = 1 result = 0 # i가 9보다 작거나 같을 때 아래 코드를 반복적으로 실행 while i = 80: print(i + 1, "번 학생은 합격입니다.") [실행 결과] 3. 중첩된 반복문 : 구구단 예제 for i in range(2, 10): for j in range(1, 10): print(i, "X", j, "=", i * j) print() [실행 결과] Coding Test/Python 2021. 8. 9.

• 

  [Python 문법] 조건문 [조건문] 조건문은 프로그램의 흐름을 제어하는 문법입니다. 조건문을 이용해 조건에 따라서 프로그램의 로직을 설정할 수 있습니다. x = 15 if x >= 10: print("x >= 10") if x >= 0: print("x >= 0") if x >= 30: print("x >= 30") [실행 결과] [들여쓰기] 파이썬에서는 코드의 블록(Block)을 들여쓰기(Indent)로 지정합니다. 다음의 코드에서 2번 라인은 무조건 실행됩니다. 탭을 사용하는 쪽과 공백 문자(space)를 여러 번 사용하는 쪽으로 두 진영이 있습니다. 이에 대한 논쟁은 지금까지도 활발합니다. 파이썬 스타일 가이드라인에서는 4개의 공백 문자를 사용하는 것을 표준으로 설정하고 있습니다. [조건문의 기본 형태] 조건문의 기본적인 .. Coding Test/Python 2021. 8. 9.