코딩하는 해달이

학습 목표 ▶ 재귀의 뜻을 이해한다. ▶ 재귀가 사용되는 문제의 예시들을 학습하여 재귀의 원리를 이해한다. ▶ 재귀와 수학적 귀납법 간의 밀접한 관계를 이해한다. # 재귀는 자주 등장하는 주제, 자료구조와 알고리즘을 공부하면서 반드시 알고 있어야 하는 주제 재귀(recursion)란? 내 안의 나를 찾는 것 성격은 같고 크기만 작은 나를 찾아 큰 나와 작은 나가 연결된 관계를 드러내는 것 재귀 함수(recusive function), 재귀 호출(recursive call) 알고리즘이나 함수가 수행 도중에 자기 자신을 다시 호출하여 문제를 해결하는 기법 정의 자체가 순환적으로 되어 있는 경우에 적합한 방법 재귀 알고리즘 자신과 성격은 똑같지만 크기만 작은 알고리즘(들)을 호출하는 알고리즘 복잡한 문제도 간..

알고리즘의 기술 방법 자연어를 이용한 서술적 표현 (영어 or 한국어) 장점 : 대화나 의사소통을 통해서 전달하기 때문에 의사소통만 가능하다면 편하게 전달이 가능함 단점 말하는 사람과 듣는 사람에 따라 다르게 이해할 수 있어 일관성과 명확성이 떨어짐 언어, 단어, 표현등에 의존적임 ex) 배열에서 최대값 찾기 알고리즘 도식화 : 흐름도 (flowchart) 장점 : 간단하고 명확하게 흐름을 표현 가능 단점 : 복잡한 알고리즘을 표현하기에는 어려울 수 있음 ex) 배열에서 최대값 찾기 알고리즘 가상코드를 이용한 추상화 : 의사 코드 (pseudo-code) 장점 의사코드를 실제코드로 변환하기만 하면 되기 때문에 편하게 구현이 가능 알고리즘 기술에 가장 많이 사용 코드지만 프로그래밍 언어에 대한 의존성이 없..

자료구조 데이터를 저장, 조직, 관리하는 방법 문제 해결에 사용할 부품 프로그래밍과 문제 해결 데이터와 구조 모듈에 대한 이해 프로그래밍 언어, 정수, 문자열,.... 리스트, 스택, 큐, 우선순위 큐, 검색트리, 그래프,..... 종류 선형 자료구조 배열 연속적인 메모리에 데이터를 저장하는 자료구조 특징 : 같은 형태의 데이터 집합을 같은 사이즈의 메모리로 나열 연결리스트 데이터를 연결하는 방식으로 저장하는 자료구조 특징 : 한 개의 노드가 데이터부분과 다음 데이터를 가르키는 포인터부분으로 나뉨 행렬 파이썬에서는 이중 리스트로 구현하게 되는 자료구조 특징 : 행과 열로 이루어져있음 스택 특징 : 마지막에 들어온 데이터가 가장 처음으로 나가는(Last In First Out) 구조로 이루어짐 큐 특징 :..

자료구조 수업때 과제를 하며 공부한 기록을 남긴다. [과제 2] 1.1원 다항식을 정의할 수 있다. 다항식의 이름은 x를 제외한 영문 소문자이다(예: f, g등) 2.변수는 항상 x이다. 3.각 항의 지수는 음이 아닌 정수이고, 계수는 정수이다. 4.=,+,-등의 앞뒤로 하나 이상의 공백이 있을 수도 있고 없을 수도 있다. 5. 항들이 반드시 차수에 대한 내림차순으로 입력되는 것은 아니며, 동일 차수의 항이 여럿 있을 수도 있다. 6. 함수는 항상 차수에 대한 내림차순으로 정렬되어 저장되고 출력되어야 한다. 7. 동일 이름의 함수를 새로 정의할 수도 있다. 이 경우 기존의 함수는 지워진다. ========================================================= -다항식의 ..

자료구조 수업때 과제를 하며 공부한 기록을 남긴다. [과제 1] 1.배열 활용하기 공백문자들이 문장의 앞, 중간, 뒤에 포함되어있는 스트링이 입력될 때 스트링의 문자 개 수 를 계산하여 다음과 같이 출력하라. (단, 단어 사이에 두개이상의 연속된 공백 문자들은 하나의 공백 문자로 대체) *출력결과 > hello hello: 5 > welcome to the class welcome to the class: 20 > programming is fun, right? programming is fun, right? 언어는 자신이 원하는 언어로 작성해도 좋습니다. ================================================================================= 나..

연결리스트를 배우면서 연결리스트로 구현한 스택에 대해서도 배워서, 직접 연결리스트로 스택을 구현해보려고 하던 중에 그냥 스택에 대해서도 블로그에 써 놓는게 더 도움이 될 것 같아서 스택부터 정리한 후 아래에 연결리스트로 스택을 구현해 보아야겠다. 스택이란? 스택은 기본적으로 후입선출(Last In First Out)을 기반으로 한 선형 구조이다. 이런 구조는 한쪽 끝에서만 자료의 출입이 이루어지기 때문에 기본적으로 push() 와 pop()연산이 필수적으로 필요하다. 여기서 push()는 '데이터를 밀어 넣는다'는 개념으로 데이터를 추가하는 입력 연산이고, pop()은 자료가 튀어나오는 것을 의미하여 출력 연산을 지칭한다. 그 외에도 조회 연산인 peek가 있는데 이 연산은 가장 마지막으로 들어간 데이터..