CS(36)
-
C언어에서 포인터(pointer)의 개념
C언어에서 포인터란, 메모리의 주소 값을 저장하는 변수이다. 포인터는 아래와 같이 선언한다. int n = 150; int *p = &n; 정수 값 150은 n이라는 변수 안에 저장되며, 이는 메모리 상에 어떤 공간에 할당된다. 150의 값을 가지는 n이 어떻게 메모리에 할당되는지 알아보자. 컴퓨터의 메모리 구조 컴퓨터에서 int 자료형이 저장될 때는 메모리 상에서 아래와 같이 저장된다. 메모리 주소 당 8자리 이진수가 들어가고, 이를 바이트(byte)라고 한다. 이때 이진수 하나를 비트(bit)라고 한다. 즉 8비트 = 1바이트 이다. 일반적인 컴퓨터에서 int를 저장할 때, 총 4바이트의 공간을 차지한다. 즉 0x51이라는 메모리 주소에 정수를 저장하고 싶다면 0x51~0x54의 4칸을 차지하는 것이..
2024.03.28 -
[열혈자료구조] 2강. 재귀(Recursion)
* 본 글은 [윤성우의 열혈 자료구조 - C언어를 이용한 자료구조 학습서] 를 바탕으로 작성하였습니다. 재귀는 자료구조와 알고리즘에서 매우 중요한 요소이다. 재귀함수의 기본적 이해 void Recursive(){ printf("Recursive Call\n"); Recursive(); } 재귀함수는 위와 같이 함수 안에서 함수를 다시 호출하는 형태이다. 그러나 Recursive의 정의 부분에서 Recursive를 호출하고 있는데, 정의가 끝나지 않은 함수를 다시 호출하는 것이 가능한가? 재귀함수가 작동할 때 아래와 같이 메모리상에서 함수의 복사본을 여러 개 만들고 다시 호출한다. 즉, 함수의 명령문을 실행할 때 CPU로 불러와서 사용하는데, 명령문을 실행하는 중간에 재귀 조건이 등장한다면 CPU로 하나 ..
2024.03.27 -
[열혈자료구조] 1강. 자료구조와 알고리즘의 이해
* 본 글은 [윤성우의 열혈 자료구조 - C언어를 이용한 자료구조 학습서] 를 바탕으로 작성하였습니다. 자료구조 vs 알고리즘 자료구조: 데이터의 표현 및 저장 방법 알고리즘: 표현 및 저장된 데이터를 대상으로 하는 문제의 해결방법 즉 데이터 자체를 다루는 것이 자료구조, 데이터를 가지고 문제를 해결하는 것이 알고리즘이다. ex) 자료구조의 예시: 배열의 선언 int arr[10] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}; 알고리즘의 예시: 반복분의 구성 for(idx=0; idx
2024.03.27 -
스택구조 문제풀이 (백준 28278번, 4949번, 12789번)
백준 28278번: 스택 2 정수를 저장하는 스택을 구현한 다음, 입력으로 주어지는 명령을 처리하는 프로그램을 작성하시오. 명령은 총 다섯 가지이다. 1 X: 정수 X를 스택에 넣는다. (1 ≤ X ≤ 100,000) 2: 스택에 정수가 있다면 맨 위의 정수를 빼고 출력한다. 없다면 -1을 대신 출력한다. 3: 스택에 들어있는 정수의 개수를 출력한다. 4: 스택이 비어있으면 1, 아니면 0을 출력한다. 5: 스택에 정수가 있다면 맨 위의 정수를 출력한다. 없다면 -1을 대신 출력한다. 10828번 스택 문항과 굉장히 유사하다. 사실상 command가 문자열에서 숫자로 바뀐 것 말고는 똑같은 문제이다. 마찬가지로 시간 초과에 주의해야 하기에 input() 대신 sys 내장모듈을 이용하여 sys.stdin...
2024.03.26 -
탐색 알고리즘 (백준 1920번)
무작위로 N개의 수가 들어있는 리스트가 있다고 하자. 이 안에 특정 수 x가 들어있는지 찾는 최적의 알고리즘은 무엇일까? 이런 류의 문제를 탐색(searching)문제라고 한다. 탐색 문제에는 크게 세 가지 알고리즘이 있다. 선형 탐색(linear searching) 복잡도 : O(N) 선형 탐색은 N개의 수를 하나씩 차례대로 x인지 비교하는 방법이다. 이는 가장 간단한 알고리즘이지만 N이 커질 때 복잡도가 크게 늘어난다. 파이썬의 in 연산자가 선형 탐색을 이용한다. 이진 탐색(binary searching) 복잡도 : O(logN) 정렬된 리스트에서 사용 가능한 알고리즘으로, 아래의 순서로 진행된다. 리스트의 중간 인덱스를 잡고, 해당 인덱스의 값을 x와 비교하여 같으면 종료한다. 다르다면, 크기를 ..
2024.03.25 -
스택(stack)구조란? (백준 9012번, 10828번)
스택 구조란, 쌓여 있는(stack) 더미처럼 된 자료구조를 말한다. 그림처럼 쌓은 수건을 위에서부터 사용하면서, 빨래한 새 수건을 다시 위에 쌓으면 아래 있는 수건은 계속 안 써서 먼지가 쌓인다. 이 구조가 스택 구조이다. 스택 구조는 나중에 들어온 데이터가 먼저 나가는 LIFO(Last In, First Out) 구조이다. 또한, 스택에 데이터를 넣는 것을 push, 데이터를 (위에서) 빼는 것을 pop이라고 한다. 백준 9012번: 괄호 백준 9012번(괄호)는 스택 문제의 대표적인 유형이다. 괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인 ‘(’ 와 ‘)’ 만으로 구성되어 있는 문자열이다. 그 중에서 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열(Valid..
2024.03.25