기초 알고리즘!
1.기초 알고리즘 - 스택(1)
https://st-lab.tistory.com/142?category=856997알기 쉽게 설명해준 출처를 참고했으므로 남긴다.스택에 대한 개념을 알 수 있다.
2.기초 알고리즘 - 단어 뒤집기(2)
단어 뒤집기 문제다.첫 줄에 테스트 케이스 T를 입력받는다.다음 줄 부터는 공백단위로 문장을 입력받고, 입력받은 문자열의 순서를 바꾼다.어려울게 없는 문제다.나는 공백 단위로 입력을 받지만 얼만큼의 공백을 입력받는지는 모르기때문에 hasMoreTokens를 이용해 반복
3.기초 알고리즘 -괄호(3)
괄호 문자열은 (, ) 두 괄호만으로 이루어진 문자열이다.이 중에서 ()처럼 제대로 배치된 문자열은 VPS이고, vps끼리 접합시켜도 vps이다.즉, 처음과 끝이 ()로 닫혀있어야만 한다.논리적인 구조로 볼 때, 여기서 해석할 수 있는 것은 무엇일까?처음과 끝이 닫히므
4.기초 알고리즘 - 스택 수열(4)
문제를 이해하는 시간이 꽤 걸렸다. 1에서 n까지의 숫자를 순서없이 입력받고, 1부터 n까지를 오름차순으로 스택에 push 와 pop을 이용해서 입력받은 순서대로 수열을 만들어야한다. 43687521을 입력받으면, push1 -> push2 -> push3 -> p
5.기초 알고리즘 - 에디터(5)
문자를 기록해 명령어에 해당하는 문자를 편집하는 에디터를 만드는 문제다. 커서를 L이라고 할 때, 문자열의 마지막 위치인 L+1에서 커서가 시작한다.L : 커서를 왼쪽으로 한 칸 옮김 (커서가 문장의 맨 앞이면 무시됨)D : 커서를 오른쪽으로 한 칸 옮김 (커서가 문장
6.기초 알고리즘 - 큐(6)
큐에 대한 문제다.큐를 사용하기 위해 필요한 조건은 둘이다.LinkedListQueue위와 같이 선언하고 기능들은 아래와 같다.addofferpollremoveisEmptysizepeek이 문제는 back만 잘 처리해주면 문제 없다.이 문제에서 back은 가장 뒤에 있
7.기초 알고리즘 - 요세푸스 문제
1 2 3 4 5 6 7 -> 31 2 4 5 6 7 -> 61 2 4 5 7 -> 21 4 5 7 -> 71 4 5 -> 51 4 -> 14이 순열은 N, K를 입력받아 N까지의 수에서 K번쨰 수를 제거해가는 순열이다. K번째 수를 제거하면, K+1부터 3번째 수를
8.기초 알고리즘 - 덱
이번 문제는 덱을 활용한 문제다.덱은 스택과 큐, 둘의 기능을 모두 활용이 가능하며, 앞과 뒤로 모두 자료를 삽입하거나 삭제하는게 가능하다.이번 문제는 기본 덱의 기능들을 활용해 푸는 문제다. 매우 쉽게 다음과 같이 풀 수 있다.조심해야 할 부분은, if문이다. 나는
9.기초 알고리즘 - 단어 뒤집기 2
문자열을 입력받아 뒤집는 문제다. 뒤집을 때, 처음과 끝이 <>인 문자열들은 뒤집지 않고 그대로 출력되는 것이 조건이다.나는 이 문제에 스택을 사용해서 풀어보겠다. 결국, 단어를 쌓고 반대로 출력할 때는 스택에서 pop을 해줘야하므로, 공백과 <>같은 예외를
10.기초 알고리즘 - 쇠막대기
레이저로 막대를 자르는 문제다.()가 나오면 무조건 레이저를 표현한다.문제를 직관적으로 생각해보면 '('가 3개면 쇠막대기 3개가 중첩된 것이다. 그리고 ()를 입력받으면 앞에 쌓인 '('의 수 만큼 절단한다. ex) ()(((()())(())()))(())여기서 ((
11.알고리즘의 성능
특정한 크기의 입력에 대하여 알고리즘의 수행 시간 분석특정한 크기의 입력에 대하여 알고리즘의 메모리 사용량 분석가장 빠르게 증가하는 항만을 고려해 표현한 표기법!O(1) -> 상수 시간O(logN) -> 로그 시간O(N) -> 선형 시간O(NlogN) -> 로그 선형
12.알고리즘 이론 - 그리디 알고리즘
그리디 알고리즘 >- 현재 상황에서 지금 당장 좋은 것만 고르는 방법 단순히 가장 좋아보이는 것을 반복적으로 선택해도 답을 구할 수 있을지 확인함. 노드간선
13.알고리즘 이론 - 구현
구현이란, 머릿속의 알고리즘을 소스코드로 바꾸는 과정.일반적으로, 코딩테스트에서 구현 문제는, 풀이는 쉽지만 소스코드로 바꾸기는 까다로운 문제를 칭한다.시뮬레이션 - 일련의 명령에 따라서 개체를 차례로 이동시키는 문제. 단순 구현 문제이기 때문에 어떻게 구현할지의 아이
14.알고리즘 이론 - DFS
탐색이란 수많은 데이터에서 원하는 데이터를 찾는 과정임.그래프 탐색 알고리즘에는 대표적으로 DFS, BFS가 있음.팩토리얼, 유클리드 호제법(최대공약수) 등이 재귀에서 흔히 사용됨.\-> 이는 나중에 따로 다룰 예정이다.DFS는 깊이 우선 탐색으로 그래프의 깊은 부분을
15.알고리즘 이론 - BFS
BFS > - BFS는 너비 우선 탐색이라고 부르며, 그래프에서 가까운 노드부터 우선 탐색하는 알고리즘임. 큐 자료구조 이용 1. 시작 노드를 큐에 삽입하고 방문 처리함(True) 2. 큐에서 노드를 꺼내고, 인접 노드 중 방문하지 않은 노드를 모두 큐에 삽입하
16.알고리즘 이론 - 거품 정렬
거품 정렬은 현재 인덱스와 다음 인덱스의 크기를 비교해 다음 수가 크다면, 그대로 두고 다음 수가 현재 인덱스보다 작으면, 값의 위치를 바꾸는 정렬 방법이다.
17.알고리즘 이론 - 선택 정렬
선택 정렬(select sort)
18.알고리즘 이론 - 카운팅 정렬
카운팅 정렬(Counting Sort) > - 카운팅 정렬은 계수 정렬이라고도 한다. 카운팅 정렬은 정수로 이루어진 리스트만 정렬이 가능하다. 리스트의 정수의 값을 인덱스로 활용하는 방법을 사용하기 때문이다. 그러므로, 값이 인덱스가 되기 위해서는 리스트 안의 최대값을
19.알고리즘 이론 - 정수론
모듈러의 성질소수 판정약수 구하기소인수 분해유클리드 호재법에라토스테네스의 체빠른 거듭제곱