Kim-Baek 개발자 이야기

알고리즘 문제에서 정렬(Sort)는 중요한 기술이다. 여러가지 정렬 알고리즘이 있지만 기본적인 것 부터 하나하나 알아보자. 선택 정렬 (Selection Sort) 단순한 정렬 알고리즘 중 하나이다. 배열의 첫 번째 원소에서 시작하여 배열 전체를 훓으면서 작은(큰) 값을 찾아 첫 번째 원소와 바꿔준다. 이 작업을 (배열의 길이 - 1 ) 만큼 진행한다. 선택 정렬은 Best, Average, Worst Case 모두 O(N^2) 의 효율이다 - 원소를 바꾸는 횟수가 최대 n -1 이다. 즉 원소를 바꾸는 과정에서 많은 비용이 드는 경우에 효율적일 수 있다. - 선택 정렬은 다른 알고리즘에 비해 효율(performance) 가 좋지 않다. - stable을 만족하지 않는다. #include using na..

BFS는 너비우선탐색 이라고 블리는 Graph 알고리즘 중 하나이다. - BFS 는 일반적으로 Queue를 이용해 구현 - 시작 정점과 인접한 모든 정점을 방문하는 방법 - 얻어진 해가 최단 경로가 된다는 것을 보장 - 경로가 매우 길 경우에는 많은 저장 Memory 가 필요 C++를 이용해 BFS를 구현 #include #include #include using namespace std; vector* vertex; bool* checked; void bfs(int st); int main() { int n, m, s; int from, to; cin >> n >> m >> s; vertex = new vector[n + 1]; checked = new bool[n + 1]; for (int i = 0..

사용자가 현재 a.com 이라는 사이트에 접속해서 인터넷을 하고 있다. 그런데 사용자의 PC가 해킹되어 사용자가 모르는 hacking.js 라는 프로그램이 내부적으로 동작하고 이 hacking.js 는 사용자가 a.com 사이트에 접속하면 사용자 PC의 개인정보가 담겨있는 쿠키파일을 hacking.com 으로 전송한다고 하자. (이를 크로스 사이트 스크립팅(XSS) 해킹기법이라고 한다.) 웹 브라우저는 이처럼 사용자가 특정사이트에 접속중인 상태에서 동시에 다른 사이트를 접근하는 경우 보안상 문제가 발생했다고 인식하여 이와 같은 행위를 기본적으로 불허한다. 이를 동일출처정책(Same Origin Policy) 이라고 한다. 그런데 이러한 해킹말고 실제로 기능구현 할 때 다른 사이트를 동시에 접속해야 될 필..

Tree Traversal Tree Traversal 은 트리 순회이다. Tree 자료구조에서 각각의 노드를 정화히 한 번만, 체계적으로 방문하는 과정이다. 전위 순회(PreOrder Traversl) Root 노드부터 탐색하기 시작한다. root => sub left => sub right PreOrder Traversal은 가장 깊은 왼쪽 노드부터 탐색하기 때문에, 우리가 잘 알고 있는 DFS 라고 생각하면 된다. def preOrder(node): print(node, end = ' ') if node.left != null: preOrder(node.left) if node.right != null: preOrder(node.right) 중위 순회(InOrder Traversal) 왼쪽 서브 트리..