분류 전체보기
-
15926 현욱은 괄호왕이야!!백준/스택 2022. 5. 5. 21:15
다른 사람 블로그를 참고했다. 1. 풀이 5 (())( 일단 input 배열에 입력값을 받는다. 스택(stack)을 이용한다. 제일 먼저 stack에 -1을 넣는다. 이유는 나중에 알게 된다. 규칙 1. input[i] 값 = ( => stack에 i 값을 넣는다. 2. input[i] 값 = ) => stack에서 값 하나를 꺼낸다. 2-1. 이후에 만약 stack이 비어있으면, stack에 i 값을 넣는다. 2-2. stack이 비어있지 않으면, i-stack.peek() 로 올바른 괄호 문자열 길이를 구한 뒤, 올바른 괄호 문자열의 최대 길이를 다시 정해준다. 예시1을 가지고 자세히 살펴보자. for 문을 이용한다. 1) i = 0 일때 문자열의 맨 처음은 (이다. 이때는 i 값을 stack에 집어..
-
13702 이상한 술집백준/이분탐색 2022. 5. 4. 22:17
1. 문제 풀이 이분탐색으로 풀면 된다. 코드를 설명하겠다. 1) 예제 문제에 나온 예제를 살펴보자. 2 3 702 429 2) 변수 설명 N(주문한 막걸리 주전자 개수) : 2, K(친구들의 수) : 3 주전자 용량 : 702, 429 => drink 배열에 입력 이분탐색에 필요한 변수 left = 0, right = 702 (주전자 용량 중 제일 큰 값) => mid = (0+702)/2 = 351 이분탐색을 시작한다. for(int i=0; i 702/351 = 2 => count = 2 즉, 하나의 주전자에 들어있는 702 ml 막걸리를 351ml씩 나눠주면 2번 나눠줄 수 있다. 2) 주전자 용량 : drink[1] = 429 => 429/351 = 1.22222 => count = 3 (1.2..
-
12904 A와 B백준/그리디 알고리즘 2022. 5. 2. 23:03
시간초과가 날 수 있으니 조심해야 한다. 1. 문제 풀이 1) 문자열 S에서 문자열 T로 바꾸기 문제에 주어진 조건, - 문자열 뒤에 A 추가 - 문자열 뒤집고 뒤에 B 추가 모두 고려해야 한다. 2) 문자열 T에서 문자열 S로 바꾸기 이 방법은 비교적 쉽다. 문제 예제를 생각해보자. B : 문자열 S ABBA : 문자열 T 먼저 S에서 T로 바꾼 후, T에서 S로 바꾸는 과정을 살펴보자. 가. S에서 T로 바꾸기 1. 문자열 뒤에 A를 추가한다. B => BA 2. 문자열을 뒤집고 뒤에 B를 추가한다. BA => ABB 3. 문자열 뒤에 A를 추가한다. ABB => ABBA 나. T에서 S로 바꾸기 위의 과정을 거꾸로 하면 된다. 1. 문자열 뒤에서 A 제거한다. ABBA => ABB 2. 문자열 뒤에..
-
2872 우리집엔 도서관이 있어백준/그리디 알고리즘 2022. 5. 2. 20:01
1. 문제 풀이법 35421 이때 책 번호 5,4,3,2,1 순서로 생각해보면 된다. 자세히 살펴보자. 책을 빼서 맨 위에 올려 놓을 떄마다 count 를 증가시켜 보자. 1) 5는 그냥 그 자리에 두면 된다. 2) 4는 5 뒤에 있기 때문에 책을 빼서 맨 위에 올려 놓아야 한다. => 43521 count = 1 3) 3은 4뒤에 있기 때문에 책을 빼서 맨 위에 올려 놓아야 한다. => 34521 count = 2 4) 2도 마찬가지이다. => 23451 count = 3 5) 1도 마찬가지이다. => 12345 count = 4 최종 답은 4가 된다. 그러면 생각해보자. 35421에서, 5뒤에 있는 4,2,1은 모두 그 자리에서 빼서 맨 위에 올려 놓았다. 5앞에 있던 3 역시 이동이 있었다. 2)에..
-
14500 테트로미노백준/브루트 포스 2022. 4. 24. 20:14
풀이 다른 사람의 블로그를 참고했다. N*M 개의 각점에 대해서 테트로미노를 모두 적용해보며 최대의 합을 구하기는 불편하다. 다른 방법으로 dfs를 이용할 수 있다. 테트로미노는 정사각형 4개를 이어 붙인 폴리오미노이기 때문에, 한 점 (i,j)에서 depth == 4를 만족할때까지 dfs를 적용하고, 그때 dfs가 적용되는 각 칸의 값들을 더해나가며 최댓값을 구한다. 예를 들어서 (0,0) 의 위치에서 depth=4 를 만족하는 dfs를 진행하면, 아래와 같이 테트로미노가 완성된다. 테트로미노를 회전, 대칭 시켜도 된다고 했는데, depth==4 를 만족할 때까지 dfs를 진행시키면, 위의 테트로미노가 회전, 대칭되는 경우도 알아서 해결된다. 그런데, 문제는 ㅜ 모양이다. 이런식으로, 한번 왔던 점인,..
-
2866 문자열 잘라내기백준/해시 2022. 4. 23. 20:17
풀이 백준에 나와있는 3 4 alfa beta zeta 이 예시를 가지고 설명하자면, 테이블의 열을 위에서 아래로 읽으라고 했으므로, 먼저 input 배열에 아래와 같이 입력합니다. input[0] = abz input[1] = lee input[2] = ftt input[3] = aaa 그런 다음에 hashmap 인 word를 이용합니다. 1) word 에 abz 가 있다면 count 를 출력하고 끝내고 => 동일한 문자열이 발견되면 반복을 멈추고 count 를 출력하라고 했으므로 hashmap 인 word를 이용해서 동일한 문자열이 있는지 확인 없다면 word 에 abz를 집어 넣습니다. => 다음 단어인 lee, ftt, aaa가 abz와 동일한 문자열인지 확인하기 위해 그리고 input[0] = ..
-
1253 좋다백준/두 포인터 2022. 4. 18. 20:57
다른 사람 블로그를 참고해서 풀었다. 두 포인터를 활용하였다. 1) 풀이 예시 5 =N 1 2 3 5 8 => number 배열에 오름차순 정렬하여 입력. 를 생각해보자. 2) 3이 좋다 조건을 만족할까? 먼저 3이 좋다 조건을 만족하는지 생각해보자. 일단 두 포인터로 변수 one, two 를 사용한다. 처음에 one = 0, two = N-1 = 4 => number[one] = 1, number[two] = 8 => sum = number[one] + number[two] = 9 3을 변수 value 에 입력한다. => value = 3 value (3) < sum(9) 이므로, sum 값을 줄여야 value 에 가까워진다. number 배열을 오름차순 정렬했기 때문에, sum 을 줄이려면 two 인..
-
1422 숫자의 신백준/정렬 2022. 4. 17. 19:53
1. 정렬 사용하는 방법은, ex) 3=K 5=N 1234 567 89 이렇게 있다고 하자. 그렇다면 1234 567 89 를 number 배열에 넣은 다음 정렬시킨다. 그 방법은 아래에서 자세히 살펴보자. 일단 1234 567 89는 모두 1번씩 사용해야 한다. 그렇다면 이 세가지 숫자들을 어떻게 이어붙어야 가장 큰 숫자를 만들 수 있을까? 1) 먼저 1234, 567 을 어떤 순서로 이어붙어야 될까? 1234567 두개의 객체를 정렬시킬 때 두 객체의 자리가 그대로 유지된다. 2) 리턴값이 양수 => 두 객체의 자리가 변경된다. 예를 들어서 배열 input[0] =2, input[1]=3 을 가지고 정렬해보자. (compare 메서드에서는 int 형은 정렬이 안되기 때문에, Integer 형태로 저장..