알고리즘 공부...공......공12 [백준: 알고리즘_Java] 1463_1로 만들기 시간 제한이 0.15초로 너무 짧아서.. 고민하다가 이 문제의 분류가 다이나믹 프로그래밍이라서 구글에 검색을 해보았더니..... 다이나믹 프로그래밍(동적 프로그래밍) : 분할정복 알고리즘처럼 큰 문제를 작은 단위로 나누어 풀면, 작은 문제들이 겹쳐서 비효율적이다. -> 이렇게 겹치는 작은 문제들을 따로 저장해 두었다가 다음번 문제를 풀 때 바로 적용. --> 효율적 피보나치 수열을 구하는 과정이 대표적인 예시. (재귀함수 호출 X) 사용 조건 : 최적 부분 구조 (Optimal Substructure) 큰 문제를 작은 문제로 나눌 수 있으며 작은 문제의 답을 모아서 큰 문제를 해결할 수 있다. 중복되는 부분 문제 (Overlapping Subproblem) 동일한 작은 문제를 반복적으로 해결해야 한다. .. 2022. 1. 2. [백준: 알고리즘_Java] 17298_오큰수 아니...나는 처음에 그냥 배열에 넣어서 풀었는데.. 계속 시간초과가 뜸. 그래서 구글에 쳐봤는데 스택으로 하는 거더라... 배열로도 할 수 있는데 그것도 배열을 스택처럼 이용해서 푸는 거였음. 근데 스택으로 다시 이해하기가 너무 귀찮아서 그냥 못 본 척하고 내가 했던 대로 하는데.. 시간 줄일라고 별의 별 노력(버퍼로 받기...for 줄이기..등등)을 했지만. 계속 시간 초과가 뜨길래 그냥 스택으로 바꿔서 풀기로 결심함. 이제부터 한번 해보겠음. 으아아아악 머리아파. 구글에서 살짝 보고 넘긴걸 바탕으로 생각해 보겠음. --이게 처음에 배열로 푼거. import java.util.*; import java.io.*; public class RightBig { public static void main(S.. 2022. 1. 1. [백준: 알고리즘_Java] 1874번_스택 수열 그니까 첫 번째로 입력받는 숫자는 수열을 뽑는 스택의 크기가 될 것임. 그리고 다음으로 계속 입력받는 수들은 우리가 스택에 추가하고 뽑아야 될 수. (뭐래는거야..) 아무튼 간단하게 예를 들면 4라는 수가 처음 주어졌을 때, 순서대로 3 2 1 4를 입력했다고 치면 스택에 적절히 push, pop을 하면서 pop할 때 나오는 수가 순서대로 3 2 1 4가 되도록 하는 것임. (stack에 push할 때는 오름차순만 가능) push하면 +출력, pop하면 -출력 내가 진짜 이 문제 2시간동안 푼 듯.. 구글에 풀이 검색하고 싶은 거 꾹 참음. 처음엔 Scanner와 Bufferedwriter를 이용했는데, 버퍼의 마지막 개행문자때문에 출력초과가 떠서 버퍼 대신 StringBuilder 사용함. -> 마지막.. 2021. 12. 29. [백준: 알고리즘_Java] 9012번_괄호 이건 Scanner를 사용해도 시간 초과가 안뜨지만 그냥 버퍼를 씀. 그냥. 그냥. 그냥 올바른 괄호만드는 구조를 잘 살펴보자면… (()()) —>이걸 예시로 보겠음 앞에서부터 괄호를 확인하는데 닫는괄호 ')'가 나오면 그 전의 짝이 없는 괄호 중 제일 마지막으로 봤던 괄호랑 짝을 맞춘다. 제일 마지막걸 뺀다는 것에서.. Stack을 이용해야겠다는 생각이 들음. 왜냐?! Stack은 Last In First Out 구조이기 때문. (사실 중간고사 시험 보기 전에 스택 공부해야되서 이거 풀이 찾아봤었음. 그래서 스택 이용해야된다는 걸 알았다. 안 봤으면 풀기 힘들었을 듯…..) 1. 괄호문장을 입력받아 char배열에 넣음. 2. char 배열의 요소들을 순서대로 검사 3. '(' 나오면 Stack에 값 추.. 2021. 12. 26. [백준: 알고리즘_Java] 9093_단어 뒤집기 이것도 앞의 문제와 마찬가지로 BufferedReader, BufferedWriter를 사용해야 시간초과가 안뜸. 단어의 순서는 유지하고, 단어를 뒤집어서 출력해야 하므로 띄어쓰기를 기준으로 Stack에 넣고 출력하기로 함. 1. 일단 한 문장을 입력 받아 char 배열에 넣음 2. for each문으로 순서대로 검사. 3. 띄어쓰기가 나오기 전까지 Stack에 계속 추가하다가 4. 띄어쓰기가 나오면 Stack에 넣은 모든 문자들을 pop()해서 버퍼Writer에 쓰기. (주의사항: 한 단어를 출력하는 것이니 모두 다 write()한 후 띄어쓰기(공백)를 추가로 write..) 5. (3~4)번 반복하다가 마지막 단어까지 Stack에 추가하고 나면, 더 이상 띄어쓰기가 나오지 않으므로 다음문장을 입력받기.. 2021. 12. 24. [백준: 알고리즘_Java] 10828_스택 처음엔 Scanner를 이용해서 풀었는데.. 시간초과가 된다고 하여. BufferedReader/Writer를 사용하기로 하였다. .....하지만 평소에 학교 수업에서는 Scanner를 주로 써왔기에, Bufferd~이걸 어떻게 사용해야 할 지 모르겠어서 우선 Buffered~를 공부하기로 했다. (근데 5분정도 공부하다가 깨달은 건데.. 기말고사 시험 범위였구나? 그래서 기억이 남. 그러니 간단히만 적겠음.) 특징: ENTER단위로 입력받음. String형식으로 고정됨. Scanner 보다 속도 빠름 -> 이 문제에서 버퍼 쓴 이유 (버퍼 사이즈 지정할 수 있지만, 지정 안 하면 디폴트 사이즈로 알아서 됨) 사용법: BufferedReader br = new BufferedReader(new Input.. 2021. 12. 24. 이전 1 2 다음
