![]()
기존에 c를 하다가 이번에 c++로 넘어오게되었는데, 개인적으로 엄청 편리하다고 생각한 기능이 vector였다. (물론 stack,queue도 많이 쓰지만 그 중에서 가장 유용하다고 생각함 ㅎㅎ..) vector란 C++ STL(Standard Template Library)에 있는 container이다. 쉽게 이해하자면 자동으로 메모리 할당이 되는 배열이라고 생각하면 편하다. --> 자동으로 메모리 할당이 된다는게 엄청나게 큰 이점이고 c++의 장점이라고 생각한다. vector를 사용하기 위해서는 아래처럼 헤더파일을 추가해줘야한다. #include 2)vector 선언방법 vector배열이름; //자료형으로 배열을 만듬. 크기는 0 vector배열이름(size) // size만큼 자료형으로 배열을 만듬..
![]()
문제 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집들의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여기서 연결되었다는 것은 어떤 집이 좌우, 혹은 아래위로 다른 집이 있는 경우를 말한다. 대각선 상에 집이 있는 경우는 연결된 것이 아니다. 는 을 단지별로 번호를 붙인 것이다. 지도를 입력하여 단지수를 출력하고, 각 단지에 속하는 집의 수를 오름차순으로 정렬하여 출력하는 프로그램을 작성하시오. 입력 첫 번째 줄에는 지도의 크기 N(정사각형이므로 가로와 세로의 크기는 같으며 5≤N≤25)이 입력되고, 그 다음 N 줄에는 각각 N개의 자료(0 혹은 1)가 입력된다. 출력 첫 번째 줄에는 총 단지수를 출력하시오. 그리..
![]()
코드를 짜는데 map의 개념이 부족해서 굉장히 시간이 오래 걸렸다. 그래서 부족한 개념을 정리하는데 이 카테고리를 쓸 예정이다. map이란? map을 이해하기 위해서는 set에 대한 이해가 필요합니다. set은 key라고 불리는 원소들의 집합으로 이루어진 컨테이너입니다. key에서 중요한 특징은 중복을 허용하지 않는다는 점입니다. set은 key값의 순서대로 정렬이 되는 특징이 있습니다. 이때의 정렬 방식은 inorder방식을 따릅니다. 중복되면 안 되고 정렬이 되어있다.!! 그럼 map은 무엇이냐? map은 set에서 value값이 추가된 것이라고 보면 된다. map은 set에서 추가된 것이기 때문에 중복을 허용하지 않지만, value는 중복을 허용한다. map의 기본 형태는 map m; map은 pa..
![]()
●허프만 코드란? 데이터를 효율적으로 압축하기 위해서 만들어진 알고리즘. 탐욕법을 사용함. 데이터 파일은 통상적으로 이진 코드(binary code)로 표현한다. 각 문자는 코드 워드(code word)라고 하는 유일한 이진 문자열로 표현한다. ●fixed length binary code 각 문자를 표현하는 bit의 개수가 일정하다. 예를 들어 문자의 집합이 {a,b,c}라면 bit 2개만으로 문자를 코드화 할 수 있다. bit 2개로는 4개의 문자를 bit 3개로는 8개의 문자를 표현할 수 있다. a : 00 b:01 c:11 이라고 가정하자. 만약 File이 ababcbbbc라면 결과 코드는 000100011001010110일것이다. ->18비트를 사용한다. ●variable-length binar..
![]()
Knapsack Problem(배낭문제) 1)Fractional Knapsack Problem 보석의 무게를 쪼갤 수 있다는 가정을 둔다. 예를 들어 보석이 10kg라도 내가 들고가고싶은 만큼 담아서 가방에 넣을 수 있다. ->greedy를 이용해서 해결 2)0-1 Knapsack Problem 보석의 무게를 쪼 갤 수없다. 예를 들어 보석이 10kg라면 10kg 그대로 가방에 담아야 한다. ->dynamic programming을 이용해서 해결 배낭문제의 목표는 가방에 담는 보석들의 가치 합이 최대가 되야한다. ●Greedy Approach 탐욕법을 통한 전략은 다음과 같다. 단위 무게당 가치가 가장 큰 보석을 담는다. 가방에 최대 무게가 넘지않을때까지 보석을 담는다. 이러한 접근법은 보석을 쪼갤수있는..
![]()
Scheduling problem은 운영체제에서 다루는 개념이다. 최대한 적은 시간을 사용하면서 많은 작업을 해야 효율적이다 어떻게 하면 효율적으로 배치할 수 있을까? ●FCFS(First-come , First served) 들어온 순서대로 일을 시작한다. 도착 순서는 P1->P2->P3이라고 가정하자. FCFS의 방식은 p1이 먼저 도착했으니까 p1의 일을 다 끝내기 전까지 p2, p3는 일을 시작하지 못한다. P1, P2, P3의 모든 작업이 끝나는데 소요되는 시간은 30이지만, P1, P2, P3가 기다리는 시간은 24+27 = 51이다. p2, p3는 p1에 비해 굉장히 적은 시간을 사용하는 작업임에도 불구하고 p1이 끝날 때까지 기다려야 한다. 이러한 알고리즘은 굉장히 효율적이지 못하다. ●S..
![]()
●정규성 검정 데이터셋의 분포가 정규분포를 따르는지를 검정하는 것이다. ▷정규성 검정을 하는 방법 Q-Q plot Q-Q plot는 정규분포 분 위수 대조 도라 고한다. 정규 모집단 가정을 하는 방법 줌 하나이며, 수집 데이터를 표준 정규분포의 분 위수와 비교하여 그리는 그래프이다. ○정규 확률 그림 par(mfrow=c(1,2)); n=10 x=rnorm(n,0,1) hist(x,prob=T,main="Normal(0,1)",col=2) curve(dnorm(x),add=T,col=4) ## qqnorm(x,sub="Normal") ## Q-Q plot qqline(x) ##y=x 그래프 추가 --> 난수의 개수가 적어서 히스토그램 그래프와 q-q plot에서 모양이 틀어짐을 알 수 있다. ★난수의 개..
![]()
알고리즘의 효율성을 분석 할때 시간복잡도를 많이 사용한다. 일반적으로, 알고리즘의 실행시간은 1.입력의 크기(input size)가 커지면 증가하고 2.총 실행시간은 단위연산(+,-,x,/)이 몇번 수행되는가에 비례한다. ● inputsize에만 영향을 받는 경우 #include using namespace std; int main() { int n, sum = 0; cin >> n; for (int i = 0; i n; for (int i = 0; i < n; i++) { F.push_back(i); } cout n; for (int i = 0; i < n; i++) { F.push_back(i); } cout
![]()
피보나치수열: 첫째항은 0 둘째 항이 1이며 그다음 항부터는 바로 앞 두항의 합이다. ex) 0,1,1,2,3,5,8,13,21,34,55,89 ㆍㆍㆍㆍㆍㆍ #include #include using namespace std; int fibo(int n); int main() { int n; cin >> n; cout > n; cout
