1. BFS와 DFS의 개념 1) BFS먼저 BFS는 영어로 풀어쓰면 Breath-First-Search로 너비 우선 탐색을 의미한다. 다음과 같은 그래프가 주어졌을 때 BFS의 방식으로 그래프 탐색을 어떻게 하는지 알아보자. 먼저 기준 노드를 잡아야한다. 기준 노드는 쉽게 말하면 탐색을 시작하는 노드을 의미한다. 편의상 1번 노드를 기준으로 탐색을 시작하자. BFS 로 탐색하면 아래와 같은 결과가 나온다.1 - 2 - 4 - 5 - 3 - 6 - 7 BFS는 기준노드와 거리가 가까운 노드들부터 탐색을 한다고 봐도 무방하다. 2) DFS다음으로 DFS는 Depth-First-Search로 깊이 우선 탐색을 의미한다.아까와 같은 그래프가 주어져있고 1번 정점부터 탐색을 시작한다고 할 때 탐색 결과는 ..
문제 링크 문제 풀이 이 문제는 $N\times M$ 칸에 숫자들이 적혀 있을 때, 테트로미노 타일을 이용해 타일이 포함하는 수들의 합의 최댓값을 구하는 문제이다. 여기서 테트로미노는 폴리노미노의 한 종류로 네 개의 정사각형이 변끼리 인접하여 만들어지는 도형을 의미한다. $N,M ≤ 500$ 이라서 그냥 브루트포스로 모든 점들에 대해서 백트랙킹으로 탐색해줘도 충분하다. 이때 시간복잡도는 $O(MN)$인데, 정확히는 백트랙킹 할 때 최대 $4^4$ 개의 가짓수가 있어서 $256MN$만큼의 연산이 필요하다. 먼저 Back Tracking 함수를 먼저 구현해보자. 초기 좌표와 깊이, 그리고 현재까지 숫자의 합을 매개변수로 하였다.void BT(int x, int y, int depth, int k){..
파이썬에서 tkinter 모듈을 이용해서 암호화 복호화 프로그램을 만들어보았다. 그러려면 tkinter 창의 간단한 디자인과 암호화 복호화 방법을 정해야한다.디자인 먼저 디자인은 크게 중요하지 않으므로 간단하게 하였다. 암호화 시킬 텍스트를 집어넣는 엔트리와 암호화된 결과를 보여줄 엔트리, 또 암호화 시킬 버튼이 필요하고, 복호화도 마찬가지로 복호화 시킬 암호를 넣는 엔트리와 복호화된 결과를 보여주는 엔트리, 또 복호화 버튼이 필요하다. 추가적으로 무슨 엔트리인지를 보여주는 텍스트와 모든 내용을 지우는 지우기 버튼도 추가하였다.코드from tkinter import *win = Tk()win.title('Encryption & Decryption')win.geometry('400x400')entry1 =..
예전에 LIS알고리즘을 DP로 $O(N^2)$만에 구현하는 포스팅을 올린 적이 있다. 하지만 이 알고리즘을 쓰기엔 시간복잡도가 크다보니 시간초과가 나는 문제가 많다.LIS $O(N^2)$ 이번 포스팅에서는 이분탐색을 활용한 $O(NlogN)$ LIS 알고리즘을 올려보려고 한다. 이분탐색을 써서 푸는 백준 문제는 아래 세 개가 있다.가장 긴 증가하는 부분 수열 2가장 긴 증가하는 부분 수열 3 가장 긴 증가하는 부분 수열 5 LIS 길이 구현 방법 외부 배열이나 벡터에서 각각의 숫자들의 lower bound를 구해 그 인덱스로 넣어주는 방식이다. 아래 그림은 LIS 이분탐색 과정이다. 이렇게 이분탐색으로 배열을 만들고 나면 크기 순서대로 숫자들이 정렬이 되어있다. 여기서 이 배열의 길이는 LIS의 길이..
BOJ 16891. 탄성충돌
문제 링크 "물리학" 카테고리에 있는 문제들을 풀어보다가 이 문제가 재미있게 생겨서 풀어보았다. 예전에 이런 충돌수에 관련된 문제를 3Blue1Brown 이라는 굉장히 좋은(?) 채널에서 본 적이 있다.유튜브 영상 이 영상에서는 두번째 물체의 질량이 100의 거듭제곱 꼴일 때 충돌횟수가 π의 앞의 자리수가 되는 이유를 설명해주고 있는데 예전에 흥미롭게 봤던 경험이 있어서 생각이 났다. 1. 문제 풀이 먼저 알아야할 것은 두 번째 물체의 초기속력이 0만 아니라면 충돌수에 영향을 주지 않는다는 것이다. 만약 첫 번째 물체의 초기속력이 있었다면 상관이 있겠지만 첫 번째 물체의 초기속력이 0이므로 두 번째 물체가 어떤 속력을 가지든 속력비율은 항상 일정하기 때문이다. 근데 소수점계산에서 오류가 발생할 수도..