포시코딩

재귀 함수 재귀란? 재귀(Recursion)은 자신을 정의할 때 자기 자신을 재참조하는 방법을 말한다. 더 나아가 재귀함수란 정의 단계에서 자신을 재참조하는 함수를 뜻한다는걸 알 수 있다. 어디에 쓸까? 60초부터 0초까지 -1을 하며 print()를 해야할 때와 같은 상황에서 간결하고 효율성 있는 코드를 작성할 때 사용한다. 아래의 예시 코드를 보자 #def count_down(number): # print(number) # count_down(number - 1) # #count_down(60) # 이대로 실행하면 무한히 -1이 되어 Recursion Error를 내게 되므로 아래처럼 탈출 조건을 만들어야 한다. def count_down2(number): if number < 0: return pr..

2진 탐색 인덱스가 0부터 16까지 있는 array가 있을 때 그 중 정답이 target인 값을 찾으려면 어떻게 해야할까? for문을 통해 처음부터 하나씩 비교하는 방법이 있겠지만 맨 마지막에 정답이 있으면 O(N) 만큼의 시간 복잡도가 걸리게 될 것이다. 이 때, 2진 탐색이라는 방법을 통해 시도 횟수를 확 낮출 수 있다. 딱 가운데 위치하는 값을 정답과 비교해서 정답이 더 크다면 가운데 위치하는 값 이하의 인덱스를 모두 버리고 정답이 더 작다면 가운데 위치하는 값 이상의 인덱스를 모두 버리는 식으로 구하며 이를 반복하면 된다. 이는 알고리즘 문제에서 UP & DOWN 문제로도 자주 나오는 형태이다. 문제풀이 예시 시간 복잡도 O(log N) 총 숫자가 1 ~ N 까지라고 한다면 1번 탐색하면 반절이 ..

맨 뒤에 노드 추가하기 class Node: def __init__(self, data): self.data = data self.next = None class LinkedList: def __init__(self, value): self.head = Node(value) 저번 포스팅에서 LinkedList를 위해 위와 같은 클래스를 만드는 것 까지 했다. 이번에는 LinkedList의 맨 뒤에 새로운 Node를 붙이는 append 함수를 만들어보자 how? 현재 있는 노드의 가장 맨 뒤에 새로운 값을 가진 노드를 추가하면 된다. 끝 말로는 쉽지만 그러기 위해선 먼저 가장 맨 뒤의 노드까지 이동해야 한다. head [3] -> [5] -> [7] head를 변경시킬 수는 없으니 cur = self.he..

js 또는 java에서의 class에 대한 기초 지식이 있다는 가정하에 작성된 글입니다. class in Python 파이썬에서는 생성자 함수의 이름이 __init__ 으로 고정되어 있다. 생성 시 생기는 self는 객체 자기 자신을 가리킨다. 파라미터를 따로 넣을 필요 없이 알아서 넣어줌 class Person: def __init__(self): print('hi') person = Person()# hi가 출력됨 추가로 아래처럼 self를 사용해서 객체에 데이터를 쌓을 수 있다. class Person: def __init__(self, param_name): self.name = param_name 메소드를 추가할 때도 self가 자동으로 붙는데 만들어보면 다음과 같다. class Person: ..

개요 들어가기에 앞서, 자료구조를 왜 배워야할까? 특정 자료구조는 삽입/삭제가 빠르고 특정 자료구조는 조회가 빠르다. 이처럼, 어떤 경우에는 이 자료구조가 좋고, 어떤 경우에는 저 자료구조가 좋은 것 처럼 경우에 따라 다양한 자료구조와 알고리즘을 사용해야 한다. 이번 포스팅에선 자료구조 중 Array와 Linked list에 대해 알아보도록 하자 특징 어레이(Array) = 배열 배열은 크기가 정해진 데이터의 공간이다. 한 번 정해지면 바꿀 수 없음 배열은 각 원소에 즉시 접근할 수 있다. ex) arr[0] 여기서 원소의 순서는 0부터 시작하고 이를 인덱스라고 부른다. 이 때, 즉시 접근 가능하다는 말은 상수 시간 내에 접근할 수 있음을 의미한다. 즉, O(1) 내에 접근 할 수 있다고 말할 수 있다...

처음엔 나도 다른 사람들처럼 for문 두개로 2부터 n까지 모든 수로 나눠보며 소수를 찾는 방법으로 풀이했는데 정확도만 측정하는 테스트에서조차 시간초과나는 테스트케이스가 있었다. 솔직히 이런 소수를 다뤄본적이 많이 없었기 때문에 해당 문제의 질문답변 항목을 보던중에 엄상우 라는 분의 https://school.programmers.co.kr/questions/21359 글에서 정수론 관련하여 소수의 대한 성질을 이용해 연산 과정을 급격하게 줄이는 방법을 알게됨 해당 글의 3번은 앞의 1, 2번에서 다 해결되므로 알고만 있는거로 하고 (소수인지 여부를 묻는데 짝수면 1, 2번의 과정 없이도 바로 판별이 가능하므로) n은 2이상 1000000이하의 자연수고 n이 소수인지의 여부를 묻는게 아닌 그 사이에 소수..

점근 표기법의 종류에는 빅오(Big-O) 표기법과, 빅 오메가(Big-Ω) 표기법이 있다. 빅오 표기법 - 최악의 성능이 나올 때 어느 정도의 연산량이 걸릴 것인지 ex) O(N) 빅오메가 표기법 - 최선의 성능이 나올 때 어느 정도의 연산량이 걸릴 것인지 ex) Ω(1) for element in array: # array 의 길이만큼 아래 연산이 실행 if number == element: # 비교 연산 1번 실행 return True return False 다음과 같은 함수가 있을 때 이 함수의 시간복잡도는 N * 1 인 것을 알 수 있다. 만약 array = [3, 5, 6, 1, 2, 4]에 대해 3을 찾는다면 1번의 연산만에 답을 찾을 수 있을 것이다. 하지만 array = [5, 6, 1, ..

소수(prime number)는 자신보다 작은 두 개의 자연수를 곱하여 만들 수 없는, 1보다 큰 자연수이다. // for(int i=1;i