뭥미
합병 정렬(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. 프림 알..
STL (Standard Template Library)
- 표준 C++ 라이브러리 - 프로그램에 필요한 자료구조와 알고리즘을 템플릿으로 제공하는 라이브러리 - 자료구조와 알고리즘은 서로 반복자라는 구성 요소를 통해 연결 구성 : 컨테이너, 반복자, 알고리즘, 함수 객체, 어댑터, 할당기 --> 다 구체적으로 설명하지 않을 것 1. 컨테이너(Container) - 데이터를 저장하는 객체 - 연속 컨테이너, 연관 컨테이너 2. 반복자(Iterator) - 컨테이너의 원소를 가리키고, 가리키는 원소에 접근하여 다음 원소를 가리키게 하는 기능 3. 알고리즘(Algorithm) - 정렬, 삭제, 검색, 연산 등을 해결하는 일반화된 방법을 제공하는 함수 템플릿 4. 함수 객체(Function Object) - 함수처럼 동작하는 객체로 operator() 연산자를 오버로..
Procedure, Function
프로시저와 함수의 정의와 차이를 해보려한다. 정의 : 일련의 쿼리를 마치 하나의 함수처럼 사용하기 위한 쿼리의 집합 - 특정 작업을 수행하는, 이름이 있는 PL/SQL BLOCK 차이점 : Procedure (프로시져) - 서버 측에서 실행된다. Function (함수) - 클라이언트 측에서 실행된다. DB 상에서 쓰이는 용어로서, 다른 게시글 찾아보면 뭐 IN OUT 있다고 하는데 정작 팩트를 가려낼 수 없어 적지 않았다.
Call by Value, Call by Reference
콜 바이 밸류, 콜 바이 레퍼런스 많이 들어 봤다. 이 글을 쓰기 위해 공부를 하면서 Call by Address, Call by Assignment 등을 들어봤다. 그러나 언어에 따른 차이점인 것 같아 크게 들어본 Value, Reference에 대해서만 언급하기로 한다. --> 추후, 프로그래밍 언어 공부에 따라 다른 부분도 필요하면 업로드할 예정. 항상 말하지만, 정확한 정의, 해석 전달을 해주고 싶다. 그러나 능력이 부족해 올바르게 전달하지 못할 수 있다. 그래서 댓글이나 연락을 준다면 꼭 수렴해 변경하고 싶다. 먼저, 각 정의부터 정리하고, 차이점을 짚어주겠다. 함수 호출방식에 따른 단어. 1. Call by value ( 값에 의한 호출 ) - C++ 경우, 함수가 호출될 때, 메모리 공간 안..
백준 10451번: 순열 사이클
문제링크: https://www.acmicpc.net/problem/10451 10451번: 순열 사이클 문제 1부터 N까지 정수 N개로 이루어진 순열을 나타내는 방법은 여러 가지가 있다. 예를 들어, 8개의 수로 이루어진 순열 (3, 2, 7, 8, 1, 4, 5, 6)을 배열을 이용해 표현하면 \(\begin{pmatrix} 1 & 2 &3&4&5&6&7&8 \\ 3& 2&7&8&1&4&5&6 \end{pmatrix}\) 와 같다. 또는, Figure 1과 같이 방향 그래프로 나타낼 수도 있다. 순열을 배열을 이용해 \(\begin{pmatrix} 1 www.acmicpc.net 문제 해결 방법은, 기본 DFS 방문 표시를 하면서 깊이 탐색하다보니, Main 문에서 실행되는 DFS 함수의 횟수는 순열..
백준 9466번: 텀 프로젝트
문제링크: https://www.acmicpc.net/problem/9466 9466번: 텀 프로젝트 문제 이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 있을 수도 있다. 프로젝트 팀을 구성하기 위해, 모든 학생들은 프로젝트를 함께하고 싶은 학생을 선택해야 한다. (단, 단 한 명만 선택할 수 있다.) 혼자 하고 싶어하는 학생은 자기 자신을 선택하는 것도 가능하다. 학생들이(s1, s2, ..., sr)이라 할 때, r= www.acmicpc.net 처음에는 그냥 단순 DFS인줄 알았다. 순환인 그래프를 찾는 DFS였다. BOOL 배열 변수 하나 선언해서 진행했다. (사..