AI Platform / Web

DFS (깊이 우선 탐색) DFS 깊이 우선 탐색은 코딩테스트에서 기본적으로 알아야한다. DFS란 말 그대로 깊이를 우선적으로 탐색하는 방법이다. 좀 더 쉽게 말하면, 갈림길이 있다면 한방향으로 끝까지 간 후에 답을 확인하는 과정을 반복한다. 따라서 재귀함수를 기본적으로 이해를 해야한다. 재귀함수관련 내용은 아래의 링크를 확인하자. 사실 그런말이 있다. DFS는 스택(stack)를 이용하고 BFS는 큐(Queue)를 이용한다. 그리고 DFS에서 스택을 쓸 수 있다고 할 수 있지만, 이는 원론적인 개념에 대한 이야기이고, 코딩테스트에서는 보통 재귀를 쓴다. 우선 비선형 구조에 대해 간단히 알아보고 DFS를 마스터 해보자. https://han-py.tistory.com/224 [python] 재귀함수(re..

아래의 내용은 파이썬 알고리즘 인터뷰 책을 참고하여 작성하였다. 이전 내용은 아래의 링크를 참고하자 문자열 유형 기초 정리_1 유형 4. 특정 단어 추출 > 이 유형은 NLP에서도 자주 사용되는 스킬이다. paragraph = "Bob hit a ball, the hit BALL flew far after it was hit" 위의 예제에서 "hit"을 제외한 단어 중 가장 많이 등장하는 단어를 뽑는 코드를 작성하자. 대소문자는 구분하지 않고 구두점은 무시한다. 1단계 정규식을 사용해서 불필요한 구두점을 지우자 import re re.sub('[^\w]', ' ', paragraph) [^\w] 은 모든 문자와 숫자를 제외하고는 공백으로 바꾼다. 2단계 정규식에 추가적으로 처리를 해보자. banned =..

python의 꽃. DFS의 필수 개념인 재귀 함수에 대해 알아보자. 왜 재귀 함수를 알아야 할까? 미로 찾기 문제를 생각해보자. 미로를 찾기 하기 위해서는 매 순간 갈림길에서 선택을 해야 하는 순간이 생긴다. 갈림길에서 한 선택의 결과가 막힌 길이라면, 그 즉시 갈림길이 있었던 위치로 순간 이동하는 것을 가능하게 해주는 것이 재귀 함수다. 0. 기본 모양 재귀 함수란 호출한 함수 안에서 그 함수를 다시 호출(recursive call)함으로 반복하는 것을 의미한다. 쉽게 말하면 def를 통해 함수를 만든다. 그리고 만든 함수 안에서 다시 그 함수를 호출하는 것을 의미한다. 아래의 예를 참고하자. def recursive_call(x): print(x) recursive_call(x+1) recursiv..

아래의 내용은 파이썬 알고리즘 인터뷰 책을 참고하여 작성하였다. 코딩 테스트에서 점수를 받으려면, 주어진 문제를 에러 없이 주어진 시간 안에 정해진 정답을 출력해야 한다. 따라서 우리가 집중을 해야 할 부분은 첫째, 정답을 도출해 낼 수 있는 알고리즘을 짜야한다. 둘째, 주어진 시간 안에 코딩 정답을 도출해야 한다. 이러한 2가지 포인트에 집중하여, 아래의 글을 읽어주기 바란다. 문자열 유형 코딩 테스트에서 주로 1번 문제로 등장하는 문자열에 대해 정리해보고자 한다. 아래의 유형이 나오면 5분 안에 풀고 넘어가면 된다. 물론 아래의 유형으로 문자열을 요구사항에 맞게 정렬 후 다른 유형과 결합되어 나오기도 한다. 유형 1. 회문(Palindrome) 회문, 즉 팰린드롬이란 앞뒤가 똑같은 단어나 문장을 의미..

코딩테스트에 딕셔너리(해시)를 사용할 때 필요한 사용법과 꿀팁에 관해 정리해 보고자 한다. 자주 사용되는 방법에 대해 우선 정리하고 유형을 알아보자. 파이썬의 딕셔너리를 해시라고도 부르니 참고하도록 하자. 딕셔너리 생성 a = dict() b = {} print(type(a), type(b)) ```결과값 ``` 딕셔너리 추가 a = dict() a['aa'] = 'abc' a[2] = [1, 2, 3] a['test'] = {'b': 'bbb'} print(a) ```결과값 {'aa': 'abc', 2: [1, 2, 3], 'test': {'b': 'bbb'}} ``` 딕셔너리 수정 a = {'aa': 'abc', 2: [1, 2, 3], 'test': {'b': 'bbb'}} a['aa'] = 'ne..

문제의 저작권은 SW Expert Academy에 있습니다. swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWIeRZV6kBUDFAVH&categoryId=AWIeRZV6kBUDFAVH&categoryType=CODE SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 선표는 게임을 통해 사칙 연산을 공부하고 있다. N개의 숫자가 적혀 있는 게임 판이 있고, +, -, x, / 의 연산자 카드를 숫자 사이에 끼워 넣어 다양한 결과 값을 구해보기로 했다. 수식을 계산할 때 연산자의 우선 순위는 고려하지 않고 왼쪽에서 오른쪽으로 차례대로 계..

0. 들어가면면서 메모이제이션을 찾는다는 것은 기본적인 재귀가 익숙하다는 전제로 설명하겠다. 1. Memoization 메모이제이션(memoization)은 컴퓨터 프로그램을 실행할 때 이전에 계산한 값을 메모리에 저장해서 매번 다시 계산하지 않도록 하여 전체적인 실행속도를 빠르게 하는 기술이다. 동적 계획법(DP)의 핵심이 되는 기술이라 할 수 있다. 메모이제이션의 장점인 실행속도를 높이기 위한 설명으로 우선은 재귀로 피보나치수열을 구하는 코드를 확인해 보자. def fibo(n): if n > 3: # 이 부분이 있어야 무한정으로 n값이 낮아지지 않는다. return 1 else: return fibo(n-1) + fibo(n-2) 여기서의 가장 큰 문제는 호출을 계속하면 같은 수에 대해 엄청난 호출..

0. 들어가면서 일단, 개념위주가 아니라 실전 문제 푸는 스킬위주로 적을예정이다. 그리고 백트래킹에 대해 가능한 모든 내용을 담을 예정이다. 즉, 계속 업데이트가 될 것이며, 쭉 이해만 하면 관련문제는 풀 수 있을 것이다. 따라서 python 을 활용한 코드뿐만아니라 알고리즘과 관련된 모든 유형의 문제에 관련된 풀이들도 추가할 예정이다. 일단, 기본적으로 재귀를 쓰기 때문에 DFS와 BFS를 구현하지 못한다면 이부분이 어려울 수 있다. 시작해보도록 하자. 1. 백트래킹 백트래킹 기법은 해를 찾는 도중에 '막히면' 되돌아가서 다시 해를 찾아 가는 기법이다. 일명 가지치기라고도 한다. => 재귀를 이용한 완전 검색을 하고 가지치기를 추가하는 기법 백트래킹으로 최적화문제(optimization)와 결정문제(d..