목록Algorithm (87)
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) 와 같이 ..
[백준] 14916 - 거스름돈 (Java) 문제 https://www.acmicpc.net/problem/14916 풀이/후기 그리디 알고리즘을 사용하여 풀이한다. 2원과 5원을 이용해 가장 적은 동전으로 거슬러야 하기 때문에 5원으로 먼저 계산한다. 5로 나누어 떨어지지 않으면 N에서 2원을 빼주면서 cnt를 늘려주는 것이 포인트였던 것 같다. 코드 package Greedy; import java.io.*; public class Problem14916 { public static void main(String[] args) throws IOException{ BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int ..
[백준] 16926 - 배열 돌리기1 (Java) 문제 https://www.acmicpc.net/problem/16926 풀이/후기 주어지는 배열의 겉부분과 속부분을 나눠서 회전해야 하는 점이 어려웠다. 풀이를 이것저것 찾아보니 보통 회전하는 그룹(ex. 겉부분, 속부분 등)으로 분리한 후 상, 하, 좌, 우를 각각 회전시켜주는 방법이 많았다. 회전시켜주는 방법은 복잡한 방법도 많았지만, 그래프 문제를 풀며 가장 익숙한 dir 배열을 사용해 회전시켰다. 코드 package Implementation; import java.io.*; import java.util.*; public class Problem16926 { static int N, M, R; static int[][] arr; static i..