완전탐색
완전탐색이란문제 유형복잡도 파악 완전탐색이란모든 경우를 탐색하는 방법.부분점수를 얻기 좋으나 시간 복잡도가 일반적으로 높은 편. 완전탐색 문제를 접근할 땐 고를 수 있는 값의 종류 파악 중복을 허용하는지 순서를 중요시 하는지 위 세가지를 파악해자. 문제 유형완전탐색 문제는 크게 4가지로 나눌 수 있다. N개에서 중복 허용해서 M개를 순서 있게 나열하기
Category: Algorithm
29. 백준 1080번 행렬(그리디)
문제 : https://www.acmicpc.net/problem/1080 이 문제는 그리디로 접근해야 한다.그리디는 현재 상황에서 최선을 고르는 과정을 반복해서 답을 찾아가는 것 근데 나는 개인적으로 저 정의보다 다음과 같이 이해하는게 빨랐다.그리디는 뒷 일을 생각하지 않는 거다!! 풀이법 이 문제에서도 풀이법은“처음부터 답안과 비교해 다른 원소를 만
28. 소수 판별 문제(제곱근, 에라토스테네스의 체)
제곱근으로 판별소수를 판별할 때, 굳이 모든 수를 검사 하지 않아도 된다.주어진 수의 제곱근에 해당하는 수까지 검사하면 된다. 1234567boolean isPrime(int num){ if(num == 1) return false; for(int i = 2 ; i < Math.sqrt(num); i++){ i
27. 최소공배수, 최대공약수 (GCD, 유클리드 호제법)
최대공약수, 최소공배수를 다룬 문제가 나오면 GCD나 유클리드 호제법을 반드시 알고 있어야한다!알아보자! GCD 최대공약수를 구하는 알고리즘두 수 중 작은 수가 0이 될 때까지 반복하면 된다.큰수는 작은수가 되고, 작은수는 큰수를 작은수로 나눈 나머지가 된다. 123456789//a>bint GCD(int a, int b){ whil
26. 백준 10799번 쇠막대기
접근 아이디어 스택을 사용해서 “(“이 나올 때마다 push!“)”이 나올때마다 pop하고 나서 스택에 남은 요소 만큼 쇠막대기가 더해지거나 하나만 더해진다.이전에 “(“ 였으면 스택 요소 갯수만큼, 이전에 “)”였으면 그냥 1만 더해진다. 필요한 개념 삼항 연산자에 대해 알아보자.조건문 ? true일 경우 : false일 경우 1int add =
25. 백준 17413번 단어 뒤집기2
접근 아이디어 < >안에 있는 단어를 그렇지 않은 단어와 다르게 처리해야 한다.그러나 언제 < >가 나올지 모르는게 문제다!그래서 “>”를 기준으로 문장을 나누면 < > 문자열의 위치에 규칙이 생긴다.만약 < >가 있으면 항상 뒤 쪽에 있다는 것! 필요한 문법 이번엔 라벨을 사용해서 루프를 빠져 나왔다
24. 백준 1406번 에디터
이 문제는 참 고생 많이 했다 ㅋㅋ… 틀렸던 접근 1 주어진 문자열을 char 배열로 받은 다음, 이 녀석을 ArrayList에 저장하자.그 다음 arrayList를 하나더 추가해서 마치 스택처럼 사용하자.그렇게 모든 명령을 수행하고 나면두 arraylist에 저장된 요소들을 반복문으로 하나씩 출력하자. 123456789101112131415161718
23. 백준 9012번 괄호
문제괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인 ‘(’ 와 ‘)’ 만으로 구성되어 있는 문자열이다. 그 중에서 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열(Valid PS, VPS)이라고 부른다. 한 쌍의 괄호 기호로 된 “( )” 문자열은 기본 VPS 이라고 부른다. 만일 x 가 VPS 라면 이것을 하나의 괄
22. 백준 9093번 단어 뒤집기
문제문장이 주어졌을 때, 단어를 모두 뒤집어서 출력하는 프로그램을 작성하시오. 단, 단어의 순서는 바꿀 수 없다. 단어는 영어 알파벳으로만 이루어져 있다. 입출력입력 : 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있으며, 문장이 하나 주어진다. 단어의 길이는 최대 20, 문장의 길이는 최대 1000이다. 단어와 단
21. 백준 10828번 스택
문제정수를 저장하는 스택을 구현한 다음, 입력으로 주어지는 명령을 처리하는 프로그램을 작성하시오.명령은 총 다섯 가지이다. push X: 정수 X를 스택에 넣는 연산이다.pop: 스택에서 가장 위에 있는 정수를 빼고, 그 수를 출력한다. 만약 스택에 들어있는 정수가 없는 경우에는 -1을 출력한다.size: 스택에 들어있는 정수의 개수를 출력한다.empty:
20. 백준 1004번 어린 왕자
문제어린 왕자는 소혹성 B-664에서 자신이 사랑하는 한 송이 장미를 위해 살아간다.어느 날 장미가 위험에 빠지게 된 것을 알게 된 어린 왕자는, 장미를 구하기 위해 은하수를 따라 긴 여행을 하기 시작했다.하지만 어린 왕자의 우주선은 그렇게 좋지 않아서 행성계 간의 이동을 최대한 피해서 여행해야 한다.은하수 지도, 출발점, 도착점이 주어졌을 때 어린 왕자에
19. 그래프 깊이우선탐색(DFS)
깊이우선탐색(DFS)현재 방문중인 노드와 연결된 이웃 노드 중 아직 방문하지 않은 노드 있으면, 그 노드를 다음에 방문.재귀함수로 작성, 마치 트리의 preorder방식과 비슷. psuedo code 12345678910DFS(v): mark v as visited node pre[v] = curr_time #pre리스트는 해당 노드에 첫 방
17. Backtracking 활용 - Subste Sum 문제
Subset sum주어진 집합의 부분집합의 원소 합이 특정 값이 되는 조건을 만족하는 집합을 찾아내는 문제.모든 집합을 찾아보는 건 2^n개임 DP로 푼다면?(안좋은 예시) 어떤 숫자가 포함될 경우와 그렇지 않은 경우를 모두 재귀적으로 표현 123456789subsetSum(A, i, S): #A는 배열, i는 포함 여부를 살펴보는 수의 인덱스 , S는
16. Backtracking
Backtracking답이 x1, x2, x3… 이런 형식으로 도출되는 문제에서, 유효한 답을 모두 찾는 경우 사용되는 알고리즘 기법 x1부터 차례대로 결정하면서 만약 어느 순간 조건에 맞는 답을 도출 못하는 상황에 마주하면,그 전 단계로 돌아가 다른 선택지로 다시 답을 찾아가는 방법이다. 이 기법은 굳이 더 알아보지 않아도 되는 경우를 확인하지 않도록 설
15. 그리디 알고리즘 활용 - 허프만 코딩
허프만 코딩 문제(Huffman coding problem)아스키 코드 : 알파벳과 문자들을 0~255개의 숫자로 배정한 것. 즉 8bit로 표현.이렇게 표현된 8비트의 비트들을 고정길이코드(fixed-length code)라고 한다.(문자열 100개면 800비트가 필요하게 된다.) 이때 a e i o u 같은 모음들은 빈도수가 높고 q z y는 빈도수가
14. 그리디 알고리즘
그리디 알고리즘현재 상태에서 가장 좋은 선택을 반복해서 해를 구성하는 알고리즘 문제는 이 그리디 알고리즘을 통해 얻은 해가 진짜 최선의 선택으로 얻은 해이냐는 것인데,이를 증명하기 위해서는 귀류법을 통해 증명해봐야 한다. 즉 우리가 찾은 해가 해가 아님을 가정으로 하여 다른 해를 가정하여,그 해를 논리적으로 추론하여 모순을 찾아내면, 우리가 찾은 그리디는