//공부 기록용 포스팅입니다. 틀린 부분이 있을 경우 댓글로 알려주시면 감사합니다! 😎 1. 연결 리스트의 맨 앞에 새로운 노드 삽입하기 새로운 노드를 만들고 → 추가할 데이터를 저장 배열) 공간을 미리 잡아두고 데이터를 수시로 채움 연결 리스트) 필요할 때마다 동적 할당으로 노드를 생성 ~ 노드의 개수 = 데이터의 개수 새로운 노드의 next 필드가 현재 head 노드가 가리키는 노드를 가리키도록 한다. 현재의 head 노드가 가리키는 노드의 주소는 head 노드에 저장되어 있다. head노드는 첫 번째 노드를 가리킴 새로 생성한 노드를 새로운 head 노드로 한다 이 과정을 앞선 과정보다 먼저하면 원래 가리키고 있었던 첫 번째 노드의 주소를 분실하기 때문에 순서에 유의 #include #include..

//공부 기록용 포스팅입니다. 틀린 부분이 있을 경우 댓글로 알려주시면 감사합니다! 😎 1. 연결 리스트 예제프로그램 연결 리스트는 노드 10개를 미리 만들어두고 사용하지 않고 필요한 그때그때마다 노드를 만들어서 연결 리스트에 추가한다. 연결 리스트 예제프로그램 목표 struct node{ char * data; struct node * next; }; typedef struct node Node; Node *head = NULL; 1-1. 2nd int main(){ //어떤 구조체를 가리키는 포인터 head Node *head = (Node *)malloc(sizeof(Node)); //head가 가리키는 구조체 안의 data 멤버를 엑세스할 때 화살표 연산자를 쓴다. //head->data = "2..

//공부 기록용 포스팅입니다. 틀린 부분이 있을 경우 댓글로 알려주시면 감사합니다! 😎 1. 리스트(List) List: 리스트: 원소들 간의 순서 개념 O ex) (1, 2, 3) ≠ (3, 2, 1) Set: 집합: 원소드 간의 순서 개념 X ex) {1, 2, 3} == {3, 2, 1} 리스트: 하나가 아닌 여러 개가 쭉 일렬로 나열되어 있는 것 기본적인 연산: 삽입(insert), 삭제(remove), 검색(search) 리스트를 구현하는 대표적인 두 가지 방법 - 배열, 연결 리스트 배열 장점) 랜덤 액세스가 가능한 자료구조 배열의 이름은 포인터 변수이고, 이 포인터 변수는 배열의 시작 주소를 가지고 있다. 배열의 각 칸은 동일한 타입이다 → 배열의 각 칸은 크기가 동일하다. 배열의 각각의 항..

일직선상에 있는 좌표 1 (x1, y1)과 좌표 2 (x2, y2)의 x 간의 거리와 y 간의 거리가 같다면 두 좌표는 같은 대각선 위에 위치한다. x 간의 거리와 y 간의 거리가 같다면 => |x1 - x2| == |y1 - y2|

백트레킹 진행 과정에서 답이 아닌 분기를 만나면 탐색을 진행하지 않고 돌아가 다른 분기로 감으로써 가지치기를 한다는 차이가 있다. 조건에 맞지 않는 분기에서 가지 치기를 하고, 부모 노드로 돌아가 다른 자식을 검색한다 First In Last Out을 하는 Stack과 재귀를 사용해서 구현할 수 있다. 모든 요소를 포함하고 있는 그래프에서 조건에 맞게 분기를 할지 말지 결정하는 것이 아니라 그래프(혹은 배열)에 바로바로 추가할지 말지를 결정해야 하는 문제이다. 또한 조건을 만족하는 답을 찾아서 끝내는 것이 아니라 재사용을 위해서 마지막 요소를 popLast() 하고 부모 노드로 돌아가서 재귀를 이용해야 한다. [popLast()와 removeLast()] - 둘 다 배열의 마지막 요소를 제거하지만 pop..

//공부 기록용 포스팅입니다. 틀린 부분이 있을 경우 댓글로 알려주시면 감사합니다! 😎 1. 깊이 우선 탐색(DFS: Depth-First-Search) 그래프 완전 탐색 재귀함수로 구현 스택 자료구조 이용 깊이 우선 탐색은 그래프 완전 탐색 기법 중 하나 그래프의 시작 노드에서 출발하여 탐색할 한쪽 분기를 정하여 최대 깊이까지 탐색을 마친 후 다른 쪽 분기로 이동하여 다시 탐색 수행 ⇒ 자식 노드부터 탐색 재귀 함수로 구현, 스택 자료구조를 이용 처음 탐색 노드의 어떤 인접 노드부터 탐색할지에 대한 순서는 상관없음 [깊이 우선 탐색의 원리] 한 번 방문한 노드를 다시 방문하면 안 된다. 노드 방문 여부를 체크할 배열이 필요하다. 그래프를 인접 리스트로 표현 DFS는 후입 선출의 특성을 가짐 → 스택 o..

//공부 기록용 포스팅입니다. 틀린 부분이 있을 경우 댓글로 알려주시면 감사합니다! 😎 자료구조 1강 메모리 모든 변수는 주소를 가진다. 포인터 포인터는 메모리 주소를 값으로 가지는 변수이다. type-name * variable-name; variable-name은 선언된 포인터 변수의 이름 *는 포인터 변수임을 표시하는 기호 type-name은 * variable-name이 저장하는 메모리 주소에 저장된 값의 데이터 타입 & 연산자: 엠퍼센트 연산자 &(엠퍼센트)는 변수로부터 그 변수의 주소를 추출하는 연산자 int a = 100; int *ptr = &a; //ptr = 변수 a의 주소 값 ptr은 주소값을 저장 → *ptr은 ptr(주소값) 가리키는 값 ptr은 a의 주소 값을 저장 → *ptr은..

//공부 기록용 포스팅입니다. 틀린 부분이 있을 경우 댓글로 알려주시면 감사합니다! 😎 구조체에 대한 포인터, 동적 메모리 할당 구조체의 배열 → 구조체 포인터의 배열 1. C언어에서의 매개 변수 전달 방식 typedef struct person{ char * name, number, email, group; } Person; //Person 타입의 디렉토리 배열 선언 Person directory[CAPACITY]; C언어에서 구조체의 배열은 일반적인 방법이 아니다. void status(){ int i; for(i=0;i=0 && strcmp(directory[i].name, name)>0){ //구조체 이기 때문에 name, number 배열을 따로 이동할 필요 없이 한 번에 이동 directory..

스위프트의 경우 pascal(n: n-1, k: k-1) + pascal(n: n-1, k: k)를 DP를 이용해서 풀면 시간초과의 문제가 생긴다. -> 시간초과를 해결하기 위해서는 2차원 배열에 값들을 저장해서 c[n-1][k-1] + c[n-1][k]를 계산해서 문제를 풀 수 있다. 1. 먼저 이항계수의 성질은 nCk = n-1Ck-1 + n-1Ck 2. nC0 = 1, nCn = 1 을 사용해서 문제를 풀 수 있다. 위의 2가지를 사용한다면 풀 수 있는 문제이지만, 한 번에 풀지 못해 다른 블로그를 참고했을 때 이해 되지 않던 점을 정리해보았다. 1. 범위를 k가 n을 초과할 수 없는 이유 - 이항계수 값을 저장할 배열은 [N+1][N+1]개의 사각형 형태의 이차원 배열로 저장했지만 당연히 이항계수..

주어진 수의 최대공약수의 약수를 구하는 문제이다. - 주어진 수의 규칙을 찾아내는 것이 중요하다. - 나머지(r)가 모두 같게 되는 M을 구하는 문제 1. 모든 수에서 r을 빼면 M으로 나눠진다. 2. 가장 큰 M을 구하고(최대공약수), M의 약수를 구하면 된다. - 사실 이 문제를 풀면서 런타임 에러가 많이 발생했는데 이유를 찾을 수 있었다. - 차(gap: input[1] - input [0])를 새로운 정렬에 저장해서 gcf를 구했는데, 이때 변수의 범위를 잘 못 지정해서 런타임 에러가 발생했다. for i in 1..

최대공약수와 최소공배수를 구하는 문제에서는 최대공약수만 안다면 최소공배수는 쉽게 구할 수 있다. 1. 최대 공약수를 부르트포스 처럼 모든 수로 나누는 방법을 생각했지만 유클리드 호제법이라는 알고리즘이 있었다. 유클리드 호제법 또는 유클리드 알고리즘은 2개의 자연수 또는 정식(整式)의 최대공약수를 구하는 알고리즘의 하나이다. 호제법이란 말은 두 수가 서로(互) 상대방 수를 나누어(除)서 결국 원하는 수를 얻는 알고리즘을 나타낸다. 2개의 자연수(또는 정식) a, b에 대해서 a를 b로 나눈 나머지를 r이라 하면(단, a>b), a와 b의 최대공약수는 b와 r의 최대공약수와 같다. 이 성질에 따라, b를 r로 나눈 나머지 r'를 구하고, 다시 r을 r'로 나눈 나머지를 구하는 과정을 반복하여 나머지가 0이 ..

방정식도 없이 경로를 구하라고? - 그렇다. 내 맘대로 하면 되는 문제지만 사실 경로가 필요 없는 문제다. - 주어진 입력을 좌표상에 그려보고 규칙을 찾을 수 있었다. - 1. 출발과 도착지점이 원의 안에 있는지 밖에 있는지가 이 문제를 해결하는 방법이다. 1 - 1. 출발과 도착지점이 원의 안에 있다면 원의 경계를 지나지 않고는 이동할 수 없기 때문에 카운트 +1 (= 보라색 점) 1 - 2. 출발과 도착지점이 원의 밖에 있다면 해당 원은 무시해도 된다. (= 초록색 해당 없음) - 2. 여기서 주의할 점은 주황색 원이다. 2 - 1. 출발과 도착지점 둘 다 주황색 원 안에 위치해 있다. 2 - 2. 이 경우는 주황색 원을 지날 필요가 없기 때문에 카운트하지 않고 무시한다. (= 주황색 해당 없음) -..