algorithm
-
코테 정리 및 공부algorithm/이것이 취업을 위한 코딩테스트다 2023. 9. 11. 16:56
기본 문법 - 진수 & 알파벳과 정수 # 16진수 변환 int(a, 16) # 알파벳의 정수값 ord(x) # 정수의 알파벳 값 chr(x) - 반올림 값 print( format(x, ".2f") ) - 최대공약수와 최소공배수 import math # 최대공약수 math.gcd(a,b) # 최소공배수 (a * b) // math.gcd(a,b) - i 부터 j 까지의 원소를 역순으로 변경 my_list[i:j+1] = reversed(my_list[i:j+1]) - exception 처리 try: # ... except: # ... - 삼항 (true logic) if (조건문) else (false logic) - replace 키워드 ( 재저장해야한다 ) # 공백제거 replaced_a = a.re..
-
파이썬 문법algorithm/이것이 취업을 위한 코딩테스트다 2023. 8. 24. 14:35
리스트 컴프리헨션 # 0부터 9까지의 수를 포함하는 리스트 array = [i for i in range(10)] # 0부터 19까지의 수 중에서 홀수만 포함하는 리스트 array = [i for i in range(20) if i % 2 == 1] # 1부터 9까지의 수들의 제곱 값을 포함하는 리스트 array = [i * i for i in range(1, 10)] so-리스트 컴프리헨션은 2차원 리스트를 초기화할 때 효과적으로 사용될 수 있다. - 특히 N x M 크기의 2차원 리스트를 한 번에 초기화 해야 할 때 매우 유용하다. ㆍ좋은 예시 : array = [[0] * m for _ in range(n)] - 만약 2차원 리스트를 초기화할 때 다음과 같이 작성하면 예기치 않은 결과가 나올 수 있..
-
PART04 - APPENDIX B 기타 알고리즘algorithm/이것이 취업을 위한 코딩테스트다 2023. 8. 23. 14:23
소수 판별 알고리즘 - 소수(Prime Number) : 1보다 큰 자연수 중에서 1과 자기 자신을 제외한 자연수로는 나누어떨어지지 않는 자연수이다. 약수의 성질 - 모든 약수가 가운데 약수를 기준으로 곱셈 연산에 대해 대칭을 이룬다. - 따라서 우리는 특정한 자연수의 모든 약수를 찾을 때 가운데 약수(제곱급)까지만 확인하면 된다. import math # 소수 판별 함수 (2이상의 자연수에 대하여) def is_prime_number(x): # 2부터 x의 제곱급까지의 모든 수를 확인하며 for i in range(2, int(math.sqrt(x)) + 1): # x가 해당 수로 나누어 떨어진다면 if x % i == 0: return False# 소수가 아님 return True# 소수임 소수의 판..
-
PART02 - CHAPTER 10. 그래프 이론algorithm/이것이 취업을 위한 코딩테스트다 2023. 3. 26. 17:13
1. 다양한 그래프 알고리즘 이미 배운 내용을 훑어보자 - 10장에서 다룰 알고리즘은 앞서 배운 내용에 기반하는데, 예를 들어 크루스칼 알고리즘(Kruskal Algorithms)은 그리디 알고리즘으로 분류되며, 위상 정렬 알고리즘(Topology Algorithms)은 앞서 배운 큐 자료 구조 혹은 스택 자료구조를 활용해야 구현할 수 있다. - 다른 장에 비해서 비중은 낮은 편이지만, 코딩 테스트를 꼼꼼히 준비하기 위해서 지금부터 배울 내용을 잘 숙지하도록 하자. - 그래프(Graph)란 노드(Node)와 노드 사이에 연결된 간선(Edge)의 정보를 가지고 있는 자료구조를 의미한다. - 알고리즘 문제를 접했을 때 '서로 다른 개체(혹은 객체(Object))가 연결되어 있다' 는 이야기를 드릉면 가장 먼..
-
PART02 - CHAPTER 09. 최단 경로algorithm/이것이 취업을 위한 코딩테스트다 2023. 3. 26. 17:07
1. 가장 빠른 길 찾기 가장 빠르게 도달하는 방법 - 최단 경로(Shortest Path) 알고리즘은 말 그대로 가장 짧은 경로를 찾는 알고리즘이다. - 그래서 '길찾기' 문제라고도 불린다. - 최단 경로 알고리즘 유형에는 다양한 종류가 있는데, 상황에 맞는 효율적인 알고리즘이 이미 정립되어 있다. - 예를 들어 '한 지점에서 다른 특정 지점까지의 최단 경로를 구해야 하는 경우', '모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야하는 경우' 등의 다양한 사례가 존재한다. - 이런 사례를 맞는 알고리즘을 알고 있다면 문제를 좀 더 쉽게 풀 수 있다. - 최단 경로 문제는 보통 그래프를 이용해 표현하는데 각 지점은 그래프에서 '노드'로 표현되고, 지점간 연결된 도로는 그래프에서 '간선'으로 표..
-
PART02 - CHAPTER 08. 다이나믹 프로그래밍algorithm/이것이 취업을 위한 코딩테스트다 2023. 3. 26. 17:05
1. 다이나믹 프로그래밍 중복되는 연산을 줄이자 - 현실 세계에서는 다양한 문제가 있다. 그런데 이 중에서 컴퓨터를 활용해도 해결하기 어려운 문제는 무엇일까? ㆍ최적의 해를 구하기에 시간이 매우 많이 필요하거나 메모리 공간이 매우 많이 필요한 문제 등이 컴퓨터로도 해결하기 어려운 문제이다. ㆍ컴퓨터는 연산 속도에 한계가 있고, 메모리 공간을 사용할 수 있는 데이터의 개수도 한정적이라는 점이 많은 제약을 발생시킨다. ㆍ그래서 우리는 연산 속도와 메모리 공간을 최대한으로 활용할 수 있는 효율적인 알고리즘을 작성해야한다. * 해결하기 어려운 문제에 대해서 깊게 다루는 분야로는 계산 복잡도 이론이 있다. ㆍ이 부분에 대해서 깊게 공부하기 위해서는 P-NP 문제를 다루는 계산 복잡도 이론에 대해서 공부해보는 것을..
-
PART02 - CHAPTER 07. 이진 탐색algorithm/이것이 취업을 위한 코딩테스트다 2023. 3. 26. 17:03
1. 범위를 반씩 좁혀가는 탐색 순차 탐색 - 순차 탐색(Sequential Search)이란 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 차례대로 확인하는 방법 - 보통 정렬되지 않은 리스트에서 데이터를 찾아야 할 때 사용한다. - 리스트 내에 데이터가 아무리 많아도 시간만 충분하다면 항상 원하는 원소(데이터)를 찾을 수 있다는 장점이 있다,. - 순차 탐색은 이름처럼 순차로 데이터를 탐색한다는 의미이다. - 리스트의 데이터 하나씩 방문하며 특정한 문자열과 같은지 검사하므로 구현도 간단하다. - 순차 탐색은 정말 자주 사용되는데, 리스트에 특정 값의 원소가 있는지 체크할 때도 순차 탐색으로 원소를 확인하고, - 리스트 자료형에서 특정한 값을 가지는 원소의 개수를 세는 coun..
-
PART02 - CHAPTER 06. 정렬algorithm/이것이 취업을 위한 코딩테스트다 2023. 3. 26. 17:02
1. 기준에 따라 데이터를 정렬 정렬 알고리즘 개요 - 정렬(Sorting)이란 데이터를 특정한 기준에 따라서 순서대로 나열하는 것을 말한다. - 프로그램에서 데이터를 가공할 때 오름차순이나 내림차순 등 대부분 어떤 식으로든 정렬해서 사용하는 경우가 많기에 정렬 알고리즘은 프로그램을 작성할 때 가장 많이 사용되는 알고리즘 중 하나다. - 정렬 알고리즘으로 데이터를 정렬하면 다음 장에서 배울 이진 탐색(Binary Search)이 가능해진다. - 정렬 알고리즘은 이진 탐색의 전처리 과정이기도 하니 제대로 알고 넘어가자! - 정렬 알고리즘은 굉장히 다양한데 이 중에서 많이 사용하는 선택 정렬, 삽입 정렬, 퀵 정렬, 계수 정렬만 이 책에서 언급한다. - 더불어 파이썬에서 제공하는 기본 정렬 라이브러리를 적용..