분류 전체보기
시간복잡도와 공간복잡도
시간복잡도와 공간복잡도
2022.03.31시간 복잡도는 코드의 실행 시간을 의미하고, 공간복잡도는 코드가 메모리를 얼마나 잡아먹는지를 의미한다. 배열에서 특정 원소에 접근할 때는 인덱스를 기반으로 한 번에 찾아갈 수 있지만, LinkedList에서 특정 원소에 접근하려하면 처음이나 끝에서부터 시작해서 특정 원소의 위치까지 접근해야 한다. 이 때 배열은 원소의 접근에 있어서 시간복잡도가 낮고, 링크드리스트는 접근에 있어서 시간복잡도가 높다고 할 수 있다. C언어에서 int타입은 4바이트, char타입은 1바이트 등.. 변수를 선언하면 메모리에 주소값이 할당된다. 여기서 할당되는 메모리를 효율적으로 사용하면 공간복잡도가 낮다고 할 수 있다. 최근에는 대용량 시스템이 보편화돼서 공간복잡도보다는 시간복잡도를 향상시키는 쪽으로 기울고 있지만, 공간복잡도..
Java와 자료구조 - 배열
Java와 자료구조 - 배열
2022.03.29특정 타입의 데이터를 연속된 형태로 묶어놓은 자료구조로, 인덱스로 데이터에 접근할 수 있어 접근에 대한 시간복잡도가 매우 낮다. ( O(1) ) 배열을 선언할 때 메모리를 할당해야 한다. 간단하게 계산할 수 있다. (타입의 크기) * (배열의 크기) int[100][100]크기의 배열을 선언하면 4 * 100 * 100이 메모리에 할당된다. 정해진 타입의 데이터를, 입력 길이가 변하지 않을 때 배열을 사용하면 편하다. 구현이 간단하고 이해하기 쉬우며 앞에서 살펴봤듯 데이터에 접근하는 속도가 매우 빠르다는 장점이 있다.
[C] 포인터
[C] 포인터
2022.03.28포인터는 메모리 공간의 주소를 의미한다. 포인터만 따로 처리하는 타입으로 포인터 타입이 있다. ( * 로 표시하고, "%p"를 사용 ) 변수를 저장할 때 처음부터 포인터와 값을 함께 기록하면 좋지만, 저장할 때 메모리 공간이 따로 들어가고 매번 값을 확인해야 하기 때문에 잘 사용하지 않는다. 대신 크기별로 전담 변수를 둬 데이터의 타입으로 덩어리의 크기를 표현하는 방법을 사용한다. (int타입이면 int포인터, char타입이면 char포인터) int형 포인터 ptr1에 대해서 주소로 접근해 데이터를 읽을 때는 4byte를 한 덩어리로 보고 읽어온 값은 int형으로 처리한다. char형 포인터 ptr2에 대해서 주소로 접근해 데이터를 읽을 때는 1byte를 한 덩어리로 보고 읽어온 값은 char형으로 처리..
[C] 문자열
[C] 문자열
2022.03.28C에서는 boolean타입도 없지만 String타입도 없다. boolean대신 int타입을 대신해서 사용했고, String타입 대신 char타입의 배열로 String을 표현한다. char배열과 문자열의 구분은 문자열의 마지막에 '\0'의 유무로 판단한다. char배열의 끝에 모두 0으로 채우는 '\0'이 있으면 문자열로 인식하고, 그렇지 않으면 char배열로 인식한다. '\0'은 숫자로 해석 시 0이고, char로 해석 시 null로 해석하면 된다. char배열에서 '\0'을 만나면 뒤에 남아있는 요소에 상관없이 해석을 끝마친다. 즉, 널문자를 이용하면 문자열을 파싱할 수 있다. char str[10]; scanf("%s", str); printf("%s", str); scanf를 사용해 입력받을 때 문..
[C] 배열
[C] 배열
2022.03.28C에서는 자바와 배열의 선언 방식이 다르다. int arr[100]; 자바에서는 타입 뒤에 []가 와도 괜찮았지만, C에서는 변수명 뒤에 []를 붙여야 한다. 또, C에서는 객체지향 개념이 적용되지 않아서 저렇게 선언 후 바로 배열의 요소에 접근할 수 있다. int arr[100]; arr[1] = 12; 자바에서는 배열을 객체로 다루기 때문에 메모리 공간에 대해서 쉽게 이해할 수 있었다. 반면 C에서는 배열에 대해 생각해야 할 부분이 좀 있다. &는 주소를 의미한다고 보면 된다. rabbit[2] = 3; 같은 코드를 실행할 때, 배열의 시작인 rabbit[0]의 시작 부분(주소로는 100)에서 int사이즈의 크기인 4와 2를 곱한 값을 더해서 주소를 찾고, 값을 넣어준다. C에서 배열은 연속된 메모리..
Java와 자료구조 - Collection Framework 2
Java와 자료구조 - Collection Framework 2
2022.03.28Collection인터페이스를 구현하는 컬렉션들과 Map에 대해 이어서 살펴보자. HashSet Set인터페이스를 구현한 컬렉션이며, 역시 중복을 허용하지 않고 순서가 유지되지 않는다. 지정된 순서를 보장하지 않고 자체적인 저장방식에 의해 순서가 결정되기에, 순서가 중요한 경우는 LinkedHashSet 컬렉션을 사용하는 편이 합리적이다. 여기서 Hash는 해시 함수(Hash Function)를 이용해 데이터를 해시테이블에 저장하고 검색하는 기법을 의미한다. 해시를 통해 데이터가 저장된 위치를 빠르게 알 수 있어 많은 데이터 중 원하는 데이터를 빠르게 찾아올 수 있다. 해싱 기법에서 사용하는 자료구조는 배열과 링크드 리스트로 구성된다. 저장할 데이터의 키 값을 해시함수를 통해 배열의 한 요소를 얻고, 연..
Pytorch Lightning
Pytorch Lightning
2022.03.26Pytorch Lightning은 Pytorch보다 더 높은 수준의 추상화를 지원해 구조화된 코드를 작성할 수 있도록 한다. PL의 코드 스타일에 대해 살펴보자. 먼저 클래스(모델)를 선언한 다음, init함수에서 신경망 모델의 layer, 활성함수 등을 선언하고 forward에서는 이미 만든 layer를 활용해 모델을 구축한다. 그 다음 데이터를 준비한다. prepare_data함수에서 데이터를 입력받은 다음 텐서로 변환하고, 변환된 텐서에 대해 학습 / 검증 / 시험 단계를 거친다. 다음으로는 옵티마이저를 준비한 다음, 오차함수를 준비한다. 입력한 데이터를 최적화하는 과정이다. 즉, 학습 검증 평가 모드를 함수단위로 분할해서 진행한다. 각각의 단계를 자세히 살펴보자. epoch_end부분의 리턴타입은..
[C] 함수 간 소통 / 재귀
[C] 함수 간 소통 / 재귀
2022.03.22소통 전역변수를 이용하면 함수들 간에 정보를 교환할 수 있다. 하지만... 전역변수와 지역변수의 이름이 같을 때는 전역변수에 접근할 수 없고, 어떤 함수가 전역변수에 접근했는지 판단하기 어렵기 때문에 디버깅도 어렵다. 그러므로 두 함수 사이에서 소통하는 방법이 합리적이다. 지역 변수를 복사해서 건네주고, 또 리턴 값을 돌려받는 방식으로 함수들 간의 소통을 구현할 수 있다. 이 때 리턴할 수 있는 인자는 하나뿐이기에 이 부분에 주의해서 코드를 작성하자. 재귀 알고리즘 문제를 풀 때 분할 정복 방법으로 푸는 경우가 많다. 이 때 자신을 호출하는 재귀함수를 많이 사용한다. 속도와 성능 측면에서는 불리하지만, 코드를 간결하게 작성할 수 있을 경우 사용한다. 재귀함수는 base case부분과 재귀 호출 부분으로 ..
[C] Register / Volatile
[C] Register / Volatile
2022.03.22Register CPU가 자신과 가장 가깝게 가지고 있는 기억장치를 Register라고 한다. 메모리에 저장된 변수보다 레지스터에 저장된 변수를 읽어오는 것이 훨씬 빠르다. 빠르니까 다 레지스터에 넣으면 좋겠지만... 레지스터에 넣을 수 있는 변수는 한정되어있다. 레지스터에 어떤 변수를 넣을지는 컴파일러가 결정하고, 컴파일러에게 특정 변수를 레지스터에 넣어놓으라고 말할 때 register키워드를 사용한다. (모든 레지스터가 사용중이면 할당받지 못할 수 있다.) 레지스터에 있으면 좋은 변수로는 for문 안에서만 사용되는, 증감만 반복하는 변수들이 있다. i, j, count 등등.. Volatile int ready = 0; while(!ready){ printf("asdf\n"); } 이런 프로그램은 그..
[C] Scope
[C] Scope
2022.03.22함수와 여러 문법을 중첩해서 사용할 때, 변수의 이름이 겹치는 경우가 많아 내가 어떤 변수를 사용하게 될 지 헷갈리는 경우가 많이 발생한다. void func1(){ int i =0; while(1){ int k = 100; int i =1; while(1){ int i = 2; while(1) { printf("%d %d", k, i); // 어떤 k 이고 어떤 i 일까? } } } } 바로 위와 같은 경우인데, 이 경우 가장 가까운 Scope부터 변수를 탐색한다. 위에서는 k에는 100, i에는 2가 해당된다. 이를 Scoping 규칙이라고 한다. 변수의 Scope와 Lifetime을 헷갈리면 안된다. 개념을 명확히 하고 가자. Lifetime은 시간적인 개념이고, Scope는 공간적인 개념이라고 이..
[C] 스택 프레임
[C] 스택 프레임
2022.03.22스택 자료구조는 나중에 들어간 요소가 먼저 나오는 LIFO형태를 갖춘 자료구조이다. 함수가 동작할 때 스택 구조로 동작하게 된다. 메모리구조와 함수에 대해 알아보자. 사실 Data Segment와 Code Segment부분은 함께 붙어서 하드디스크에 존재한다고 생각해도 된다. 전역변수와 정적변수는 서로 비슷한 성질을 가져 혼용되어 사용하기도 하지만, 정적변수는 전역변수와는 달리 초기화가 한 번만 발생한다. 즉, static키워드가 붙은 정적변수는 프로그램이 시작될 때 한 번만 초기화되며, 함수의 매개변수로 사용할 수 없다. 프로그램을 실행할 때 데이터는 Data Segment / Stack Memory / Heap Memory 세 구간으로 나뉘어 위치하게 된다. 여기서 Data Segment부분의 전역변..
[C] 입문
[C] 입문
2022.03.22C는 자바와 달리 가비지 컬렉터가 없다. int asdf; printf("%d\n", asdf); 자바에서 위와 같이 작성하면 asdf가 기본값인 0으로 초기화되겠지만, C에서는 쓰레기값이 출력된다. C에서는 문자열 타입이 없고 char타입의 배열로 문자열을 사용한다. char asdf[] = "asdfasdf"; printf("%s", asdf); 입력은 scanf()함수로 처리한다. int input; scanf("%d", &input); printf("%d", input); printf와는 달리 변수 앞에 &를 붙여야 한다. 정수형 타입에는 네 가지가 있다. short // 2byte int // 4byte long // 4byte long long // 8byte 크기는 컴파일러마다 다를 수 있다..