자료구조

[알고리즘] 백트래킹(Backtracking)을 알아보자

요즘 백준 문제집을 풀고있는데, 백트래킹 개념의 문제가 나와서 한번 개념을 블로그에 정리해보려고 한다. # 등장 배경 이 글을 읽고있는 분들이라면 DFS(깊이 우선 탐색), BFS(너비 우선 탐색) 등의 유명한 완전탐색 알고리즘은 한번쯤 들어본 적이 있을 것이다. 이러한 알고리즘은 모든 가능한 경우의 수를 탐색하는 특징이 있는데, 백트래킹도 이와 비슷한 motivation을 공유한다. 즉, '가능한 모든 방법'을 탐색하는 데에 관심사가 있는 것 ! 하지만 DFS와 BFS는 정말 모든 노드를 탐색한다. 그러다보면 해답이 될 가능성이 없는 그래프의 노드까지 "모두" 탐색하게 되는 것이다. 우리는 알고리즘 문제를 풀고있으므로, 전혀 가능성이 없는 노드는 관심이 없을 것이다. 따라서 백트래킹(Backtracki..

[백준] 에디터(Python) - Stack

# 문제 # 입출력 # Idea 스택을 이용한 문제다. 이 문제의 특징은 주어진 시간제한이 매우 짧기 때문에, insert와 pop(i) 등을 사용해서는 시간복잡도가 커지기 때문에 사용할 수 없다. (시간초과가 뜬다) 그래서 pop()와 append()만을 이용해 스택으로 구현해야한다. 그렇다면 이 문제를 어떻게 스택으로 구현하느냐? 필자는 처음에 각각의 L, D, B, P 경우를 하나하나 스택으로 구현할 수 있도록 경우를 생각했는데, 이럴 경우에 예외처리가 너무 복잡하고 까다로워져서 난항을 겪었다. 따라서 이 문제의 핵심 아이디어는 커서의 위치를 기준으로 데이터를 두개의 스택으로 나누는 것이다! 처음에는 하나의 스택에 데이터를 모두 몰아넣는다. 그리고 앞서 언급한 pop과 append의 스택 연산을 이..

[자료구조] - (2) 스택(Stacks) with Python

스택(Stacks) 역시 추상적 선형 자료 구조 중 하나이다. 본 게시글은 Python 코드로 작성되었습니다. 1. 스택의 구조 기본적으로 스택은 넣을 때는 한쪽 끝에서 밀어넣어야 하고(push), 꺼낼 때에는 같은 쪽에서 뽑아 꺼내야한다.(pop) 간단히 그림으로 나타내면 다음과 같다. 이와 비슷한 선형 자료구조 큐(Queue)는 좀 다르다. 큐는 '선입선출'의 구조로서, 먼저 들어간 요소가 가장 먼저 나오는 구조이다. 기본적으로 스택은 한쪽에서 꺼내고 빼고를 하는 반면, 큐는 한쪽에서 들어가면 다른쪽에서 나온다! 그리고 스택은 가장 마지막에 들어간 요소가 가장 먼저 나온다 (후입선출) 스택에는 정해진 저장 공간이 있다. 따라서 비어있는 스택에서 원소를 꺼내려 하거나, 꽉찬 스택에 데이터 원소를 넣으려..

[자료구조] (1) - 연결리스트(Linked List) with Python

연결리스트는 대표적인 추상적 자료구조(Abstract Data Structures) 중 하나이다. 본 게시글은 Python 코드로 작성되었습니다. 1. 단순 연결리스트의 기본 구조 각 연결리스트는 Node로 구성되어있고, Node안에는 data와 link로 구성되어있다. 안에 들어있는 data는 그림에 나와있는 정수형 말고도 문자, 레코드 등 여러 구조가 가능하다. Node를 코드로 구성해보면 다음과 같다! class Node: def __init__(self, item): self.data = item # data self.next = None # next link (다음 인자를 가리킴) 여기서 next는 다음 노드에 접근하는 방법이다. 예시 ) L.head == a a.next == b b.next ..

[알고리즘] - 선형배열(리스트 내 해당 원소의 인덱스 반환)

✔ 주안점 index의 중복처리 반환(존재하는 모든 원소의 인덱스를 반환해야 했던 것) 💻 부끄러운 나의 코드 def solution(L, x): answer = [] if x in L: for i in range(len(L)): a = L[i] if x == a: if i< len(L): answer.append(L.index(a, i)) else: answer.append(L.index(a, i-1)) # 인덱스에 집착하다보니 index method를 이용할 수밖에 없었음. ... # 그 결과.. 비효율적인 코드 완성됨.. else: pass else: answer.append(-1) return answer ✔ 문제점 - 또 비슷하게 if/else 식의 코드 진행.... 으... 극혐.... - i..

[알고리즘] - 선형배열 (정렬된 리스트에 원소 삽입하기)

✔ 주안점 - 원소가 기존 리스트의 원소보다 가장 크거나 가장 작은경우를 예외로 처리해야 했던 것 💻 부끄러운 내 코드 def solution(L, x): last = int(len(L)-1) for i in range(last): if int(L[i]) int(max(L)) : L.insert(int(len(L)), x) break elif x < int(min(L)): L.insert(0, x) break else: pass return L ✔ 문제점 - 단순 if와 else를 반복한 코드임. 너무 길고 불필요함...