알고리즘에 많이 쓰이는 함수 & 라이브러리

알고리즘 풀이에 많이 쓰이는 함수 & 라이브러리를 모아두었다

 

공통

---

- 절대값 활용

- 수를 세거나 위치 표시/계산 등 여러 가지 형태의 문제에서 배열을 사용하면 문제가 빠르고 쉽게 풀리는 경우가 있다.

- 문자열을 int 형태의 배열에 받아 처리하는 경우, 널 문자[\0]의  처리에 주의한다.

- 문자열 배열의 경우, 문자열을 한 번에 받는 식으로 반복하여 받을 수 있다.

- 변수/배열을 사용할 경우 초기화 필수

 

C언어/C++

---

- C/C++ Reference

 

- <stdlib.h> 헤더

(1) strtol 함수 : 진법으로 표기된 문자열을 정수로 변환시켜준다. 

https://khsc.tistory.com/43

 

- printf 함수 포맷

 

- scanf 함수 포맷

 

- scanf("%[^\n]\n",s)

- scanf 무한 입력 : while(scanf("%d", &n)+1) => scanf 값이 음수가 되면 while 문이 멈춘다.

 

- 데이터 형식 범위

 

- int와 long은 무엇이 다를까

 

- C언어/C++에서 문자열이 할당된 변수는 주소 값이므로 직접 비교해서는 안 된다. String 관련해서 정의되어 있는 함수를 사용한다.

 

- 배열 초기화에는 memset 함수를 활용한다.

#include <memory.h> 또는
#include <string.h>

// 매개변수 : 배열 이름, 초기화할 값, 바이트 단위의 초기화할 영역 크기
void * memset ( void * ptr, int value, size_t num );

 

※ memset 함수를 사용할 때 주의해야 할 점

1) 1 Bytes 변수[char, unsigned char 등]를 제외한 변수를 초기화 할 때는 0 이외의 값으로 초기화를 하면 안 된다.

// 이 코드의 경우 Byte 단위로 처리가 되어
// n = [00000001000000010000000100000001] = 16843009의 원하지 않는 값으로 초기화가 된다.
int n;
memset(&n, 1, sizeof(int));

 

2) new, malloc 등을 이용하여 동적으로 배열을 생성하는 변수가 있는 struct, class에서는 memset으로 초기화를 하면 안 된다.

// sizeof(A)는 struct member alignment가 어떤 값이든 4(int i) + 4(char* c, address는 4) = 8 Bytes가 된다.
// 그러므로 위의 소스는 동적으로 생성한 변수는 초기화가 되지 못하고, char* c가 NULL로 초기화가 되어
// 이전에 생성한 메모리는 메모리 누수가 발생하게 된다.
struct A
{
   int i;
   char* c;
};

void main()
{
   A a;
   a.c = new char[100];
   memset(&a, 0, sizeof(A));
   if(a.c != NULL)
   {
      delete[] a.c;
      a.c = NULL;
   }
}

// 위와 같이 동적으로 생성하는 경우는 아래와 같이 각각을 분리하여 초기화를 해야 한다.
a.i = 0;
memset(a.c, 0, sizeof(char)*100);

 

3) CString은 절대 memset으로 초기화를 하면 안 된다.

CString은 내부적으로 m_pchData 변수를 동적으로 생성하여 문자열을 저장한다.
이 변수에 대한 직접적인 접근은 private로 막혀 있다.
그래서 CString, 또는 CString을 member variable을 가지고 있는 struct, class를 memset을 이용하여 초기화를 하면 안 된다. CString을 memset으로 초기화를 하면 메모리 누수뿐만 아니라, run-time error도 발생한다.

 

4) virtual function을 가지고 있는 struct, class에서는 절대 memset으로 초기화를 하면 안 된다.

실제 실행될 함수의 주소를 가리키는 공간(4 Bytes)을 추가로 가지게 되므로, virtual function이 NULL로 바인딩되어 실행할 수 없게 된다.

 

 

파이썬

---

- 파이썬에서 재귀를 사용하여 문제를 해결할 때는 다음 코드를 사용한다. 파이썬의 기본 재귀 깊이 제한은 1000으로 매우 얕은 편이기 때문에, 재귀로 알고리즘 문제를 풀 경우 자주 이 제한에 걸리게 된다.

import sys
sys.setrecursionlimit(10 ** 6)

 

 

- 파이썬에서 리스트를 만들 때는 리스트 컴프리헨션[list comprehension]을 자주 쓰게 된다.

# 0~9 숫자 중 2의 배수인 숫자(짝수)로 리스트 생성
>>> a = [i for i in range(10) if i % 2 == 0]
>>> a
[0, 2, 4, 6, 8]

# 2단부터 9단까지 구구단을 리스트 생성
>>> a = [i * j for j in range(2, 10) for i in range(1, 10)]
>>> a
[2, 4, 6, 8, 10, 12, 14, 16, 18, 3, 6, 9, 12, 15, 18, 21, 24, 27, 4, 8, 12, 16, 20, 24, 28, 32, 36, 5, 10, 15, 20, 25, 30, 35, 40, 45, 6, 12, 18, 24, 30, 36, 42, 48, 54, 7, 14, 21, 28, 35, 42, 49, 56, 63, 8, 16, 24, 32, 40, 48, 56, 64, 72, 9, 18, 27, 36, 45, 54, 63, 72, 81]

# 두 줄로 쓸 수도 있다.
a = [i * j for j in range(2, 10)
           for i in range(1, 10)]

 

- 입력을 빠르게 받을 때는 open((0))을 활용할 수 있다. open((0))는 이터레이터 형식으로 파일의 내용을 읽어 주며, 안의 숫자는 File Descriptor이다.

 

- 리스트 언패킹[*]과 딕셔너리 언패킹[**]을 활용한다.

 

- 파이썬 3.8부터 바다코끼리 연산자[:=]를 활용할 수 있다.

# 파이썬 3.8 새로운 기능 문서 : https://docs.python.org/ko/3/whatsnew/3.8.html
# 기본 예시 : len(a)이라는 표현식에 n이라는 이름을 부여하여, 할당과 사용을 한 단계로 줄일 수 있다.
if (n := len(a)) > 10:
    print(f"List is too long ({n} elements, expected <= 10)")

 

- list 자료형 + reverse 함수

 

- set 자료형

 

출처

---

• memset 함수 사용 시 주의사항
• 파이썬 코딩도장
• open(0) : 1
• 파이썬 3.8의 새로운 기능