본문 바로가기

장원익 기술블로그

💻 Computer Science/- Data Structure, Algorithm147

[자료 구조] - 연결 리스트 자료구조 :: Linked List Data Structure 연결 리스트 Linked List 지금까지 우리는 다량의 공통(선형) 데이터를 다루기 위해서 Array, 즉 배열을 많이 써왔다. 배열은 구현이랄 것도 없이 간단하고 쉽게 사용할 수 있지만 치명적인 단점이 있다. 바로 연속적인 데이터 저장이다. 배열은 data의 element 들이 메모리에 인접한 위치에 저장되거나 메모리에 연이어 저장된다. 이러한 점이 배열을 생성하고 삭제, 삽입하는 과정에서 큰 오버헤드를 가져올 수 있기 때문에 우리는 LinkedList를 배워야 하는 이유이다. 연결 리스트는 그림에서도 보이듯이 비연속적 위치에 각각의 데이터들이 다음 데이터를 연결하고 있다. Node 연결 리스트에는 노드라는 개념이 있다. 이 노드에 우리는 데이터를 넣고 다음 데이터를 찾을 수 있게 하는 주소 참조를 .. 2020. 6. 12.

[알고리즘-PS(스택)] 백준 10799번 자바 문제 풀이. (Stack을 활용하여 풀이) 문제 입 출력 및 예제 문제 이해 및 접근 이번 문제는 Stack을 이용하여 풀어야하는 문제이다. 문제가 어렵게 보이지만 단순화를 시켜서 본다면 다음과 같이 한 문장으로 정리할 수 있다. 괄호가 () 처럼 붙어 있으면 레이져이고, (...) 처럼 있으면 막대다. 레이져가 막대를 자르는데 잘린 막대의 갯수는 얼마인가. 그럼 다음과 같이 세 경우가 나온다. ( 문자를 만났을 경우 ) 문자를 만났을 경우 레이져를 만났을 경우 이 경우에 따라 소스만 짜주면 끝! ( 문자를 만났을 경우 이 때는 ( 로 시작하는게 막대일지 레이져일지 모르기 때문에 일단 스택에 push하고 다음에 ) 를 만나면 확인하도록 한다. Stack.push 레이져를 만났을 경우 여기서 레이져를 만났는지 아닌지 판별을 하기 위해서 한 칸 앞의.. 2020. 6. 11.

[자료 구조] - 큐 자료구조 :: Queue Data Structure 큐 (Queue) 큐 자료구조는 Abstract Data Type 으로 순차 자료구조라고도 하며, FIFO 구조를 갖는다. F : first I : In F : first O : out 앞에서 봤던 스택과는 다른 형태를 갖고 있는데, 좀 더 알아보자. 큐의 기본 원리 큐는 일단 우리가 음식점에 들어가기 위해서 줄을 서있는 것과 같다. Bob과 Steve라는 사람이 있을 때, Steve가 먼저 줄을 서 있었다면 당연히 Steve가 음식점에 먼저 들어간다. 이 것이 바로 큐의 원리이다. 큐의 연산 Enqueue enqueue는 데이터를 삽입할 때 사용하는 연산이며, queue의 길이만큼 갔을 때 더 이상 추가 연산을 진행할 수 없을 때 까지 연산이 수행될 수 있다. Dequeue dequeue는 데이터를 삭.. 2020. 6. 10.

[자료 구조] - 스택 자료구조 :: Stack Data Structure Stack 스택은 Abstract Data Type으로 추상 자료형으로 분류된다. 스택은 후입 선출 자료구조로, LIFO라고 불리기도 한다. L : last I : in F : frist O : out 스택 자료구조라고 한다면 쉽게 프링글스를 생각해보자. 스택의 기본원리 프링글스에는 감자칩이 일정한 모양으로 담겨있다. 우리가 프링글스를 꺼내먹기 위해서는 어떠한 제조 공정에서는 프링글스에 들어있는 내용물을 프링글스 통에 담아야 한다. 그럼 과자를 만들고 통에 담을 때 처음에 담기는 과자가 프링글스 통에 가장 아래에 위치하게 되고 마지막에 담는 과자가 프링글스 통에 가장 위에 위치하게 되어서 우리가 처음으로 먹게된다. 이것이 바로 스택의 기본 원리와 정확히 부합한다. 스택의 연산 Push 스택에 데이터를 넣.. 2020. 6. 10.

[알고리즘 PS(DP)] (백준 9095) 1, 2, 3 더하기 자바 백준 9095 는 solved.ac 기준 Tier : silver 3 DP 문제의 핵심은 큰 문제를 작은 문제로 나누기 이며, 해당 문제에도 적용하여 문제를 풀어야 한다. 큰 문제를 작은 문제로 나누기 위해서는 문제에 보이는 일정한 규칙을 찾아 점화식으로 도출하는 과정이 필수적이다. 문제 입출력 문제 해결 과정 문제를 해결하기 위해서 1에 더하기 경우의 수와 2의 더하기 경우의 수, 3의 더하기 경우의 수를 나눠서 생각했다. 자세히 문제를 본다면 x + x + x + x + x = n 일 경우 n이 1로 이루어진 경우 x + x + x + x + 1 = n x 는 n - 1 n이 2로 이루어진 경우 x + x + x + x + 2 = n x 는 n - 2 n이 3으로 이루어진 경우 x + x + x + .. 2020. 4. 1.

[알고리즘 PS(DP)] (백준 1463) 1로 만들기 백준 1로 만들기 는 solved.ac 기준 Tier : Silver3 이 문제는 DP 문제로 분류되며 DP 문제중 쉬운 편에 속한다. DP 문제의 핵심은 큰 문제를 작은 문제로 나누기 이며, 해당 문제에도 적용하여 문제를 풀어야 한다. 큰 문제를 작은 문제로 나누기 위해서는 문제에 보이는 일정한 규칙을 찾아 점화식으로 도출하는 과정이 필수적이다. 문제 입출력 문제 해결 과정 1로 만들기 문제는 정수 x를 입력 받고 x가 1이되기 까지 최단 횟수를 구하는 것이다. 아무렇게나 1로 만드는 것이 아니라 다음과 같은 기준이 존재한다. x가 3으로 나누어 떨어지면 3으로 나눈다. x가 2로 나누어 떨어지면 2로 나눈다. x에 1을 뺀다. 이를 기준을 문제를 작게 만들어보자. 문제를 작게하는 방법 문제를 작게 만.. 2020. 3. 27.

이전 1 ··· 18 19 20 21 22 23 24 25 다음

티스토리툴바