그냥 개발블로그에요

알아보기 큰 문제를 직관적으로 이해할 수 있는 작은 문제로 바꾸어서 소형화시킴. 작은 문제의 답을 메모이제이션, 그렇게 점점 큰 문제로 확장시켜 나간다. 사용 예시 예를 들어 계단오르기 문제가 그렇다. 계단을 오를때 한번에 한 계단 또는 두 계단씩 올라갈 수 있을 때, 총 7 계단을 올라간다면 그 방법의 수를 구해보자. 차근차근 처음부터 알 수 있는 것부터 따져보자. 먼저 첫번째 계단을 올라가는 방법은 한가지다. 두번째 계단을 올라가는 방법은 한칸+한칸, 두칸으로 두가지다. 세번째 계단을 올라가는 방법은, 두번째 계단에서 올라갈때와 첫번째 계단에서 올라갈때 경우로 나눠진다. 첫번째 계단으로 가는 방법은 한가지였고, 두번째 계단으로 가는 방법은 두가지였으므로, 세번째 계단으로 가는 방법은 세가지이다. 그렇..

알아보기 Greedy는 탐욕스러운 이라는 뜻이다. 선택의 순간마다 당장 제일 좋아보이는 경우를 선택한다. 여러 경우 중에 하나를 선택해야할 때, 그 순간 최적이라고 생각하는 것을 선택해 나가는 방식으로 진행하여 최종적인 해답에 도달한다. 그 순간 선택한 결정은 지역적으로는 최적이지만, 전역적인(최종적인) 해답이 최적이라는 보장은 없다. 따라서 그리디 알고리즘을 적용하려면, 지역적으로 최적이면서 전역적으로 최적이어야 한다. 조건 Greedy choice property - 탐욕적 선택 속성 - 앞의 선택이 이후의 선택에 영향을 주지 않는다. optimal substructure - 최적 부분 구조 - 문제에 대한 최종 해결법은 부분 문제에 대한 최적해이다. 이러한 조건이 성립하지 않을때에도, 근사 알고리즘..

알아보기 다익스트라 알고리즘은 가중치 그래프에서 가중치의 값이 모두 양수일 때 한 노드에서 각 노드까지의 최소거리를 구할때 사용한다. 기본적으로 그리디과 다이나믹을 사용한다. 방문한 노드들을 체크하여, 체크하지 않은 노드들 중 가장 비용이 적은 노드를 선택(그리디)하고, 그 비용과 기존의 비용을 비교하여 값을 갱신(프로그래밍)하는 방식이다. 적용해보기 위의 그래프를 이용하여 1번 노드에서 각 노드까지의 최소비용 구해보도록 하자. 각 노드로 가는 최소 비용을 담는 배열 dis을 생성한다. 그 값들은 최대값으로 일단 해놓고, 1번정점을 0으로 한 뒤 시작한다. 배열 값 중 0의 값이 최소이므로 체크해 놓고, 1번노드에서 바로 갈 수 있는 노드에 대한 비용을 각 노드가 가진 현재 값과 비교하여 더 작다면 바꾼..

들어가며 코딩테스트를 잘 보기 위해서는 자료구조와 알고리즘을 공부해야한다고는 하는데 이 둘이 정확히 뭔지 둘 사이의 관계는 무엇인지 코테는 왜 이러한 지식을 요구하는지 이번에 정리하고자 한다. 둘 사이의 관계가 너무 헷갈렸다.. 자료구조 단어 그대로 자료를 담는 구조를 말한다. 그 구조는 논리적인 규칙으로 정해는 것이다. 예를 들어보자! 책장에 책을 꽂아두는 상황에서, 아무렇게나 꽂으면 원하는 책을 찾기 어렵다. 규칙1. 가나다 순으로 꽂아넣기 규칙2. 분야별로 꽂아넣기 등등 규칙을 정해서 꽂아넣으면 찾기 쉬울것이다. 하지만 여기서도 문제가 생길 수 있다. 규칙2로 정해진 책장 구조에서 분야별로 동일한 공간을 마련했지만 소설책은 거의 없어 공간이 널널하고, 만화책은 너무 많아 공간이 비좁다면, 공간을 비..

알아보기 Breadth-First Search 너비 우선 탐색이다. 임의의 노드에서 시작하여 인접한 노드를 먼저 탐색하는 방법이다. BFS 는 재귀적으로 동작하지 않는다. 위의 그림에서도 볼 수 있듯이, 같은 레벨에 있는 노드들을 방문한 뒤 다음 레벨의 노드들을 방문하는 방식이다. 노드들은 큐에 집어넣어, 레벨이 바뀌면 뺀다. 이 과정은 아래의 그림을 통해 이해해 볼 수 있다. 적용하기 미로의 최단거리, 그래프 최단거리등 최단거리를 구하고자 할 때 사용된다. 말단 노드까지의 가장 짧은 경로를 구해보자. import java.util.LinkedList; import java.util.Queue; class Node{ int data; Node2 lt, rt; public Node2(int val){ da..

알아보기 데이터 베이스는 여러 사람이 공유하여 사용할 목적으로 체계화해 통합, 관리하는 데이터의 집합이다. 아무렇게나 쌓여있는 자료들을 모아서 체계적으로 저장해둔 창고라고 말할 수 있다. 사람들은 창고에 들어가 원하는 자료를 읽거나, 쓸 수 있는 것이다. 아무나 창고에 들어가선 안되기 때문에 권한을 부여하여 접근을 제한한다.다수의 사람들이 쓰는 만큼, 자료들도 중복되거나 불일치가 일어나면 안된다. 이러한 관리를 해주는 시스템을 데이터베이스 관리 시스템이라고 한다. 데이터베이스관리 시스템이 존재하기 이전에는 File System을 이용하여 데이터를 관리하였다. 파일시스템의 단점때문에 데이터베이스가 탄생한 것이다. 특징 데이터의 독립성 물리적 독립성 : 디비 크기를 변경해도 관련된 응용 프로그램을 수정할 필..

알아보기 Depth-First Search 깊이 우선 탐색이다. 임의의 노드에서 시작하여 다음 분기로 넘어가기 전까지 해당 분기를 끝까지 탐색하는 방법이다. 미로를 탐색할 때 한 방향으로 쭉 가다가(깊이) 갈 수 없는 상황이 되면, 그 전 노드로 돌아와(**백트래킹**) 인접한 다른 노드를 탐색하고, 그 노드 아래에 있는 노드들을 쭈욱 탐색하는 경우가 dfs를 사용하는 예라고 볼 수 있다. 따라서, 어떤 노드를 방문했었는지 반드시 체크하여 검사를 해야한다. 그렇지 않으면 무한 루프에 빠질 수도 있다. 적용하기 미로 탐색뿐만아니라, 순열, 중복순열,조합,메모이제이션에서도 응용이 가능하다. 순열 예를 들어 1~N까지의 자연수 중 M개를 뽑아 일렬로 나열하는 경우의 수가 순열이다. N=3, M=2이라고 가정하..

이번에 보스 울트라 신제품이 나와서 또 다시 주목을 받고 있는데요. 저는 울트라는 없고 2년전에 산 보스 QC45 헤드셋을 리뷰하려고 합니다. 색상은 화이트, 그레이, 블랙이 있는데 저는 그레이로 골랐어요~ 구성 오른쪽 부분에 전원스위치, 블루투스, 볼륨버튼, 노이즈 캔슬링 버튼이 있습니다. 블루투스 연결 스위치를 쭈욱 밀면 전원이 켜지고, 페어링 준비가 돼요. 앱으로 들어가서 페어링 설정하면 블루투스가 연결됩니다. 최대 3개의 기기까지 연결돼서 아주 맘에 들어요 ㅎㅎㅎ 착샷

알아보기 정점(Vertex)과 간선(Edge)으로 이루어진 자료구조이다. 정점은 노드, 간선은 노드를 연결하는 선으로 생각하면 된다. 그렇다고 해서 노드 간 부모 자식이라는 관계는 존재하지 않고 그냥 연결관계만 나타낸다. Tree와 비슷하지만, 그래프는 간선이 없는 노드도 존재한다는 점에서 차이를 나타낸다. 탐색방법 그래프 탐색이란 하나의 정점으로 부터 모든 정점들을 한번씩 방문하는 행위를 뜻한다. 예를 들어 섬끼리 이동할 수 있을지, 이동할 수 있다면 시간이 얼마나 걸리는지 등의 예시에서 사용될 수 있다. 어떤식으로 방문해야 할까? 여기서 두가지 방법이 있다. DFS 깊이 우선 탐색 BFS 너비 우선 탐색 구현 인접 행렬과 인접리스트 방식으로 구현할 수 있다. 인접행렬 2차원 배열 안에 모든 정점들의 ..

구름? 컴퓨터..? 뭐지 클라우드와 컴퓨팅 모두 들어본적 있는 단어이다. 그러나 클라우드 컴퓨팅이 뭐야? 라고 묻는다면 뭐라고 말해야될지 모르겠다. 이 참에 정리해보려고 한다. 개념 클라우드 컴퓨팅이란 인터넷 상의 가상의 서버(컴퓨터)를 두고 필요할때마다 불러오는 서비스를 뜻한다. 자원,스토리지,디비 등의 자원을 필요에 따라 꺼내 쓰는 것이다. 과거에 서버 컴퓨터를 만들기 위해서는 미리 물리적인 컴퓨터를 사놔야했다. 현재에는 클라우드 컴퓨팅을 운영하는 업체들이, 간단한 클릭 만으로 서버 컴퓨터를 제공하고 있다. 그 업체 중 가장 유명한것이 바로 우리가 많이 들어본 AWS 이다. 그렇다면 클라우드를 사용함으로써 얻게 되는 이점을 뭘까? 가장 먼저 생각나는 이득은 비용 절감이다. 사용한 만큼만 비용을 지불하..