728x90 Algorithm88 스택, 큐, 덱 정리 스택(Stack)스택이란 젠가 통에서 젠가 블록을 뺄 때처럼 입구와 출구가 같은 자료구조를 스택(stack)이라고 한다.이러한 구조를 후입선출 구조(LIFO : Last In First Out)라고 한다. Stack에는 5가지 함수가 사용된다. push(x) : x 를 스택에 넣는다.size() : 스택에 쌓인 블록의 개수를 반환한다.empty() : 비어있다면 true, 비어있지 않다면 false를 반환한다.top() : stack에 블럭을 제거하지 않고 최상단의 값을 반환한다.pop() : 맨 위에 숫자를 반환한다( 최상단의 값이 제거된다)stack과 배열의 관계배열의 크기가 무한하다고 가정했을 때, 배열에 삽입과 삭제 연산이 발생하는 장소를 맨 뒤에만 생긴다는 가정했을 때, 배열을 스택처럼 활용할 .. 2024. 4. 27. 백트래킹이란 💡 백트래킹은 그래프를 순회하면서 값을 찾는 중 막힐 경우 다시 되돌아가서 해를 찾는 기법을 말합니다. 이때 해를 찾는 도중에 해당 그래프 경로에 해가 존재하지 않게 될 경우 탐색하지 않는 것도 백트래킹의 일종이라고 합니다. → 전문용어로는 가지치기 라고 해요 가지치기를 통해서 더이상 탐색하지 않아야 하는 경우를 줄여 코드를 효율적으로 작성할 수 있습니다. 알고리즘 문제를 풀때 문제에 원하는 조합을 만들고 문제에서 원하는 답을 고르는 경우가 존재합니다. 만드는 조합이 크지 않고 시간이 충분하다고 생각이 들면 이러한 경우 for문만으로 표현하기 어렵고 이때 그래프 탐색 개념을 활용하고 백트래킹을 이용하여 문제를 해결할 수 있습니다. 그래프 탐색 문제 같은 경우 문제푸는 요령(bfs, dfs) 트리를 직접 .. 2024. 4. 22. 재귀함수 분석 & 초 간단 트리 이론 Part 1 재귀함수 아래 코드를 보고 두 개의 코드 출력 결과를 생각해 보세요 코드 1 package baekjoon.tree; public class RecursionPrac { public static void main(String[] args) { int n = 7; recursion1(n); } public static void recursion1(int n) { if(n == 0) return; System.out.println(n); // 출력하는 코드 입니다. recursion1(n - 1); } } 코드 2 package baekjoon.tree; public class RecursionPrac { public static void main(String[] args) { int n = 7.. 2024. 4. 22. 스택의 활용(연산 표기법 : 중위 표기법, 전위 표기법, 후위 표기법) + 큐 연습문제 수식을 표현하는 방법에 3가지가 있습니다. 중위표기법(infix) : 연산자가 안에 있어서 infix라고 부릅니다. ex) 2 + 3 * 5 전위 표기법(prefix) : 연산자가 앞에 있어서 prefix라고 부릅니다. + 2 * 3 5 후위 표기법(postfix) 연산자가 피 연산자 다음에 있어서 postfix라고 부릅니다. ex) 2 3 5 * + 💡 후위표기법이 필요한 이유 우리가 익숙하게 사용하는 중위표기법은 컴퓨터가 이해하기 힘들다. 컴퓨터가 이해하기 쉽게 도와주는 방법이 후위표기법을 사용하는 이유이다. infix → postfix로 변환 방법 각각의 연산에 괄호를 친다. 연산자의 오른쪽 괄호 다음으로 연산자를 이동한다. 괄호 지운다. infix를 posfix로 변환하는 방벙(코드) 스택을 활용.. 2024. 4. 22. 알고리즘 시간 복잡도 연산의 횟수를 점근적 표기법을 통해 추상적으로 표현하는 것을 시간복잡도 라고합니다. 표기는 대문자 O를 이용해서 표기 코드의 시간복잡도는 최악의 경우의 수를 가정하고 부릅니다. 코드의 시간복잡도는 연산 중에서 가장 복잡한 시간복잡도를 기준으로 합니다. Ex) 1 int sum = 0; for(int i = 0; i < 10; i++) { sum += i; } //위와 같은 연산을 했을때 연산은 총 10번 실행됩니다. int sum = 0; for(int i = 0; i < N; i++) { sum += i; } // 위와 같은 연산을 했을때 연산은 총 N번 실행됩니다. 위 코드처럼 N번실행되는 경우 O(N)이라고 표기합니다. Ex) 2 int a = 5; System.out.println("a"); 예제.. 2024. 4. 22. 백준 15651 자바 (N과 M(3)) https://www.acmicpc.net/problem/15651 15651번: N과 M (3) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 1. 어떤 접근으로 문제를 접근하려고 했는지 중복순열의 모든 경우의 수를 출력하는 문제이다. 다른 N과 M 문제와 다르게 단순하게 그냥 재귀함수로 숫자를 넣고 재귀함수가 끝날 때 숫자를 제거하면 되는 문제이다. 2. 문제를 해결하기 위한 기능 중복순열 구하는 기능 선택한 숫자 출력기능 import java.util.*; import java.io.*; public class Main { publ.. 2024. 4. 22. 백준 15650 자바 (N 과 M(2)) https://www.acmicpc.net/problem/15650 15650번: N과 M (2) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 1. 어떤 접근으로 문제를 접근하려고 했는지 nCr의 경우의 수를 출력하는 프로그램이다. 조합은 순서가 상관없으므로 매개변수에 v라는 값을 통해 한번 출력을 했을 때 순서가 바뀌어서 출력되는 부분을 막는다. 2. 문제를 해결하기 위한 기능 nCr 기능 구현 import java.util.*; import java.io.*; public class Main { public static int n,.. 2024. 4. 22. 백준 15649 자바 ( N 과 M (1)) https://www.acmicpc.net/problem/15649 15649번: N과 M (1) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 1. 어떤 접근으로 문제를 접근하려고 했는지 일반적인 순열을 출력하는 문제이다. visited라는 boolean 배열을 활용해서 사용한 숫자의 경우 해당 인덱스를 True로 바꾼다. true로 되어있을 경우, 재귀함수를 동작하지 않게 코드를 작성한다. 재귀함수에서 나오게 되면 다시 사용을 해야하기때문에 visited를 False로 다시 바꿔줘서 순열을 구현한다. 2. 문제를 해결하기 위한 기능 .. 2024. 4. 22. 백준 1918 자바 (후위 표기식) https://www.acmicpc.net/problem/1918 1918번: 후위 표기식 첫째 줄에 중위 표기식이 주어진다. 단 이 수식의 피연산자는 알파벳 대문자로 이루어지며 수식에서 한 번씩만 등장한다. 그리고 -A+B와 같이 -가 가장 앞에 오거나 AB와 같이 *가 생략되는 등의 www.acmicpc.net 1. 어떤 접근으로 문제를 접근하려고 했는지 1) A ~ Z 문자(피연산자)일 경우 출력한다. 2) 이때 스택이 비어있으면 그냥 스택에 연산자를 push 한다. 3) 스택이 비어있지 않을경우 스택의 최상단 연산자와 들어오려는 연산자의 우선순위를 비교한다. 4) 만약 스택의 최상단보다 들어오려는 연산자의 크기가 들어오려는 연산자가 스택의 최상단에 있는 연산자보다 크기가 같거나 작을 때까지 본인보.. 2024. 4. 22. 백준 2164 자바 (카드 2) https://www.acmicpc.net/problem/2164 2164번: 카드2 N장의 카드가 있다. 각각의 카드는 차례로 1부터 N까지의 번호가 붙어 있으며, 1번 카드가 제일 위에, N번 카드가 제일 아래인 상태로 순서대로 카드가 놓여 있다. 이제 다음과 같은 동작을 카드가 www.acmicpc.net 1. 어떤 접근으로 문제를 접근하려고 했는지 문제에서 요구하는 건 하나를 빼고 그다음 하나는 담고 이러한 행위를 반복한다. 하나를 빼서 맨뒤로 보낸다 -> 전형적인 큐를 사용하는 문제이기 때문에 큐 자료구조를 이용해서 문제를 풀어야 하는지 접근하려고 했다. 2. 문제를 해결하기 위한 기능 목록 큐를 이용해서 값을 담아두고 한 번은 값을 버리고 한 번은 값을 맨뒤로 옮기는 행위 import java.. 2024. 4. 22. 백준 18258 자바 (큐 2) https://www.acmicpc.net/problem/18258 18258번: 큐 2 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 2,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 www.acmicpc.net 1. 어떤 접근으로 문제를 접근하려고 했는지 Deque를 이용하려고 했으나, 큐를 구현해 보고자 배열을 이용해 큐를 구현했다. 앞에 있는 원소를 제거하는 기능을 구현하고자 front 변수를 활용해 처음에 0을 저장해 놓고 pop을 하면 front번째 값을 가져오고 front값을 1씩 더했다. 맨 뒤 값을 가져와야 하기 때문에 back 변수를 활용해서 front와 비슷한 방.. 2024. 4. 20. 백준 10773 자바 https://www.acmicpc.net/problem/10773 10773번: 제로 첫 번째 줄에 정수 K가 주어진다. (1 ≤ K ≤ 100,000) 이후 K개의 줄에 정수가 1개씩 주어진다. 정수는 0에서 1,000,000 사이의 값을 가지며, 정수가 "0" 일 경우에는 가장 최근에 쓴 수를 지우고, 아닐 경 www.acmicpc.net 1. 어떤 접근으로 문제를 접근하려고 했는지 0을 부를 때마다 직전의 적었던 번호를 지워야 한다. 즉 맨 마지막번째 숫자를 가지고 넣고 지우는 행위를 반복하는 문제이다. LIFO인 Stack을 활용하는 것이 효과적이라고 생각했다. (물론 일반적인 list도 가능하긴 하다) 2. 향상된 for문을 이용해 Stack의 모든 값들을 접근해서 다 더한 값을 구하려고 했다.. 2024. 4. 20. 이전 1 2 3 4 ··· 8 다음 728x90
