본문 바로가기

전체 글

 (94)
[자료구조] 덱(Deque)의 개념과 연결 리스트로 구현(C언어) INDEX 1. 덱의 개념 2. 덱의 ADT를 구성하는 함수 3. 구현 3-1. 노드와 덱 구조체 3-2. 덱의 초기화와 비어 있는지 확인 3-3. 덱의 Front삽입과 Rear삽입 3-4. 덱의 Front추출과 Rear추출 1. 덱의 개념 덱은 아래의 그림처럼 직관적으로 이해하는 것이 가장 편하다. 스택이 입구와 출구가 1개뿐이었고 큐가 입구와 출구가 구별되는 일방향 통로의 느낌이었다면 덱은 큐의 업그레이드 버전인 양방향 이동 통로라고 이해할 수 있다. 그만큼 큐보다 개념적인 것들이 더 등장하게 된다. 덱에서 정보의 접근과 저장은 오직 Front와 Rear에서만 가능하다. 즉 큐보다 데이터 접근성이 더 좋아진 것이다. 덱의 Front에서 시작해서 Rear까지 이동할 수 있고 그 반대도 마찬가지로 가능하..
[머신러닝] 파이썬으로 선형회귀 BGD, SGD, MSGD 구현 + 실습(광고에 의한 수익 예측) 선형 회귀에서는 경사하강법을 이용해서 파라미터를 찾는다. 하지만 파라미터를 찾기 위해서는 경사하강법에 의거한 다량의 행렬 연산을 수행해야 한다. 행렬 연산의 크기에 따라 크게 3개의 모델로 나뉜다. BGD : 전체 데이터 셋을 연산에 포함 SGD : 데이터 하나만 연산에 포함 MSGD : 전체 데이터 셋을 mini batch로 쪼개고 거기에서 랜덤으로 뽑아 연산 선형 회귀에 대한 개념은 여기에 있다. 여기서 해볼 실습은 kaggle에 있는 Advertising data를 이용해서 광고와 수익 사이의 관계를 예측하는 모델을 만들어볼 것이다. 데이터 셋은 바로 아래에 있다. 의문이 들 수 있는 점이 어차피 여기서 구현하고자 하는 모델 3개는 이미 지원해주고 있는 클래스여서 굳이 스스로 구현할 필요가 있을까?..
[머신러닝] 선형 회귀(Linear Regression)의 이해 INDEX 1. 선형 회귀란 2. 수학적 표현 3. 경사하강법(Gradient Descent) 4. 배치 경사하강법(Batch Gradient Descent) 5. 확률적 경사하강법(Stochastic Gradient Descent) 6. 미니 배치 경사하강법(Mini Batch Gradient Descent) 7. 일반화 식(normal equation) 1. 선형 회귀란 인공지능 분야에서의 출발점이자 기초 모델 중 하나인 모델 선형 회귀(Linear Regression) 모델이다. 이름에 적혀있는 그대로 데이터 간의 선형적인 관계를 이용하자는 목적이 담겨있는 모델이다. 정확히 말하자면 선형 회귀는 한 개의 종속 변수(y)와 한 개 이상의 독립 변수(x)와의 선형 관계를 모델링하는 기법이다. 대표적인 ..
[백준]_1991번 : 트리 순회(C언어) 1991번: 트리 순회 첫째 줄에는 이진 트리의 노드의 개수 N(1 ≤ N ≤ 26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 알파 www.acmicpc.net 입력으로 노드들이 부모, 왼쪽 자식, 오른쪽 자식 순서로 주어지고 이렇게 완성된 트리에서 전위 순회, 중위 순회, 후위 순회를 해서 노드에 저장된 값들을 순회별로 출력하면 되는 문제이다. 전략 먼저 입력 방식을 정의해 보자. 부모 노드는 반드시 입력되고 존재하지 않는 자식 노드는 '.'으로 대체된다. 즉 일단 크기가 6인(최대 입력이 5개까지인데 크기가 6인 이유는 배열의 마지막에 널 문자('\0')를 저장해야 되기 때문) 배열로 문자열을 받은 다음에..
[자료구조] 스택을 활용해서 두 자리 수 이상의 연산이 가능한 계산기 만들기(C언어) 스택으로 계산기를 구현하려면 아래와 같은 과정을 거쳐야 한다. 중위 표기법을 모두 후위 표기법으로 바꾼다. 후위 표기법으로 바뀐 식을 스택에 넣어준다. 스택에 있는 값들을 특정 규칙에 따라 연산한다. 중위 표기법과 후위 표기법에 대한 내용은 위키 문서를 참조하기를 바란다. 이해를 돕기 위해서 후위 표기법을 가장 잘 설명한 블로그 주소도 남긴다. 주로 스택은 구제체 안에 배열을 선언한 상태로 사용한다. 아래는 스택을 구성하는 여러 기능들을 구현해 보았다. 이들 모두 계산기 구현에 중요한 역할을 하기 때문에 반드시 알고 넘어가야 한다. #include #include #include #define MAX_LEN 100 typedef struct Stack { // 스택 구조체 int data[MAX_LEN]..
[백준]_2568번 : 전깃줄 - 2(파이썬) 2568번: 전깃줄 - 2 첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100,000 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결 www.acmicpc.net 일단 아이디어 자체는 전깃줄과 다를 바가 없다. 꼬인 전깃줄을 꼬이지 않게 하기 위해서는 전깃줄을 하나의 쌍(예를 들어 [1, 8])으로 묶은 다음에 첫 번째 요소에 대해 정렬을 진행한 다음에 두 번째 요소의 LIS(최장 부분 수열)를 구하면 된다. 애초에 전깃줄의 꼬임이 왜 발생하는지에 대해 생각해 보면 이해하기 수월해진다. 전깃줄은 다음과 같은 조건을 만족시킬 때 꼬인다. 왼쪽 전봇대의 전깃줄을 a1, b1 이라고 하고 그에 대응하는(이어져 있는) 오른쪽..
[자료구조] 연결 리스트(C언어) 연결 리스트(Linkedlist) 연결 리스트란 노드가 연결되어 있는 자료구조이다. 이때 노드는 노드만의 데이터와 포인터를 갖고 있다. 여기서 데이터는 우리가 저장하고자 하는 대상이 될 수도 있다, 예를 들면 수열, 등수에 따른 시험 점수 등이 될 수 있다. 즉 관리되는 데이터를 표현하는 것이 노드의 데이터 부분이다. 노드의 포인터는 사실 연결 리스트를 연결 리스트로 만들어주는 가장 중요한 특성이다. 포인터는 다음 노드 또는 이전 노드와의 연결을 담당한다. 즉 데이터 관리를 위한 포인터인 것이다. 우리가 알고 있는 일반적인 배열과는 다르게 데이터의 추가와 삭제가 어느 지점에서도 O(1)만에 가능하다는 장점이 있다. 하지만 단점으로는 데이터로의 임의적 접근이 상당히 제한된다는 점이다. 왜냐하면 초기 데이터..
[백준]_2239번, 2580번 : 스도쿠(파이썬) # 입력 부분 import sys input = sys.stdin.readline tmp=[input().strip() for _ in range(9)] board=[[0]*9 for _ in range(9)] for r in range(9): for c in range(9): board[r][c]=int(tmp[r][c]) # 출력 부분 for r in range(9): for c in range(9): print(board[r][c], end='') print()​ 2580번: 스도쿠 스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루 www.acmicpc..

티스토리툴바