본문 바로가기

분류 전체보기

 (224)
[C++] NULL과 nullptr NULL과 0은 다릅니다. NULL은 포인터이고 0은 int이니 사실은 비교도 되지 않습니다. NULL과 NOT NULL로 나뉘고, 0은 그저 NOT NULL에 불과합니다. [NULL] 초기화조차 안 한 상태. 포인터 변수에 넣어서 0 주소를 넣는 용도로 사용할 수도 있지만 일반 변수에도 넣을 수 있습니다. 분명 위에서 NULL은 포인터라고 했는데 일반 변수에 들어간다니 조금 의아합니다. 아래에서 확인해 봅시다. #include using namespace std; int main(void) { int a = NULL; // 가능 int* b = NULL; // 가능 cout
[BOJ 16570] 앞뒤가 맞는 수열 KMP 문제 https://www.acmicpc.net/problem/16570 KMP 실패 함수 응용 문제입니다. [문제 풀이] 앞에서부터 수열을 잘라가면서 접두부와 접미부가 일치하는 최대 길이와 그 길이가 가능한 방법의 수를 구하는 문제입니다. 아주 간단하게 생각해보면 수열을 앞에서부터 하나씩 자르면서 자른 수열의 앞뒤가 같은지 비교하고, 앞뒤가 다르다면 제일 앞의 수를 또 자르고 비교(생략)하면 됩니다. 그러나 이렇게 푼다면 앞에서부터 잘린 수열의 개수 N개에 대해 수열의 앞뒤를 비교하게 되는데, 1 1 1 ... 1과 같이 수열의 모든 요소가 같다면 위의 생략 과정이 없어지기에 시간복잡도는 $O(N^2)$이 됩니다. N이 1,000,000이니 당연히 시간 초과입니다. 접두, 접미에 관한 내용이 나..
[자료구조] 트라이 (Trie) 문자열 [자료구조 소개] 문자열을 char단위로 쪼개서 트리에 저장한 자료구조. 문자열 검색에 용이함. [자료구조 특징] 트리 사용. 재귀, 포인터(C++ 사용 시), 트리에 대한 지식 필요 공간, 시간 복잡도를 효율적으로 개선함 (기존의 방식으로 문자열을 찾으려면 문자열 길이 M, 배열 길이 N으로 복잡도가 $O(NM)$, 트라이는 $O(M)$) [코딩 방법] 클래스(구조체) 생성, 현재 노드가 끝인지(문자열이 끝인지) 확인하는 bool타입 변수와 자식노드를 가리킬 객체포인터배열(C++) 혹은 객체배열(Java) 생성. 객체포인터배열은 nullptr(C++) 혹은 null(Java)로 초기화. C++의 경우 동적할당을 사용하므로 자식노드를 삭제할 소멸자도 생성. (!if (child[i]) delete..
[영어 표현] 묘사하다 [describe] 말 혹은 글로 묘사하는 경우 쓰는 표현. ex) The mass media describe Koreans as rushed. => 대중 매체는 한국인들을 성격이 급하다고 묘사한다. [portray] 작가가 그림이나 글로 묘사하는 경우 쓰는 표현 ex) He is portrayed as a devil. => 그는 악마로 묘사된다. [depict] portray와 비슷하나, 영화에서 묘사하는 경우에 쓰는 표현 ex) The movie depicts the inner world of the director. => 그 영화는 감독의 내면세계를 묘사한다. 사실 describe, portray, depict는 차이가 크게 없어서 섞어서 써도 무방하다. 주로 decribe는 글, portray는 ..
[프로그래머스 SQL 고득점 Kit] 중복 제거하기 그룹 함수 문제 https://school.programmers.co.kr/learn/courses/30/lessons/59408 [문제 설명] 주어진 테이블 내에서 NULL을 제외한 동물의 이름이 몇 개인지 출력하는 문제입니다. 단순히 열이 몇 개 인지 구현한다면 COUNT(*)로 끝낼 수 있습니다. 그러나 동물 이름에 대해 중복을 제거하고 COUNT해줘야 하는 문제입니다. 중복을 제거하는 키워드인 DISTINCT를 NAME에 사용하여 중복을 제거하고 COUNT를 하면 해결됩니다. (= COUNT(DISTINCT NAME)) 어려운 문제는 아니지만 헷갈릴만한 부분이 두 가지 있습니다. 첫 번째로는 COUNT(DISTINCT NAME) / DISTINCT COUNT(NAME) 의 차이점입니다. 차근차근 ..
[알고리즘] KMP [알고리즘 소개] 전체 문자열에서 부분 문자열을 효율적으로 찾는 알고리즘. [코딩 방법 - 실패 함수] 실패 테이블 만들기. table[i]는 0부터 i까지에서 접두사, 접미사가 겹치는 최대 길이 부분 문자열 pattern을 1부터 N까지 for문으로 순회, j는 0에서 시작 j > 0 이거나 pattern[i] != pattern[j]이면 j = table[j - 1] 반복 (이전까지 계속 맞았다면 table[j - 1]에는 0이 아닌 값이 들어 있을 것이고 접미사 부분까지 맞았음이 확인됐으므로 처음부터 다시 비교할 필요가 없이 접미사와 같았던 접두사 부분까지는 생략하고 확인 가능) pattern[i] == pattern[j] 이면 table[i] = ++j [코딩 방법 - KMP] 전체 문자열 par..
[Oracle SQL] 1. SELECT 보호되어 있는 글입니다.
[자료구조] 트리, 이진 트리 그래프 이론 트리 [자료구조 소개] 정점이 V개일 때 모든 정점이 연결되어 있고 간선이 V - 1개인 그래프. [자료구조 특징] 순환하지 않는 그래프. [코딩 방법] 일반 양방향 그래프와 동일 [응용] 트리 동적 계획법 트라이 변형된 트리들 (이진 트리 등) 이진 트리 [자료구조 소개] 트리와 같으나, 하나의 루트 노드가 있고 자식 노드가 최대 두 개인 트리. [자료구조 특징] 일반 트리와 동일. 자식 노드가 최대 두 개. [코딩 방법] 자식 노드가 최대 두 개이므로 일반 그래프처럼 코딩할 이유가 없음. 보통 이진 트리를 사용하는 경우에는 루트 노드가 핵심이고 재귀를 사용하는 경우. 크기가 V이고 원소로 크기가 2인 배열을 갖는 2차원 배열을 생성하여 좌우 자식 노드를 저장하면 됨. [응용] 변형된 이진..

티스토리툴바