본문 바로가기

알고리즘

 (7)
[Python] 딕셔너리의 기능들 두 리스트를 합치고 싶을때는 그냥 '+' 연산자를 활용하면 된다. a=[1,1,2,3,3] b=[3,4,5] print(a+b) #[1,1,2,3,3,3,4,5] 하지만 두 리스트에서 공통된 부분을 삭제해야 할 경우에는 어떻게 해야할까? 그냥 '-' 연산자를 쓰면 될까? a=[1,1,2,3,3] b=[3,4,5] print(a-b) #TypeError: unsupported operand type(s) for -: 'list' and 'list' 위 처럼 오류가 뜬다. list끼리는 '-' 연산자를 지원하지 않는다. 그렇다면 어떻게 하면될까? 여기서 집합 자료형을 사용할 수 있다. a=[1,1,2,3,3] b=[3,4,5] print(set(a)-set(b)) #{1,2} print(list(set(a)..
[알고리즘/Python] 투 포인터 알고리즘 (Two Pointers Algorithm) 크기가 N인 리스트가 있을때 그 리스트를 완전 탐색으로 해결해버리면 O(N^2)의 시간이 소요된다. 아래에서 소개하는 알고리즘을 활용하면 선형시간으로 문제를 해결할 수 있다. 투포인터 알고리즘 리스트에 순차적으로 접근해야 할 때 2개의 점(start, end)의 위치를 기록하면서 처리하는 알고리즘이다. 리스트의 특정 연속된 구간을 처리하는 경우에 매우 유용하다. ex) 특정합을 가지는 부분 연속 수열, 팰린드롬 등의 문제에 활용 가능하다. 예제문제를 풀어보자. https://www.acmicpc.net/problem/2003 2003번: 수들의 합 2 첫째 줄에 N(1 ≤ N ≤ 10,000), M(1 ≤ M ≤ 300,000,000)이 주어진다. 다음 줄에는 A[1], A[2], …, A[N]이 공백으..
[Python] 딕셔너리의 기본값 처리 (defaultdict) 일반적으로 파이썬의 딕셔너리에서 미리 삽입하지 않은 키를 호출할 경우에는 오류가 발생한다. dic=dict() print(dic['A']) >>>KeyError: 'A' 오류 발생! 딕셔너리에 'A'라는 키의 값을 삽입하지 않았으므로 오류가 발생하는건 당연하다. 이를 해결하기위해 아래처럼 setdefault라는 함수를 사용할 수 있다. dic=dict() dic.setdefault("A",1) setdefault를 이용하면 key값을 삽입할때마다 매번 함수를 호출해야하는 번거로움이 있다. 딕셔너리를 선언함과 동시에 미리 지정한 값이 설정되도록 할 수는 없을까? 이때 collections 모듈에 있는 defaultdict 라는 함수가 등장한다. from collections import defaultdic..
[알고리즘/Python] 퀵 정렬(Quick Sort) 퀵 정렬(Quick Sort) 이란?? 병합 정렬(Merge Sort)와 더불어 대표적인 분할 정복 알고리즘 중 하나이다. 리스트 값중 랜덤한 값을 pivot으로 설정한 뒤 pivot보다 작으면 왼쪽에, pivot보다 크면 오른쪽에 위치시킨다. pivot을 기준으로 나눠진 왼쪽과 오른쪽 리스트에 대해 또 다시 위의 과정을 재귀적으로 시행한다. 평균 시간복잡도는 O(n*log n), 최악의 시간복잡도는 O(n^2)이다. def quick_sort(arr): #리스트가 하나 이하의 원소를 가지고 있다면 종료 if len(arr)
[알고리즘/Python] DFS(깊이 우선 탐색)과 BFS(너비 우선 탐색) 구현 DFS (Depth-First-Search) 그래프에서 가장 깊은 부분을 우선으로 탐색하는 알고리즘이다. 진행 가능한 노드가 없을 때까지 깊게 파고드는 방식이며, 더이상 방문 가능한 노드가 없다면 이전의 위치로 돌아와 다른 방향으로 깊게 파고든다. 주로 모든 노드를 방문하고자 하거나, 이동할때 마다 가중치가 붙어서 이동하는 경우, 그리고 이동 과정에서 여러 제약이 있는 경우에 이 방식을 사용한다. 또한 검색 대상 그래프가 정말 크다면 DFS를 사용한다. DFS 알고리즘을 구현할때는 재귀로 구현할 수도 있고, 스택을 이용해서 구현할 수도 있다. 코딩테스트에서 구현할때는 재귀로 구현하는것이 더 선호되는 편이다. 장점 BFS에 비해 저장공간의 필요성이 적다(적은 메모리 사용). 백트랙킹을 해야하는 노드들만 저..
[알고리즘/Python] 그래프 구현 - 인접 행렬과 인접 리스트 알고리즘 문제를 보다가 보면 Graph와 관련된 문제들을 매우 많이 접할 수 있다. 보통 이런 그래프와 관련된 문제를 풀때는 현재 그래프의 모습을 모델링하고 난 뒤에 문제를 푼다. 이때, 모델링한 그래프의 연결관계를 나타내는 방법에는 크게 두가지가 있다. 1. 인접 행렬 2. 인접 리스트 1. 인접 행렬 그래프에서 두 노드(vertex) 사이의 연결 관계를 이차원 배열로 나타내는 방식이다. 보통 adj[][]형태로 많이 사용한다. adj[i][j] : 노드 i에서 j로 가는 edge가 존재할 경우 1, 아니면 0 만약 구현하고자 하는 그래프가 Undirected Graph 일때는 adj[i][j] == adj[j][i] 일것이다. 이 경우에서 인접 행렬을 구현하면 대각선을 기준으로 대칭인 성질을 가질 것..
[알고리즘/Python] 알고리즘 설계 Tip!! 코딩 테스트 문제에서 시간제한은 보통 1~5초가량이라고 생각해야함. Python의 경우 연산 횟수가 5억을 넘어간다면 통상 5~15초 가량의 시간이 소요된다. 문제에서 가장 먼저 확인해야 하는 내용은 시간제한(수행시간 요구사항)이다. 만약 시간제한이 1초인 문제를 만났다면, 일반적인 기준은 다음과 같다. N의 범위가 500인 경우 : 시간 복잡도가 O(N^3)인 알고리즘을 설계하기 N의 범위가 2,000인 경우 : 시간 복잡도가 O(N^2)인 알고리즘을 설계하기 N의 범위가 100,000인 경우 : 시간 복잡도가 O(N*logN)인 알고리즘을 설계하기 N의 범위가 10,000,000인 경우 : 시간 복잡도가 O(N)인 알고리즘을 설계하기 일반적으로 알고리즘 문제를 만났을때의 사고과정!! 지문 읽기 및 컴..

티스토리툴바