분류 전체보기
-
[C언어] 문자열 비교 strcmp,strncmpC \ C++ 2021. 1. 26. 17:21
strcmp 두 문자열이 같으면 0을, 같지 않으면 0이 아닌 값을 반환한다. strncmp 두 문자열의 원하는 길이만큼 같으면 0, 같지 않으면 0이 아닌값 반환한다. //헤더파일 //c: //c++ : int strcmp(const char* str1, const char* str2) //str1, str2 : 비교할 문자열 1 ,2 int strncmp(const char* str1, const char* str2, size_t n); //str1 , str2, n : 비교할 문자열 1, 2, 비교할 문자열 길이 strcmp, strncmp 는 각각 아스키 코드 값으로 비교를 하고, 아스키 코드를 사용 하므로 대소문자 구별이 가능하다 그리고 0혹은 양수 음수를 반환 하는데 그 경우는 * 첫번째 인자..
-
[프로그래머스] 완주하지 못한 선수알고리즘 & 자료구조/코딩테스트 2021. 1. 25. 22:53
문제 설명 수많은 마라톤 선수들이 마라톤에 참여하였습니다. 단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였습니다. 마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수들의 이름이 담긴 배열 completion이 주어질 때, 완주하지 못한 선수의 이름을 return 하도록 solution 함수를 작성해주세요. 제한사항 마라톤 경기에 참여한 선수의 수는 1명 이상 100,000명 이하입니다. completion의 길이는 participant의 길이보다 1 작습니다. 참가자의 이름은 1개 이상 20개 이하의 알파벳 소문자로 이루어져 있습니다. 참가자 중에는 동명이인이 있을 수 있습니다. 입출력 예 participant completion return [leo, kiki, ..
-
[baekjoon] 10872번 팩토리얼 (재귀)알고리즘 & 자료구조/코딩테스트 2021. 1. 25. 19:13
문제 0보다 크거나 같은 정수 N이 주어진다. 이때, N!을 출력하는 프로그램을 작성하시오. 입력 첫째 줄에 정수 N(0 ≤ N ≤ 12)가 주어진다. 출력 첫째 줄에 N!을 출력한다. 예제 입력 1 복사 10 예제 출력 1 복사 3628800 예제 입력 2 복사 0 예제 출력 2 복사 1 필요한 개념 팩토리얼 : 서로 다른 n개를 나열하는 경우의 수를 의미, 기호로는 n! 계산은.. n! = n(n-1)(n-2)(n-3)...1 1이 될때 까지 모든수를 곱해준다. ※ 0! 은 1 이다 ex) 4! = 4 x 3 x 2 x 1 = 4 x (4-1)! = 4 x 3! 따라서 1! = 1 x (1-1)! 1! = 1 x 0! =>> 1 = 1 x 0! 이므로 0!은 1 이 된다. * a! = (a-1)! ..
-
[Data Structure] 스택, 큐, 딕셔너리알고리즘 & 자료구조 2021. 1. 25. 16:49
큐 큐는 값이 아래로 쌓이는 구조이다. 값을 넣고 뺄 때 '선입선출' 또는 'FIFO' 라는 방식을 따르게 된다. 가장 먼저 들어온 값이 가장 먼저 나가는 것이다. 식당에서 주문을 하기 위해 줄을 설때 가장 먼저 줄을 선 사람이 가장 먼저 주문을 하는것 과 동일하다. 배열이나 연결리스트를 통해 구현 가능하다. ***예제 소스코드 바로가기 ====>>> junecode.tistory.com/49 [baekjoon] 10828번 스택 (스택) 문제 정수를 저장하는 스택을 구현한 다음, 입력으로 주어지는 명령을 처리하는 프로그램을 작성하시오. 명령은 총 다섯 가지이다. push X: 정수 X를 스택에 넣는 연산이다. pop: 스택에서 가장 위 junecode.tistory.com 스택 반면 스택은 값이 위로 ..
-
[Data Structure] 트라이알고리즘 & 자료구조 2021. 1. 25. 16:32
'트라이'는 기본적으로 ' 트리' 형태의 자료 구조이다. 특이한 점은 각 노드가 '배열'로 이루어져 있다는 것이다. 예를 들어 영어 알파벳으로 이루어진 문자열 값을 저장 한다고 하면 이 노드는 a부터 z까지의 값을 가지는 배열이 된다. 그리고 배열의 각 요소, 즉 알파벳은 다음 층의 노드(a-z배열)를 가리킨다. 아래 그림과 같이 Hermione, Harry, Hagrid 세 문자열을 트라이에 저장해보자 루트 노드를 시작으로 각 화살표가 가리키는 알파벳을 따라가면서 노드를 이어주면 된다. 단순히 문자열의 각 문자를 보며 트리를 탐색해나가기만 하면 되기때문에, 위와 같은 트라이에서 값을 검색하는데 걸리는 시간은 '문자열의 길이'에 의해 한정된다. 일반적인 영어 이름의 길이를 n이라고 할때, 검색 시간은 O..
-
[Data Structure] 해시 테이블알고리즘 & 자료구조 2021. 1. 25. 16:13
해시 테이블은 '연결 리스트의 배열' 이다. 여러 값들을 몇 개의 바구니에 나눠 담는 상황을 생각해보자 각 값들은 '해시 함수' 라는 맞춤형 함수를 통해서 어떤 바구니에 담기는 지가 결정된다. 각 바구니에 담기는 값들은 그 바구니에서 새롭게 정의되는 연결리스트로 이어진다. 이와 같이 연결 리스트가 담긴 바구니가 여러개 있는 것이 '연결 리스트의 배열' , 즉 '해시 테이블' 이 된다. 쉬운 예로 아래 그림과 같이 사람의 이름이 해시 테이블에 저장되며, 해시 함수는 ' 이름의 가장 첫 글자' 인 경우를 생각해보자 그 경우 알파벳 개수에 해당하는 총 26개의 포인터들이 있을 수 있으며. 각 포인터는 그 알파벳을 시작하는 이름들을 저장하는 연결 리스트를 가리키게 된다. 만약 해시 함수가 이상적이라면, 각 바구..
-
[Data Structure] 연결 리스트 : 트리알고리즘 & 자료구조 2021. 1. 25. 14:15
트리는 연결리스트를 기반으로 한 새로운 데이터 구조다. 연결 리스트에서 각 노드들의 연결이 1차원적으로 구성되어 있다면, 트리에서의 노드들의 연결은 2차원적으로 구성되어있다고 볼 수 있다. 각 노드는 일정한 층에 속하고, 다음 층의 노드들을 가리키는 포인터를 가지게 된다. 가장 높은 층에서 트리가 시작되는 노드를 '루트' 라고 한다. 루트 노드는 다음 층의 노드들을 가리키고 있고, 이를 '자식 노드' 라고 한다. 위의 그림을 살펴보자, 뭔가 규칙을 찾았는가? 왼쪽이 자식 노드는 자신의 값보다 작고 오른쪽 자식 노드는 자신의 값보다 크다. 따라서 이런 트리 구조는 이진 검색을 수행하는데 유리하다. #include #include //이진 검색 트리의 노드 구조체 typedef struct node { //..
-
[Data Structure]연결 리스트 : 코딩알고리즘 & 자료구조 2021. 1. 24. 23:11
#include #include //연결 리스트의 기본 단위가 되는 node 구조체를 정의 typedef struct node { //node 안에서 정수형 값이 저장되는 변수를 name으로 지정 int number; //다음 node의 주소를 가리키는 포인터를 *next로 지정. struct node *next; }node; int main(void) { //list라는 이름의 node 포인터를 정의한다. 연결 리스트의 가장 첫번째 node를 가리킬 것이다 //이 포인터는 현재 아무것도 가리키고 있지 않아서 NULL로 초기화한다 node *list = NULL; //새로운 node를 위해 메모리를 할당하고 포인터 *n으로 가리킴 node *n = malloc(sizeof(node)); if(n == N..
-
[Data Structure]연결 리스트 : 도입알고리즘 & 자료구조 2021. 1. 24. 16:37
배열에서는 각 인덱스의 값이 메모리 상에서 연이어 저장 되어 있다. 하지만 꼭 그럴필요가 있을까? 각 값이 메모리상의 여러군데 퍼져 있다고 해도 메모리 주소만 기억하고 있다면 여전히 값을 연이어서 읽어들일 수 있을것이다. 이를 '연결 리스트' 라고 한다. 위의 그림과 같이 크기가 3인 연결 리스트는 각 인덱스의 메모리 주소에서 자신의 값과 함께 바로 다음값의 주소 (포인터)를 저장한다. 3은 다음값이 없기에 NULL을 다음 값의 주소로 저장한다. 연결 리스트를 사용하기 위해서는 아래 코드와 같이 간단한 구조체로 정의할 수 있다. //typedef struct 대신에 typedef stuct node 라고 'node'를 함께 명시해 주는 것은, //구조체 안에서 node를 사용하기 위함이다. typedef..
-
[Data Structure] 배열의 크기 조정하기알고리즘 & 자료구조 2021. 1. 24. 16:03
소스 코드를 보기전에 먼저 생각해보자 우리가 이미 일정한 크기의 배열을 선언 했다면, 그 크기를 키우려면 어떻게 해야할까? list[0] = 1; list[1] = 2; list[2] = 3; 밑에 표를 메모리라 생각해보자 list[3] 에 4를 저장하고 싶지만 h라는 값이 메모리에 담겨있다. e m m a 1 2 3 h e l l o 단순히 메모리의 위치 바로옆에 일정 크기의 메모리를 덧붙일수 없다. 따라서 안전하게 새로운 공간에 큰 크기의 메모리를 다시 할당하고 기존 배열의 값들을 하나씩 옮겨줘야 한다. 이러한 작업은 O(n), 즉 배열의 크기 n만큼의 실행 시간이 소요될것이다. 이 과정을 코드로 나타내면 아래와 같다. #include #include int main(void) { //첫번째 방법 /..