본문 바로가기
반응형

컴퓨터공학27

희소행렬과 희소행렬의 자료구조 저장법 희소행렬 희소행렬(sparse matrix)은 행렬의 값이 대부분 0인 경우를 가리키는 표현이다. 그와 반대되는 표현으로는 밀집행렬(dense matrix), 조밀행렬이 사용된다. 개념적으로 희소성은 시스템들이 약하게 연결된 것에 해당한다. 한 줄로 나열된 공과 공이 스프링으로 양 옆으로 하나씩 연결되었을 때 이것은 희소 시스템이다. 그와 반대로 한 줄의 공들이 여러 방향의 공들과 스프링으로 연결되었을 때 이 시스템은 밀집 행렬이 될 수 있다. 희소의 개념은 조합론과 네트워크 이론 등과 같은 응용분야에서 유용하다. 희소행렬의 자료구조 저장법 Dictionary of keys 사전식 키(Dictionary of keys,DOK)방법은 행렬을 매핑된 연관 배열로 저장한다. 이때 키는 (행번호, 열번호)가 되.. 2021. 4. 21.
점근적 분석, 점근적 표기법, 시간 복잡도, 공간 복잡도 시간 복잡도 알고리즘의 연산 수에 따른 수행시간 공간 복잡도 알고리즘이 소요 하는 메모리의 사용량 점근적 분석을 해야 하는 이유 문제를 알고리즘으로 푸는 방법은 하나만 있지 않고 다양한 방법이 있습니다. 다양한 방법과 하드웨어 및 상황에 따라 성능이 좌지우지 됩니다. 문제를 해결하는 알고리즘이 최적의 성능을 낼 수 있는지 확인 할 필요가 있습니다. 점근적 분석이란 입력 되는 데이터의 크기에 따라 수행 시간과 공간을 얼마나 차지하는지를 측정합니다. 이를 통해 효율적인 알고리즘인지를 판단합니다. 정확한것은 아니고 대략 이런식으로 수행시간이 나온다라는걸 측정하는 용도로 사용합니다. 측정의 용도로 사용하기에 최악의 경우를 측정 할 수 있는 빅오 표기법을 주로 사용합니다. 복잡도를 표현하는 방법으로 O(빅오), .. 2021. 4. 21.
점화식이란 recurrence relation · 漸化式 수학에서 점화식(漸化式) 또는 재귀식(再歸式, 영어: recurrence relation)이란 수열에서 이웃하는 두개의 항 사이에 성립하는 관계를 나타낸 관계식이다. 어떤 수열의 각각의 항들의 관계를 나타낸 식이다. 점화식을 만족하는 수열을 점화식의 해라 하고, 이 해를 찾는 것을 점화식을 푼다고 말한다. 벡터, 행렬 등 다른 수학적 대상의 열을 묘사하는 점화식들도 생각할 수 있고, 마치 파스칼의 삼각형 항등식처럼 2개 이상의 변수를 갖는 수열에 대해서 생각할 수도 있다. 보통 점화식은 n번째의 항을 이전에 나온 항들로 나타내는 공식으로 나타나고, 이 점화식을 만족하는 수열은 초깃값에 따라 유일하게 결정된다. 이렇게 수열을 정의하는 것을 수열의 귀납적 정의(.. 2021. 4. 21.
[프로그래머스] 스택/큐 주식가격 JAVA 자바풀이 초 단위로 기록된 주식가격이 담긴 배열 prices가 매개변수로 주어질 때, 가격이 떨어지지 않은 기간은 몇 초인지를 return 하도록 solution 함수를 완성하세요.제한사항 prices의 각 가격은 1 이상 10,000 이하인 자연수입니다. prices의 길이는 2 이상 100,000 이하입니다. 입출력 예 pricesreturn [1, 2, 3, 2, 3] [4, 3, 1, 1, 0] 입출력 예 설명 1초 시점의 ₩1은 끝까지 가격이 떨어지지 않았습니다. 2초 시점의 ₩2은 끝까지 가격이 떨어지지 않았습니다. 3초 시점의 ₩3은 1초뒤에 가격이 떨어집니다. 따라서 1초간 가격이 떨어지지 않은 것으로 봅니다. 4초 시점의 ₩2은 1초간 가격이 떨어지지 않았습니다. 5초 시점의 ₩3은 0초간 가격이.. 2021. 4. 18.
[프로그래머스] 깊이/너비 우선 탐색(DFS/BFS) 프로그래머스에서 알고리즘 문제를 하나 풀었는데 깊이/너비 우선 탐색(DFS/BFS) 와 관련된 문제였다. 아래와 같이 재귀적으로 풀어내는 문제였는데 깊이 너비 우선탐색에 대해서 좀 더 자세히 알아보고 싶어졌다. class Solution { public int solution(int[] numbers, int target) { int answer = 0; answer = dfs(numbers, 0, 0, target); return answer; } int dfs(int[] numbers, int n, int sum, int target) { if(n == numbers.length) { if(sum == target) { return 1; } return 0; } return dfs(numbers, n.. 2021. 4. 17.
String.format("%%%ds*\n", (i * 4) + 3), "") 코드 해석 Do it 자료구조와 함께 배우는 알고리즘 자바편 공부중 아래 코드가 생소해서 검색해보았다 String.format("%%%ds*\n", (i * 4) + 3), ""); String.format은 알고있었지만 %%% 이렇게 %가 세개가 있는 코드는 처음봤다. 검색해보니 %%가 format함수 안에서는 %로 인식된다고 한다. 만약 위에서 i가 2라면 i*4+3은 11이다. %%%ds*\n 에서 먼저 %d에 우측에서 계산한 결과값을 넣으면 String.format("%%11s*\n, ""); 가 된다 논리적으로는 %11s*\n 와 같아진다. 즉 아무 글자도 없는 String인 ""를 11글자의 넓이에 맞춰서 형식을 맞춰준 후 *을 하나 찍어주고 엔터를 친다. 결과적으로 아래와 같은 모양으로 현재 위치를 *.. 2021. 4. 17.
[자료구조] 배열과 리스트 데이터 집합이 있을때 검색만 하면 된다고 생각한다면 검색에 사용할 알고리즘은 계산 시간이 가장 짧은것을 선택하면 된다. 그러나 데이터 집합에 대한 검색뿐아니라 데이터의 추가, 삭제 등을 자주하는 경우라면 검색 이외의 작업에 소요되는 비용을 종합적으로 평가하여 알고리즘을 선택해야 한다. 리스트는 포인터를 사용해 자료를 순차적으로 저장하는 선형 자료구조를 말한다. 실제로 배열과 리스트의 차이는 속도와 자료의 크기에서 나타난다. 배열은 기본적으로 인덱스로 자료를 찾기 때문에, 자료의 삽입, 삭제, 검색에서 리스트보다 무조건 빠르다. 하지만 고정된 데이터 크기 때문에 메모리의 낭비가 심하다는 단점이 있다. 리스트는 고정된 크기 없이 포인터로 자료들을 연결하기에, 자유자재로 데이터의 크기를 바꿀 수 있다. 하지만.. 2021. 4. 17.
반응형