프로그래밍 공부

큐는 데이터를 처리하기 위해 일시적으로 쌓아 놓은 자료구조이다. 하지만 큐는 스택과는 다르게 가장 먼저 넣은 데이터를 가장 먼저 꺼내는 선입선출(FIFO, First In First Out)인 점이 스택과 다르다. 쉽게 이해하려면 은행 창구나 선착순 시스템을 생각하면 된다 먼저 온 사람한테 서비스를 제공하듯이 큐도 먼저 들어온 데이터부터 우선 처리해준다. 선형 큐도 있지만 원형 큐를 구현할 줄 알면 선형 큐도 구현할 수 있으니 굳이 설명하지 않는다. 코드 #include using namespace std; struct queue{ int max; // 큐의 최대 용량 int size; // 현재 요소의 개수 int front; // 프런트 int rear; // 리어 int *que; // 큐의 맨 앞..

스택은 데이터를 일시적으로 저장하기 위한 자료구조로 후입선출(LIFO, Last In First Out)이다. 말그대로 데이터를 쌓는다는 느낌으로 이해하면 된다 가장 나중에 쌓은 접시를 제일 먼저 사용하게 된다고 생각하면 이해하기 편할것이다. #include using namespace std; struct stk{ int max; int ptr; int *stk; }; int stk_init(stk* s, int max){ // 스택을 초기화 s->ptr = 0; if((s->stk = new int[max]) == NULL){ s->max = 0; return -1; } s->max = max; return 0; } int push(stk* s, int data){ // 스택에 데이터를 추가 if(s..

배열에서 데이터를 검사하는 방법중 하나인 선형 검색 또는 순차 검색으로 불리는 방법은 배열에서 데이터를 찾는 가장기본적인 방법이지만 확실하게 모든 요소를 검색할수 있고 정렬되지 않은 배열도 검색할수 있다는점이 장점이다. 말그대로 순서대로 배열을 검색하는 방법인데 배열의 처음 요소 부터 배열의 끝 요소 까지 반복하며 데이터를 찾습니다 반복문을 사용하여 구현합니다. while문 사용 int linear_search_while(const int arr[], int n , int key){ // while syntax int i = 0; while(true){ if(i == n){ return -1; } if(arr[i] == key){ return i; } i++; } } for 문 사용 int linear_..

https://www.acmicpc.net/problem/13549 13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 언어 : C++17 환경 : VSCode gcc 8.1.0 1697번 숨바꼭질과 비슷하다 하지만 여기서는 순간이동을 할 때는 0초 만에 이동하기 때문에 현재 dist의 내용에서 +1을 하지 않고 계속 BFS를 돌려주면 된다. 이때 순간이동이 이동시간이 더 빠르기 때문에 순간이동부터 먼저 계산해준다. 코드 #include using namespace std; int..

https://www.acmicpc.net/problem/15921 15921번: 수찬은 마린보이야!! 기댓값 E(X)의 정의는 ‘각 사건이 벌어졌을 때의 이득과 그 사건이 벌어질 확률을 곱한 것을 전체 사건에 대해 합한 값’이다. 다시 말해, 어떤 수 x가 수열에 등장할 확률 P(x) = (x의 등장 횟수) / www.acmicpc.net 언어 : C++14 환경 : Visual Studio 2019 이 문제를 푸는 방법은 2가지가 있다 하나는 문제의 힌트를 사용해서 또는 평균값과 기댓값은 일반적으로 같다는 것을 이용하는 방법. 문제의 힌트를 사용해서 일일이 계산을 해주는 방법. #include using namespace std; struct Record { // 점수를 저장할 구조체 double s..

https://www.acmicpc.net/problem/1654 1654번: 랜선 자르기 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 www.acmicpc.net 언어 : C++14 환경 : ideone.com - https://ideone.com Parametric Search를 이용한 문제입니다. 아이디어는 입력받는 값 중 최솟값은 1, 최댓값을 end 변수에 넣고 중앙값을 구해준 다음 배열의 원소를 중앙값으로 나눈 값을 cnt 변수에 더해줘서 몇 개의 랜선을 만들 수 있는지 계산했다. cnt 값이 n값 즉 필요한 랜선의 개..