29. 백준 1080번 행렬(그리디)
문제 : https://www.acmicpc.net/problem/1080 이 문제는 그리디로 접근해야 한다.그리디는 현재 상황에서 최선을 고르는 과정을 반복해서 답을 찾아가는 것 근데 나는 개인적으로 저 정의보다 다음과 같이 이해하는게 빨랐다.그리디는 뒷 일을 생각하지 않는 거다!! 풀이법 이 문제에서도 풀이법은“처음부터 답안과 비교해 다른 원소를 만
Category: Problem Solving
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에서 자신이 사랑하는 한 송이 장미를 위해 살아간다.어느 날 장미가 위험에 빠지게 된 것을 알게 된 어린 왕자는, 장미를 구하기 위해 은하수를 따라 긴 여행을 하기 시작했다.하지만 어린 왕자의 우주선은 그렇게 좋지 않아서 행성계 간의 이동을 최대한 피해서 여행해야 한다.은하수 지도, 출발점, 도착점이 주어졌을 때 어린 왕자에
17. Backtracking 활용 - Subste Sum 문제
Subset sum주어진 집합의 부분집합의 원소 합이 특정 값이 되는 조건을 만족하는 집합을 찾아내는 문제.모든 집합을 찾아보는 건 2^n개임 DP로 푼다면?(안좋은 예시) 어떤 숫자가 포함될 경우와 그렇지 않은 경우를 모두 재귀적으로 표현 123456789subsetSum(A, i, S): #A는 배열, i는 포함 여부를 살펴보는 수의 인덱스 , S는
15. 그리디 알고리즘 활용 - 허프만 코딩
허프만 코딩 문제(Huffman coding problem)아스키 코드 : 알파벳과 문자들을 0~255개의 숫자로 배정한 것. 즉 8bit로 표현.이렇게 표현된 8비트의 비트들을 고정길이코드(fixed-length code)라고 한다.(문자열 100개면 800비트가 필요하게 된다.) 이때 a e i o u 같은 모음들은 빈도수가 높고 q z y는 빈도수가
13. 다이나믹 프로그래밍-3(LCS 문제)
LCS(최장공통부문자열) 문제부문자열은 문자열에서 0개 이상의 문자를 제외하고 남은 문자열을 의미YANG에서 A를 제외한 YNG같이… 하지만 AGY는 안된다! 공통 문자열은 두개의 문자열의 부문자열이 동일한 것을 말한다!이 문제는 가장 긴 길이의 공통부문자열을 찾는 문제이다! Xn 을 x1, x2, x3, … xn 즉 n개의 글자를 갖는 문자열이라고 하고,
12. 다이나믹 프로그래밍-2(행렬 곱셈 문제)
행렬 곱셈 문제 n개의 행렬 곱셈을 최소 비용으로 푸는 문제 만약 무지성으로 pXq , qXr 인 두 행렬을 3개 for루프로 풀면, O(pqr)번 연산이 필요하다.이때 여러개의 행렬이 주어졌을 때는, 행렬을 어느 순서로 곱하느냐에 따라 기본 연산 횟수가 달라진다.a = 1x2, b=2x3, c=3x4 일때, (ab)c와 a(b