토투바기

DFS/BFS DFS/BFS가 첫 번째 고비라고 들었던 것 같은데, 공부해보니 시간이 정말 정말 많이 들어서 이렇게 오래 걸려도 되나 싶은 개념이었다. 물론 많은 문제를 접하고, 이에 익숙해지면 어려움 없이 풀어갈 수 있을 것 이기에, 큰 두려움은 가지지 않았다. 먼저 DFS(Depth First Search)란 다차원 배열 혹은 그래프에서 각 칸을 방문할때 깊이를 우선으로 탐색하는 알고리즘이다. 위의 gif에서도 알 수 있듯이, 각 top node에서부터 하나의 branch의 최하단까지 탐색하고 끝에 도달하면 다른 branch를 탐색한다. 다음으로, BFS(Breadth First Search)란 BFS와 매우 유사한데, 다만, 각 칸을 방문할때, 하나의 branch에 끝에 도달하고 다른 branch를..

수식의 괄호 쌍 괄호가 쓰인 단순 수식을 풀 때나, 코딩에서 괄호로 조건문이나 반복문을 구분 지을 때, 우리는 항상 괄호의 짝을 찾게 된다. 예를 들어, 위의 사진의 맨 위의 경우는 모든 괄호가 짝이 맞기 때문에 올바른 괄호 식이 될 것이고, 밑의 두 경우는 모든 괄호가 짝을 이루지 않기 때문에 올바르지 않은 괄호 식이 될 것이다. 만약에, 엄청난 길이의 괄호가 줄지어져 있는데, 이 괄호식이 올바르게 짝이 지어져 있는지, 그렇지 않은지를 판별해야 한다면 어떻게 코드로 풀이할 수 있을까? 이러한 문제를 다루는것이 바로 수식의 괄호 쌍 문제이고, 이를 해결하기 위해서는 스택 자료구조를 이용하는 것이 가장 편리하다. 그 이유는 바로, 괄호가 짝이 맞는지 눈으로 검사를 할 때, 우리는 가장 안쪽에서부터 짝이 맞..

덱 (Deque) 덱은 Deque(Double Ended Queue)로 근본적으로는 queue와 그 구조를 상당수 공유하지만, 단 한 가지가 다르다면, 이름에서도 알 수 있듯이, queue의 양쪽에서 접근이 가능하다. 기존 queue는 FIFO(First In First Out)의 속성을 가졌다면, deque는 그러한 규칙 없이 양쪽에서 pop, push가 매우 자유롭기 때문에 아주 편리하다. 구현이 복잡하다고 하는데 파이썬에서는 다 구현을 해주니까, 안 쓸 이유가 전혀 없고, pop, push의 시간 복잡도도 O(1)로써 빠르니까 아주 편리한 자료구조라고 생각이 든다. 리스트의 랜덤 요소에 접근 (양 끝이 아닌 아무 값) 해야 할 때 말고는 자료구조 후보군에 항상 있을 것 같으며, 앞 뒤에서 삽입, 삭..

큐와 스택은 서로 비슷한점이 많아서 개념적으로 낯설지도 않고, 자료구조 시간에 배운적이 있어서 개념을 습득하는데는 크게 어렵지는 않았다. 그러나, 모든 기억이 그렇듯 자주 되새기지 않으면 까먹게 되므로 개념을 간략하게 기록하고, 위의 3개의 문제중 하나를 골라 후기를 남겨보려고 한다. 큐 (Queue) 아주 간단하다, 스택이 FILO(First In Last Out)이라는 것을 이해했다면, 큐를 이해하는것도 어렵지 않을것이다. 큐는 FIFO(First In First Out)로 먼저 들어온 원소가 먼저 나가는 것이다. 대학에서 자료구조를 배울때 교수님께서 은행에 가서 서는 줄과 비슷하다고 하신것이 기억에 남는다. 아직 기억이 나는걸 보면 꽤나 머리에 쏙 박힌 비유였던것 같다. 파이썬의 list와 연관지으..

개요 회사에서 주어진 일이 조금 생겨서 문제풀이와 포스팅에 신경을 쓰지 못했다. 그리고 드디어 문제들이 조금씩 버거워지기 시작했다. 스택이 뭐 FILO(First In Last Out), POP, APPEND 이 정도만 알면 스택을 안다고 생각했는데, 이를 단순히 메서드를 사용하는 문제가 아닌, 스택 개념을 응용한 골드 티어 문제 같은 경우에는 도저히 안 되겠어서 구글링을 하여 답지를 봐도 한동안 이해하는데 시간이 걸릴 정도였다. 무튼 본론으로 돌아가면, 약간 특이했던것이, 연결 리스트 관련 문제들 전부가 스택으로 구현하면 훨씬 더 효율적으로 코드를 짤 수 있었기 때문에, 연결 리스트 관련 문제였던 에디터, 키로거, 요세푸스 전부 스택을 사용하여 풀었다. 그중 가장 까다로웠던 두 문제, 요세푸스(BOJ ..

문제집 이름이 배열인 만큼 아직 특별한 알고리즘 기법이 나오지 않기 때문에, 거의 모든 문제가 그냥 수수께끼, 수학, 구현력과 관련된 문제였다. 그러나 하나 기억하면 좋을것 같은 문제가 하나 있었다. 이는 [BOJ 3273: 두 수의 합] 문제였다. 3273번: 두 수의 합 n개의 서로 다른 양의 정수 a1, a2, ..., an으로 이루어진 수열이 있다. ai의 값은 1보다 크거나 같고, 1000000보다 작거나 같은 자연수이다. 자연수 x가 주어졌을 때, ai + aj = x (1 ≤ i < j ≤ n)을 만족하는 www.acmicpc.net 처음에 이 문제가 왜 실버4의 문제 티어를 가지고 있는지 몰랐었다. 왜냐하면 이 문제는 그저 배열안에 저장되어 있는 수열중의 원소 두개를 합했을때 특정 N의 값..

이번 문제집은 알고리즘 기법을 응용한 문제가 아니고 단순 수학, 조건, 반복에 대한 문제이기 때문에, 코드 풀이에 대한 기록은 하지 않을 예정이다. 단, 파이썬을 사용 안 한 지가 1~2년 정도 돼가기 때문에, 파이썬의 문법에 대한 감도 익히고, 파이썬을 이용하여 알고리즘 문제를 풀 때 어떻게 접근해야 하는지를 익히는 시간을 가지도록 하였다. 내가 문제들을 풀면서 기억해놓으면 좋겠다 라고 생각이 든것들은 아래와 같다 sys.stdin.readline()의 응용 list 메서드 전체 (append,reverse...) from itertools import combination (조합 계산) max(), sum(), min() sys.stdin.readline()의 응용 파이썬은 주로 input()으로 사..

개발 언어나 환경에 익숙해지는것, 사실 실력의 문제가 아니라 시간이 해결해주는 문제라고 생각한다. 그러나, 항상 단순한 이중포문이나 길게 늘어진 조건문으로 코드를 쓰는것은 공부하지 않으면 절대 나아지지 않는것이다. 그냥 어렵게 만들어놓은 코드라고 생각했던 자료구조, 복붙하여 사용하는대만 급급했던 알고리즘의 필요성을 강력히 느끼며 알고리즘을 공부하려 한다. 또한, 바킹독님이 잘 정리해주신 알고리즘 자료를 사용할 예정이다. 참고로 알고리즘 구현은 Python을 사용할 계획이다. 알고리즘 기법을 공부하기 전에 프로그래밍의 기초가 되는 개념들을 몇개 집고 넘어가야 한다. 이는 아래와 같다. 시간, 공간복잡도 정수 자료형 실수 자료형 시간, 공간복잡도 (Time & Space Complexity) 시간과 컴퓨터 ..