Dazzling 개발 노트

노드의 정의 배열의 시간복잡도는 중간 삽입과 삭제의 시간 복잡도가 O(N)이다. 삽입과 삭제를 매우 자주 해야 하는 상황에서 배열은 비효율적이다. 이 문제를 해결하기 위해 삽입과 삭제가 잦은 상황에서는 연결 리스트 자료구조를 사용한다. 탐색은 O(N)으로 느리지만 삽입과 삭제 연산은 O(1)로 굉장히 빠르다. 연결 리스트에서는 노드라는 개념에 대한 이해가 필요하다. 노드란 '정보를 담는 하나의 창구'라고 이해하면 쉽다. 일반적으로 연결 리스트에서 하나의 노드는 데이터와 다른 노드로 이동하는 경로를 갖고 있다. 연결 리스트는 여러개의 노드가 모여서 형성되는 구조라고 생각하면 된다. 요약하자면 연결 리스트에서 노드란 정보를 담는 하나의 창구로, 연결 리스트는 노드 간의 연속적인 연결로 구성되어 있다. 정의하..

[코드트리] 정수 명령 처리 5 (Java) 문제 https://www.codetree.ai/missions/6/problems/process-numeric-commands-5?&utm_source=clipboard&utm_medium=text 풀이/후기 입력을 StringTokenizer로 받아서 token이 1개인지 2개인지 구별했다. 그 안에서 명령이 어떤 것인지, 수행할 값이 무엇인지 확인해 배열에 넣거나 값을 출력한다. 직접 코드를 보는 것이 이해가 더 빠를 것 같다. 코드 import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws IOException { Buffere..

[코드트리] 배열의 이해 Java에서 배열을 선언하기 위해서는 다음과 같이 선언했었습니다. int[] a = new int[100]; 이렇게 선언하여 만들어지는 배열을 정적 배열이라고 부릅니다. 정적 배열의 경우에는 배열의 선언과 동시에 그 크기를 정해줘야 하며, 한번 선언된 이후부터는 크기를 바꿀 수 없습니다. 하지만 자주 길이가 바뀌는 경우라면, 명확히 메모리를 낭비하고 있는 것이 아닐까요? 이러한 문제를 해결하기 위해 나온 것이 바로 동적 배열입니다. 동적 배열은 자유롭게 길이가 줄어들고 늘어날 수 있습니다. 즉, 정확히 사용하고 싶은 만큼만 공간을 차지하여 사용하는 방식입니다. 동적 배열에서 삽입, 삭제, 탐색하는 과정은 모두 정적 배열과 동일하기 때문에 시간복잡도는 완전히 일치하지만, 메모리를 ..

기본 연산 강제로 여러 줄의 코드를 한 줄로 몰지 않는 이상, 한 줄에는 하나의 명령이 올 것 입니다. 가장 간단한 연산은 역시 대입일 것입니다. set a = 10 실제로 a라는 변수를 만들고, 10이라는 값을 할당하는 과정에서 컴퓨터는 많은 연산을 하지만, 우리는 단순하게 O(1)의 연산을 수행했다고 볼 것입니다. 조건문도 비슷합니다. set a = 5 if a != 10 print('hello') print 같은 메서드를 O(1)이라고 가정한다면, 대입도 O(1)이고 print도 O(1)이니 if a != 10 만 정확하게 알면 될 것 입니다. 그러나 결국 단순히 두 값을 비교하는 연산을 수행하기 때문에, 결과적으로 조건문도 O(1)의 시간복잡도를 보여주게 됩니다. 따라서 위 코드의 시간복잡도는 O..

본래 점근적 표기법은 수학적인 개념이기 때문에 엄밀한 정의를 설명하기엔 수학적 지식이 약간 필요하지만, 우리는 간단하게 개념을 이해할 수 있는 수준으로 설명하도록 하겠습니다. 점근적 표기법에는 크게 O, Ω, Θ가 있습니다. 각각 빅-오, 빅-오메가, 빅-세타라고 부릅니다. 간단한 다항식 n3+n2+n−1이라는 식이 있다고 가정하겠습니다. O는 가장 높은 차수 보다 같거나 높은 식을 뜻합니다. 즉, n3+n2+n−1에서 가장 높은 차수는 n3 이므로 O(n3), O(n5), O(n100) 모두 맞는 말이지만, 우리는 앞으로 이 식을 보게 되었을 때 좀 tight하게 O(n3) 라고 부르게 될 것이며, 이것이 바로 시간복잡도를 재는 척도로 쓰이게 됩니다. 이때 표현은 n3+n2+n−1=O(n5) 와 같이 ..

[코드트리] 구슬의 이동 (Java) 문제 https://www.codetree.ai/cote/13/problems/marble-movement?utm_source=clipboard&utm_medium=text 풀이/후기 스터디 시간에 풀게된 문제이다. 처음엔 쉽다고 생각했는데, 한 칸에 여러개의 구슬이 존재할 때 우선순위에 따라 제거하는 작업이 까다로웠다. 그리고 이 문제를 통해 가장 먼저 느낀 것은 '자바의 한계' 였다. 평소에도 코테 준비하면서 파이썬이 훨씬 간단하다는 것은 알고 있었지만, 이번에 특히나 더 그렇게 생각이 된 것 같다. (아마도 스터디원이 파이썬을 통해 객체 정렬을 구현한 것이 간단해 보여서 그랬을까..?) 아무튼 우선순위에 따라 가장 큰 항목을 남기기는 구현을 할 수 있겠는데, 우..