생존형 개발자의 기록

https://leetcode.com/problems/maximum-depth-of-n-ary-tree/ Maximum Depth of N-ary Tree - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com Point1 . 이진트리의 최대 높이를 구하는 문제이다. Point2. The maximum depth is the number of nodes along the longest path from the root node down to the farthest l..

https://leetcode.com/problems/single-number/ Single Number - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 비트 연산에 관한 문제이다. 난이도는 easy. 짝이 주어진 배열에서 하나만 짝이 없는 수를 추출하라는 문제다. [4, 1, 2, 1, 2]라는 배열이 있을 때, 답은 4가 된다. 이 문제의 포인트는 You must implement a solution with a linear runtime complexit..

알고리즘을 풀면서 시간 복잡도에 대한 개념은 자주 나온다. O(n), O(log n), O(log n^2),...등등 실제로 문제 풀이에 있어서 큰 영향을 미치지 않는다고 생각했지만, 점차 문제가 어려워짐에 따라 문제는 맞았을지 몰라도, 효율성 테스트에서 낮은 점수를 맞곤 하였다. 알고리즘은 효율성의 싸움이기도 하니, 알고리즘 문제 풀 때, 최대한 효율적으로 짜기 위해 시간 복잡도를 나타내는 빅오 표기법에 대해 이해해보려 한다. 1. O(1) 오원은 배열의 요소를 참조하는 알고리즘의 시간 복잡도를 나타낸다. 입력된 데이터의 크기와 상관 없이 항상 일정한 시간이 걸리는 알고리즘이기 때문이다. 2. O(n) 오엔은 순차탐색 알고리즘의 시간 복잡도를 나타낸다. F(int[] n) { (for i = 0 to ..

문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/12953 코딩테스트 연습 - N개의 최소공배수 두 수의 최소공배수(Least Common Multiple)란 입력된 두 수의 배수 중 공통이 되는 가장 작은 숫자를 의미합니다. 예를 들어 2와 7의 최소공배수는 14가 됩니다. 정의를 확장해서, n개의 수의 최소공배 programmers.co.kr 해설 : 이 문제는 최대공약수와 최소공배수 구하는 방법을 모두 알고 있어야 풀이가 가능한 문제이다. 과거 2개의 수만 주어지는 최소공배수와 최대공약수 구하는 문제가 떠올랐긴 했지만, 여러 요소가 존재하는 배열이 주어지니깐 어떻게 풀어야 할지 감이 잘 오지 않았다. 결국엔, 앞 요소와 바로 뒷 요소를 선택하..

Linked List는 데이터를 노드의 형태로 저장. 노드에는 데이터와 다음 노드를 가르키는 포인터를 담은 구조로 이루어져 있음. Node Data Next Python 내장 함수의 시간 복잡도에서 List의 삽입과 삭제의 시간복잡도가 O(n)이 걸리는 것은 배열이 물리적인 데이터의 저장 위치가 연속적이어야 하므로 데이터를 옮기는 연산작업이 필요하기 때문이다. 하지만 Linked List는 데이터를 삽입, 삭제할 경우, 노드의 Next부분에 저장한 다음 노드의 포인터만 변경해주면 되므로 배열과 비교하였을 때 linked list가 효율적으로 데이터를 삽입, 삭제할 수 있다. 그러나, 안타깝게도 Linked List에서 특정 위치의 데이터를 탐색하기 위해서는 첫 노드부터 탐색을 시작해야 한다. 그 시간이 ..