본문 바로가기

전체 글203

[C언어와 친구들] 배열 .. 너 .. 포인터랑 뭐 있어? 배열은 C언어가 제공하는 가장 기본적인 자료구조이면서, 몇 없는 ... 그냥 다(?) 없는 C언어의 자료구조 중 하나이다. 배열이란, 컴퓨터 메모리 상에 같은 타입의 변수를 연속적으로 여러 개를 한꺼번에 정의할 수 있는 방법이다. 배열의 장점은 크게 두 가지가 있다. 1) 공간 효율이 좋다. 구조가 단순하기 때문에 정보 자체를 기억하는 메모리 외에 추가로 소모하는 메모리가 전혀 없이 공간효율이 좋다. 정수형 변수 100개를 저장하는 int arr[100] 배열은 정확하게 정수 100개분만큼의 메모리만을 요구한다. 2) 검색 속도가 일정하다. 배열의 크기가 아무리 커지더라도 검색 속도가 일정한다. 배열의 첨자 연산은 포인터를 통해 시작 번지에 첨자 *요소 크기를 더하는 간단한 동작이므로 임의의 한 요소를 .. 2022. 10. 22.
[C언어와 친구들] C언어를 알아볼까 ? 하잇 ~! 1. include와 헤더파일 - 헤더파일이란? C언어의 문법을 가지고 있는 프로그램. - 헤더파일이 코드에 추가되어 있지 않다면, 컴퓨터는 아무것도 하지 못한다. 1-1) #include 이 한 줄의 문장은 'stdio.h'안에 정의되어 있는 많은 함수들을 내 코드안에 포함시켜서 프로그램으로 만들겠다.는 의미 - stdio: standard input output의 약자 (studio가 아니다 🤗) - h: 파일의 확장자, header를 나타냄 1-2) #include - 문자열 변환, 의사 난수 생성, 동적 메모리 관리 등의 함수들을 포함 - 동적 메모리 할당 함수인 mallo, calloc 함수도 이 헤더에 포함되어 있으며, 시스템 명령어나 프로세스 제어함수도 포함 #include // stdio... 2022. 10. 21.
[WEEK03] 개발일지 (부제: set💖과 소소한 행복 찾기) ※ 개발일지가 아니라 일기일 수도 있는 점 양해바랍니다. 오전, 오후, 새벽이 모두 담겨있어요.※ ※ WEEK 시작인 매주 목요일에 업데이트 됩니다. 많.관.부 ※ DAY01 22.10.06 (목) from Jungle import Knowledge 벌써(?) 3주차이다. 사실 일주일 됐을 때 2주를 체감했고, 2주가 됐을 때 4주를 체감했는데 돌이켜보니 일단 했다. 이번 시험은 B반이 먼저 시험을 봤고, 문제는 쿼드트리, PPAP, 소수곱이 나왔다. 저번 주에 색종이 만들기를 공부하면서 힌트에 '쿼드트리를 만드는 문제'라고 해서 '쿼드트리가 뭐냐!!' 하면서 혼자 공부를 했었는데 문제에 나와서 반가웠다. 하지만, 공부를 하지 않았다면 과연 풀 수 있었던 문제일까 생각해보면 잘 모르겠다.. 아직 재귀에 .. 2022. 10. 13.
[알고리즘] 이진 트리, 이진 검색 트리 & 백준(이진 탐색 트리, 트리의 순회) 이진트리(Binary Tree) : 노드가 왼쪽 자식(left chile)과 오른쪽 자식(right child)만 가진다. 자식이 없을 수도 있다. (최대 두 개의 자식 노드를 가지는 트리 형태의 자료구조로서, 단순히 값을 저장하기 위한 용도로 사용되기 보다는 효율적인 탐색 혹은 정렬을 위해 사용된다.) 완전 이진 트리(Complete Binary Tree) - 마지막 레벨을 제외하고, 모든 레벨에 노드가 가득 찬다. - 마지막 레벨은 왼쪽부터 채우고 끝까지 꽉 차지 않아도 된다. - Heap, 우선순위 큐에서 사용하는 트리 구조이다. * 힙(Heap): 최댓값 및 최솟값을 찾아내는 연산을 빠르게 하기 위해 고안된 완전 이진 트리(complete binary tree)를 기본으로 한 자료구조이다. 이진 .. 2022. 10. 12.
[알고리즘] BFS 뿌셔 DFS 뿌셔 BFS - BFS = Breath-First Search - 가까운 노드부터 우선 탐색 : s로부터 거리가 k+1인 한 정점을 만나기 전에, s로부터의 거리가 k인 정점을 모두 발견하는 알고리즘 (CLSR에 적힌 정의) - 큐 자료구조를 이용: 1. 탐색 시작 노드를 큐에 삽입, 방문 처리 => Queue에 들어있는 애들 = frontier 2. 큐에서 노드를 꺼낸 뒤 해당 노드의 인접 노드 중 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리 => frontier 갱신 1) 큐에서 popleft() (popleft()한 값 u / deque이기 때문에 popleft()를 통해서 큐의 맨 앞 요소를 빼줌) 2) u의 인접 노드 v 를 방문했는지 확인 3) 방문 안 했으면 큐에 v 삽입 + v의 dist.. 2022. 10. 10.
[알고리즘] 그래프와 트리, 전위순회, 중위순회, 후위순회& 백준(트리 순회) 그래프 그래프는 현상이나 사물을 정점(Vertex) 또는 노드(Node), 간선(Edge)으로 표현하기 위해 사용한다. - 노드(Node) : 위치를 말함, 정점(Vertex)라고도 함 - 간선(Edge) : 위치 간의 관계를 표시한 선으로 노드를 연결한 선을 뜻함(Link 또는 Branch라고도 함) - 인접 정점(Adjacent Vertext) : 간선으로 직접 연결된 Vertex(또는 Node) 1) 무방향 그래프(undirected graph) - 방향이 없는 그래프로 간선을 통해 노드는 양방향으로 갈 수 있음 - 보통 노드 A,B가 연결되어 있을 경우 (A,B) 또는 (B,A)로 표기 2) 방향 그래프(directed graph) - 간선에 방향이 있는 그래프로 방향이 가르키는 곳으로만 갈 수 .. 2022. 10. 8.
[알고리즘] 스택 & 백준(탑, PPAP) * Deque을 활용하여 스택을 구현하는게 더 효율적이다. [파이썬/Python] Collections - Deque 들어가며 코딩테스트에 응시할 때 빠르게 찾아볼 수 있도록 따로 정리한 내용입니다. 공부하시기에는 빈약한 내용일 수 있음을 미리 알려드립니다. 공식 문서를 참고할 때에는 대부분의 기업이 mong9data.tistory.com 1. 2493: 탑 문제 실험을 위하여 일직선 위에 N개의 높이가 서로 다른 탑을 수평 직선의 왼쪽부터 오른쪽 방향으로 차례로 세우고, 각 탑의 꼭대기에 레이저 송신기를 설치하였다. 모든 탑의 레이저 송신기는 레이저 신호를 지표면과 평행하게 수평 직선의 왼쪽 방향으로 발사하고, 탑의 기둥 모두에는 레이저 신호를 수신하는 장치가 설치되어 있다. 하나의 탑에서 발사된 레이.. 2022. 10. 8.
[Python] 노드(Node) - 자료구조 기본 단위 노드 관리할 데이터를 보관(존재)하는 곳을 노드(Node)라고 한다. 즉, 자료구조에서 관리하고 있는 정보들 중 하나를 저장하고 있는 단위이다. 주로 연결 리스트라고 불리는 링크드 리스트에서 사용되며 연결리스트에서 노드는 데이터 값 + 포인터로 구성되어 있다. 대체로 자료구조를 공부할 때 이 노드를 클래스로 직접 구현한다. 하지만 자료구조에서 구조적 설계보다 연산(메소드)이나 연산으로 인한 구조적 변화에 학습을 집중해야될 때는 노드를 따로 구현하지 않는다. 이 경우 기본적으로 제공하는 자료형(대표적으로 리스트)으로 주로 진행한다. 즉, 구조적 설계를 필요로 할 때 노드를 클래스로 직접 구현한다. 2022. 10. 7.
[Python] 가장 파이썬스러운 enumerate 활용법 문제의 출력 조건이 정답 조건에 해당하는 원소의 인덱스를 출력하는 것이었는데 enumerate를 활용하여 인덱스를 추출하는 과정을 돌아가지 않고 바로 뽑을 수 있다는 것을 알게 되었다. 일반 for문을 사용하는 것이 가장 파이썬스럽지 않은 방법이라고 한다. ^^ enumerate 함수를 이용하면 출력형식이 무조건 tuple 형식으로 나오기 때문에 인덱스 값만 빼오고 싶거나, 원소값만 빼오고 싶은 경우 위와 같은 두 방식을 이용하여 추출할 수 있다. abc = ['A', 'B', 'C'] # 일반 for문: for 원소 in 목록: # 목록 => 리스트, 튜플, 문자열, 반복자 등 순서가 있는 모든 데이터 타입 for letter in abc: print(letter) # 일반 for문: 리스트의 인덱스와.. 2022. 10. 6.
[Python] 리스트를 join 함수 활용하여 문자열로 만들기 리스트에 있는 특정 str 값들을 뽑아서 어떤 단어이다! 라고 설명하고 싶은데 구현이 안 되는 부분이 있었다. join() 함수를 사용하여 리스트 내의 원소들을 문자열로 합쳐줄 수 있다. join() 함수는 기준을 가지고 문자열로 엮는데 위 사진에서는 공백을 활용하여 문자열을 붙이게끔 만들어주었다. 또한, join() 함수 안에 들어갈 해당 리스트를 넣는데 stack[-4:]를 넣어줬기 때문에 뒤에서 4번째까지의 원소를 의미한다. 뒤에서 네번째까지의 원소를 문자열로 출력하게 되면 PPAP가 나오는 것을 확인할 수 있다. stack = ['P', 'P', 'A', 'P', 'P', 'A', 'P'] print("스택 뒤에서 4번째 원소: ", stack[-4]) print("스택 뒤쪽의 4개 원소: ", .. 2022. 10. 6.
[알고리즘] 이분 탐색, 투 포인터 알고리즘 & 백준(두 수의 합, 두 용액) 이분탐색에 문제를 풀다가 두 용액이라는 문제가 나왔고, start, end, mid를 놓고 계속 풀었기 때문에 mid값을 어떻게 설정해야하는지에 대한 어려움이 있었다. 두 용액 문제의 알고리즘 분류를 보니 두 포인터(- 투 포인터)가 있어서 이를 활용해야함을 알았다. 이분 탐색이란? 정렬된 배열에서 target의 존재 여부와 위치를 알려준다. 재귀적으로 탐색 범위를 반으로 줄여, 시간복잡도를 O(logN)까지 줄일 수 있다. 투 포인터 알고리즘이란? 포인터가 C언어에서의 포인터가 아니다. 정말 말그대로 가리키는 두 개의 포인터라고 생각하면 된다. 이름처럼 양 끝을 각각 포인터로 설정한 다음, 포인터의 위치를 안쪽으로 옮기며 주어진 연산을 반복해 최적값을 찾아내는 방식이다. 투포인터 알고리즘의 장점은 리스.. 2022. 10. 6.
[알고리즘] 이분 탐색, 매개 변수 탐색 & 백준(랜선 자르기, 나무 자르기, 공유기 설치, 히오스 프로게이머) 이분 탐색이란? 정렬된 배열에서 target의 존재 여부와 위치를 알려준다. 재귀적으로 탐색 범위를 반으로 줄여, 시간복잡도를 O(logN)까지 줄일 수 있다. 매개 변수 탐색(Parametric Search)란? 이분 탐색과 유사하다. 탐색 범위를 반으로 줄이기 때문에 시간복잡도는 O(logN)이다. 최적화 문제를 결정 문제로 바꾸어 풀 때 사용한다. - 최적화 문제: 어떤 알고리즘의 최적 솔루션을 찾는 것 - 결정 문제: 답이 이미 결정되어 있다고 보고 문제를 푸는 것 이진 탐색과 매개변수 탐색의 차이점 이진 탐색은 배열에서 target과 일치하는 값을 찾으면 바로 함수를 종료하지만, 매개변수 탐색은 함수를 종료하지 않고 모든 배열을 살펴본다. 따라서, 매개변수 탐색은 어떤 조건을 만족하는 위치 중 .. 2022. 10. 6.

티스토리툴바