c언어

C언어 스택(stack)

✔️Stack 이란? 먼저 들어간 자료가 나중에 나오는 자료구조. 후입선출 FILO(First In Last Out) ❓ Restricted structure 특정 위치에서만 원소를 넣거나 뺄 수 있는 제한이 걸려있는 자료구조 ex) 스택, 큐, 덱 ... ✔️원소의 삽입, 제거, 확인 시간복잡도 O(1) 원소의 확인은 원칙적으로 상단만 가능하다. 상단이 아닌 나머지 원소들의 확인, 변경이 불가하다. 추가, 제거, 상단 원소 확인 외에는 스택이 제공하는 기능이 아니다. [코드] // BOJ_10828 #include #define SIZE 10000 int arr[SIZE]; int top = 0; int push(int x) { if (top >= SIZE) return 0; arr[top++] = x..

[C언어] LIS (Longest Increasing Subsequence) 최장 증가 수열 DP/binary search

LIS : 어떠한 수열에서 오름차순으로 증가하는 가장 긴 부분 수열. 부분수열의 각 수는 서로 연속할 필요는 없다 LIS 길이 구하기 : 가장 단순한 방법은 완전 탐색을 하는 것이다. 수열의 개수가 K개 -> 1개 이상의 원소를 갖는 부분 수열의 가짓수는 2^K 즉, 모든 부분 수열을 확인해 오름차순으로 정렬되어 있는지 확인하는 것은 매우 비효율적이다. 이를 개선하기 위해 다이나믹 프로그래밍으로 구현 가능하다. #1 DP(Dynamic Programming) 시간 복잡도 : O(n^2) 수열의 한 원소(k)에 대해, 그 원소에서 끝내는 최장 증가 수열 길이를 저장한다. => k를 제외한 모든 원소는 k보다 작아야 한다. 따라서 k의 앞 순서에 있는 모든 원소들 중 값이 k보다 작은 원소에 대해, 그 각각..

C언어 max/min 사용하기

C 언어의 기본 라이브러리에는 최소와 최대를 구하는 min, max 함수가 없다. #define MIN(X,Y) ((X) (Y) ? (X) : (Y)) 선언해놓고 사용하자.

[C언어 기초 정리] #1 절차 지향 프로그래밍 C언어

이 카테고리는 2020년 1학기 교내에서 진행한 튜터링 활동에 쓰였던 자료를 기반으로 C언어 프로그래밍에 관한 내용을 정리한 것이다. ​ 이곳에 적은 글들은 전부 내가 배운 것을 튜티에게 설명해주기 위해 정리한 내용으로 틀리거나 부족한 내용이 있을 수 있다. 그러므로 지적/수정은 언제나 환영이다 :) 1. 프로그래밍 언어의 시작 Hello, World! 를 출력해보자. 보통 프로그래밍 언어를 처음 시작한다면 국룰은 헬로월드이다 #include int main(void) { printf(“Hello, World!”); //Hello, World가 출력된다!! } //뒤에 표시된 문장들은 주석 이라고 표현한다. 주석은 실제 프로그래밍에 영향을 주지 않는 개발자의 메모이다. 2. 하나하나 뜯어보자 #inclu..

[BOJ/C] 10828 스택

https://www.acmicpc.net/problem/10828 10828번: 스택 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 www.acmicpc.net 알고리즘 분류 : 스택 문제 정수를 저장하는 스택을 구현한 다음, 입력으로 주어지는 명령을 처리하는 프로그램을 작성하시오. 명령은 총 다섯 가지이다. push X: 정수 X를 스택에 넣는 연산이다. pop: 스택에서 가장 위에 있는 정수를 빼고, 그 수를 출력한다. 만약 스택에 들어있는 정수가 없는 경우에는 -1을 출력한다. size: 스택에 들어있는 정수의 개수를 출력한다. e..

[BOJ/C] 2504 괄호의 값

https://www.acmicpc.net/problem/2504 2504번: 괄호의 값 4개의 기호 ‘(’, ‘)’, ‘[’, ‘]’를 이용해서 만들어지는 괄호열 중에서 올바른 괄호열이란 다음과 같이 정의된다. 한 쌍의 괄호로만 이루어진 ‘()’와 ‘[]’는 올바른 괄호열이다. 만일 www.acmicpc.net 알고리즘 분류 : 스택 문제 티어 : 실버2 문제 4개의 기호 ‘(’, ‘)’, ‘[’, ‘]’를 이용해서 만들어지는 괄호열 중에서 올바른 괄호열이란 다음과 같이 정의된다. 한 쌍의 괄호로만 이루어진 ‘()’와 ‘[]’는 올바른 괄호열이다. 만일 X가 올바른 괄호열이면 ‘(X)’이나 ‘[X]’도 모두 올바른 괄호열이 된다. X와 Y 모두 올바른 괄호열이라면 이들을 결합한 XY도 올바른 괄호열이 ..