DOing

💡 정렬 알고리즘 정렬이란, 데이터를 특정한 기준에 따라서 순서대로 나열하는 것을 말한다. 정렬 알고리즘은 굉장히 다양한데 이번 포스팅에서는 가장 많이 사용하는 선택 정렬, 삽입 정렬, 퀵 정렬, 계수 정렬을 다뤄보려고 한다. 정렬 수행시에는 상황에 맞는 알고리즘을 선택해야 효율적으로 작동할 수 있다. 선택 정렬 삽입 정렬 퀵 정렬 계수 정렬 시간 복잡도 O(N^2) O(N^2) O(NlogN) O(N+K) 공간 복잡도 O(N) O(N) O(N) O(N+K) 추천 상황 간단 거의 정렬되어 있는 경우 일반적인 경우 데이터 크기 범위가 작은 경우 (N : 데이터의 갯수, K : 데이터 최대값의 크기) * 현 포스팅에서는 오름차순만 다루고 있다. 내림차순 정렬은 알고리즘에서 크기 비교를 반대로 수행하거나 리스..

💡 BFS 알고리즘 Breath-First Search, 그래프에서 가까운 부분을 우선적으로 탐색하는 알고리즘이다. 너비 우선 탐색이라고도 한다. 데이터가 N개 있을때 O(N)시간 복잡도를 가진다. 일반적인 경우 실제 수행시간은 DFS보다 좋은편이다. [DFS vs BFS] 동작 방식 동작 원리 구현 인접한 노드가 여러개라면? DFS 멀리 있는(깊게 있는)노드 부터 탐색 스택 재귀 함수 이용 한개씩 넣음 BFS 가까운 노드부터 탐색 큐 큐 자료구조 이용 한번에 다 넣음 💡 BFS 동작과정 1. 탐색 시작 노드를 큐에 삽입하고 방문 처리를 한다. 2. 큐에서 노드를 꺼내 해당 노드의 인접노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문처리를 한다, 3. 2번과정을 더이상 수행할 수 없을 때까지 반..

💡 DFS 알고리즘 Depth-First Search, 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이다. 데이터의 갯수가 N개인 경우, O(N)의 시간복잡도를 가진다. 💡 DFS 동작과정 1. 탐색 시작 노드를 스택에 삽입하고 방문 처리를 한다. 2. 스택의 최상단 노드에 방문하지 않은 인접 노드가 있다면, 그 인접노드를 스택에 넣고 방문 처리를 한다. 방문하지 않은 인접노드가 없으면, 스택에서 최상단 노드를 꺼낸다. 3. 2번과정을 더이상 수행할 수 없을 때까지 반복한다. [참고] 그래프의 두 노드가 가나선으로 연결되어 있다면 '두 노드는 인접하다'라고 표현한다. DFS에서 인접한 노드가 여러개 일 수 있다. 그래서 스택에 어떠한 노드부터 방문할 것인지에 대한 기준이 필요하다. 이는 문제마다 다..

💡 구현 구현이란 '알고리즘을 소스코드로 바꾸는 과정'이라고 할 수 있다. 알고리즘 교재에서는 대부분 구현을 별도의 유형으로 다루지 않지만, 코딩테스트에서는 구현이 중심으로 되는 문제가 자주 출제되기 때문에 다뤄보기로 한다. 보통 구현문제는 '풀이를 떠올리는 것은 쉽지만 소스코드로 옮기기 어려운 문제'를 의미한다. 예를 들어서 완전 탐색, 시뮬레이션 문제 유형이 있다. 완전 탐색은 모든 경우의 수를 계산하는 방법을 의미하고, 시뮬레이션은 문제에서 제시한 알고리즘을 한단계씩 차례대로 직접 수행해야하는 문제유형을 의미한다. 💡 주의점 완전 탐색처럼 많은 경우의 수를 계산할때 주의해할 점은 일반 코딩 테스트환경에서는 파이썬으로 제출한 코드가 1초에 2000만번(2*10^7)의 연산을 수행하는 것이다. 대부분의..

💡 그리디 알고리즘 "지금 당장 좋은 것만 고르는 방법" 한국어로 번역하면 탐욕법이라고 할 수 있는데, 이름 그대로 어떠한 문제가 생겼을 때 단순 무식하게 탐욕적으로 문제를 해결하는 알고리즘이다. 단순하지만 강력한 문제 해결방법이다. 💡 그리디 알고리즘 사용시 주의점 그리디 알고리즘의 해가 '최적 해'를 항상 보장하는 것은 아니다. 때문에 그리디 알고리즘을 적용할 때 주의해야할 것은 "해당 방법이 정당성을 가지고 있는가?"이다. 💡 그리디 알고리즘 대표적 예시 Q1. 거스름돈 구하기 당신은 음식점의 계산을 도와주는 점원이다. 카운터에는 거스름돈으로 사용할 500원, 100원, 50원, 10원 짜리 동전이 무한히 존재한다. 손님에게 거슬러 줘야할 돈이 N원일때 거슬러 줘야할 동전의 최소개수를 구하라. [문..

저번 포스팅에서는 정규표현식에 대해 알았습니다. 이어서 이번 포스팅에서는 정규표현식을 파이썬에서 어떻게 사용하는지에 대해 알아보겠습니다. 💡 정규표현식 with 파이썬 지금까지 정규표현식이란 무엇인지에 대해서 알아보았습니다. 지금부터는 이를 파이썬에서 어떻게 사용되는지에 대해서 알아보겠습니다. 파이썬에서는 정규표현식을 지원하는 re모듈을 제공합니다. re모듈은 파이썬을 설치할때 자동으로 설치되는 기본 라이브러리로 사용법은 다음과 같습니다. import re p = re.compile('ab*') # 패턴객체 생성 이렇게 만든 패턴 객체를 사용하여 문자열을 검색하는 방법에는 4가지가 있습니다. 💡 match() match 메서드는 문자열의 처음부터 정규식과 매치되는지 조사합니다. import re p = ..

정규 표현식을 이용하게되면 원하는 문자열을 간단하게 검색할 수 있습니다. 원하는 문자열이 복잡하더라도 짧고 간결한 코드로 검색할 수 있다는 것이 장점입니다. 💡 정규표현식? 특정한 규칙을 가진 문자열의 집합을 표현하는데 사용되는 형식언어입니다. 주로 문자열 검색과 치환에 쓰입니다. 정규표현식은 표준인 POSIX의 정규표현식과 POSIX에서 확장된 perl방식의 PCRE가 대표적입니다. 이외에도 수많은 정규표현식이 존재합니다. 약간의 차이점은 있지만 거의 비슷합니다. 💡 정규표현식의 기초, 메타 문자 정규표현식에 사용하는 기호를 메타 문자라고 합니다. 메타문자는 표현식 내부에서 특정한 의미를 가지는 문자를 말합니다. 지금부터 메타문자의 종류에 대해서 알아보겠습니다. . ^ $ * + ? { } [ ] \ ..

파이썬 내장 함수인 join, split을 이용해 문자열과 리스트 사이 변환을 해줄 수 있다. join : 리스트->문자열 split : 문자열->리스트 💡 join 리스트를 특정 구분자를 포함해 문자열로 변환해주는 함수 animals = ['사자', '코끼리', '기린', '원숭이', '바나나'] # ","를 포함시켜 리스트->문자열 print(",".join(animals)) # "\n"를 포함시켜 리스트->문자열 print("\n".join(animals)) # "/"를 포함시켜 리스트->문자열 print("/".join(animals)) 💡 split 문자열을 특정 구분자를 기준으로 나누어 리스트로 변환해주는 함수 animal="원숭이/기린/코끼리" # 특정 구분자를 기준으로 문자열->리스트 pr..