전체 글
합병 정렬(Merge sort)
머지 소트, 합병 정렬 여러가지 이름으로 존재한다. 이해하면서 분할합병 정렬? 이라고 하는게 옳지 않나 싶다. 제일 먼저 합병 정렬에 큰 도움을 받은 블로그의 링크를 올려 놓는다. 링크 : https://gmlwjd9405.github.io/2018/05/08/algorithm-merge-sort.html [알고리즘] 합병 정렬(merge sort)이란 - Heee's Development Blog Step by step goes a long way. gmlwjd9405.github.io 합병 정렬은 '존 폰 노이만' 사람이 제안한 방법 -> 컴퓨터 구조를 배우면 먼저 볼 수 있는 사람. 합병 정렬은 분할 정복 알고리즘의 하나이다. -> 분할 정복 이란 -> 문제를 작은 2개의 문제로 분리하고 각각을 해..
백준 13460번: 구슬 탈출 2
문제 링크: https://www.acmicpc.net/problem/13460 13460번: 구슬 탈출 2 첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 '.', '#', 'O', 'R', 'B' 로 이루어져 있다. '.'은 빈 칸을 의미하고, '#'은 공이 이동할 수 없는 장애물 또는 벽을 의미하며, 'O'는 구멍의 위치를 의미한다. 'R'은 빨간 구슬의 위치, 'B'는 파란 구슬의 위치이다. 입력되는 모든 보드 www.acmicpc.net 문제 해결 방법: BFS 또는 DFS인데, 기울이기가 한 칸씩 이동개념이랑 다르다. 테스트 케이스 2번째로 한 칸씩..
x64와 x86의 차이
먼저 어느정도 아시는 분이라면, x64는 64비트 x86은 32비트를 의미하는 것을 압니다. 즉, 이번 글에서는 32비트 프로그래밍과 64비트 프로그래밍의 차이에 대해서 알아보려합니다. 1. 32비트 vs 64비트 차이는 레지스터의 처리값 CPU는 I/O버스를 통해 데이터 내,외부로 전송합니다. 그 한 번에 데이터를 전송하는 양이 32bit, 64bit 입니다. 2. 32비트 컴퓨터와 64비트 컴퓨터 차이 RAM에서 표현할 수 있는 주소값에서 보인다. 2^32 = 2^2 * 2^30 = 4 * 2^30 = 4 GB 즉, 4GB 초과한 메모리 영역에는 참조할 수 없고, 32비트 CPU에서는 4GB RAM을 인식하지 못한다. 3. 궁금증 Q. 32bit 프로그램은 64bit 운영체제에서 작동하지 않는가? A..
유니온 파인드(Union Find)
이 글은 아래에 블로그를 참고하여 작성되었습니다. https://twpower.github.io/115-union-find-disjoint-set [Algorithm] 유니온 파인드(Union Find)와 서로소 집합(Disjoint Set) Practice makes perfect! twpower.github.io https://www.crocus.co.kr/683 유니온 파인드(Union Find, Disjoint Set) 유니온 파인드(Union Find)란? 유니온 파인드(Union Find)는 Disjoint Set라고도 불리기도 하며, 이 자료구조는 일상속에서 우리가 은연중에 접하는 자료구조이다. 예를 들어보자. 우리는 학창 시절에 수학여행을.. www.crocus.co.kr Disjoint ..
최소 스패닝 트리 (Minimum Spanning Tree, MST)
참고 블로그 : https://www.crocus.co.kr/733 정의 : - 그래프에서 그래프의 모든 정점을 연결하되, 사이클이 존재하지 않도록 모든 정점을 간선으로 연결하는 것을 의미 - 최소 스패닝 트리는 무조건 하나의 그래프에서 하나만 생성된다고는 보장하지는 못한다. 최소 스패닝 트리 알고리즘 1. 크루스칼 알고리즘 - 모든 간선에 대해 가장 가중치가 작은 간선부터 연결해주면서 최소 스패닝 트리를 만들어 나가는 알고리즘을 의미 - 크루스칼 알고리즘 자체가 유니온 파인드 자료구조 기반으로 생성된다 --> 유니온 파인드 자료구조를 공부한 경험이 있으나, 위에 참고한 블로그에서는 더 쉽고, 자세히 설명되어있어 다시 게시글을 올릴예정 - 크루스칼 알고리즘의 시간 복잡도 : O(ElogE) 2. 프림 알..