Algorithm15 [자료구조/스택] BJ 6549: 히스토그램에서 가장 큰 직사각형(Java) 문제 풀이 핵심은 큰 값이 들어올 때는 stack에 계속 쌓아주다가, 작은 값이 들어오면 그 때 쌓아온 값들을 계산하는 것이다. 이 때, 헷갈리는 것이 있었는데 위 같은 상황에서 아래와 같이 최대값이 나올 수 있다. 만약 stack을 모두 비운다면 파란색값을 어떻게 계산하는가? 예를 들어 아래와 같이 5 6 5 4 값이 있다고 해보자. 6값이 들어올 때 최대 넓이는 위 두 값만 세주면 된다. 그러고 6의 값을 stack에서 빼준다. 그러면 stack에는 왼쪽 5만 남아있다. stack 의 존재 의의는 index 저장이고, 가로길이를 세주는 것이다. stack.peek() 은 세로 길이를 의미한다. n+2 선언이유 일단 index를 n+1까지 선언하는 이유는 마지막 값에는 0을 집어넣어줌으로써 마지막 값.. 2022. 8. 9. [자료구조/스택] BJ 2504: 괄호의 값(Python) 문제 요약 링크 () 가 붙어 있으면 2, [] 가 붙어있으면 3 ( ~~ ) 와 같이 붙어있지 않고 안에 괄호값들이 있으면 안에 있는 값들의 * 2 [ ~~ ] 경우에는 * 3을 해준다. 최종 결과값을 출력하라. 문제 풀이 실버1치고 많이 어려웠다. (해당 풀이를 참조했다) 포인트는 앞에 열린 괄호가 있다면 해당 괄호들이 있는 개수와 가중치 만큼을 곱한 형태의 상태를 갖고 있는 것이다. 그래서 만약, () , [] 와 같이 붙어있는 형태가 나오면 해당 상태만큼만 더해주면 된다. 말로 설명하면 어려우니 다음 예제로 이해해보자. 위와 같은 괄호가 있다고 해보자. 그러면 2 * 2 * (2 + 3) = 20 이 될 것이다. 즉, 괄호가 앞에 나온 만큼 가중치가 생겨서 더해지는 것이다. () 괄호는 앞에 (.. 2022. 7. 20. [재귀] BJ 1991: 트리순회(Java) 문제 요약 입력값이 주어졌을 때 preOrder, InOrder, postOrder를 출력하라. 예제 입력값은 다음과 같이 주어진다. 문제 풀이 입력값 먼저 입력값을 어떻게 받아야하지? 에 대한 고민이 있었다. 나는 Map을 사용해서 미리 객체를 만들어놓고, 해당 객체들과 매핑을 시켜놓았다. ( 다른 방법은 해당 블로그들( 참조1, 참조2 ) 을 참조 ) ( python에서는 dictionary사용, java에서는 'A' 값을 빼줘서 숫자로 만들어서 매핑해주기 ) for(int i=0;i 2022. 7. 20. [그리디 & 자료구조] BJ1202: 보석 도둑 문제 요약 링크 3 2 1 65 5 23 2 99 10 2 이런식으로 값이 주어진다 3:보석 개수 2: 가방 개수 --------- 1 65 5 23 2 99 ------ 보석의 무게 / 보석의 가치 10 2 ------ 가방에 담을 수 있는 최대 무게 이 때, 각 가방에는 단 하나의 보석만 담을 수 있다 ( 이 조건을 못 보고, 가방에 여러 개의 보석을 담을 수 있다고 생각해서 헤맸다... ) 가방에 담을 수 있는 보석의 가치의 최대합을 구하라. 문제 풀이 각 가방에 단 하나의 보석을 담을 수 있는 조건을 보지 못해서 풀이를 찾아 헤매다가, 해당 블로그에서 코드를 읽으며 내가 문제를 잘 못 읽었다는 것을 알게됐다. 풀이는 다음과 같다. 최대합을 구하려면 각 가방마다 가장 가치가 큰 보석을 담아야 한다.. 2022. 7. 18. [그리디 & 비트마스킹] BJ14939: 불끄기 문제 요약 문제링크 #O######## OOO####### #O######## ####OO#### ###O##O### ####OO#### ########## ########O# #######OOO ########O# 위처럼 값이 주어졌을 때, O은 전구가 켜져있는 상태고 #은 전구가 꺼져있는 상태다. 전구를 누르면 상하좌우, 해당 좌표가 영향을 받아서 반대값 ( O -> # , # -> O ) 으로 변한다. 모든 전구를 끌 수 있는 최소값을 출력하라. 문제 풀이 아이디어를 떠올리지 못하면 풀지 못하는 문제였다. 풀이를 검색했을 때 모든 풀이가 같은 방식으로 진행되는 것으로 봐서, 아이디어 하나로 푸는 문제라고 생각하면 될 것 같다. 나 역시 구글링을 통해 아이디어를 얻었다. 문제에 대한 포인트는 2가지가.. 2022. 7. 14. [BFS/투포인터] BJ2842: 집배원 한상덕 문제 - 문제링크 처음에는 문제를 잘 못 읽고 K개를 모두 순회할 때 고도차 차이의 합의 최소값을 물어보는 줄 알았다. 그래서 '그러려면 완전 탐색을 해야하고, K의 범위에 대해서 정해져 있어야 하는데? 20이 넘는다면 어떻게 구하지?' 라고 생각이 들었고, 여러 생각을 하다가 구글링을 해봤는데 내가 문제를 잘 못 읽었음을 깨달았다. 문제는 간단하다. 배열이 2개 주어진다. 하나는 P, . , K 로 이루어진 2차원 배열이다. 다른 하나는 각 문자에 해당하는 값이 주어지는 2차원 int 배열이다. 이 때, P에서부터 시작해서 K개를 모두 순회할 때, 가장 큰 값과 가장 작은 값의 차이를 구하는 문제다. 문제 풀이 투포인터에 대한 아이디어를 떠올릴 수 있느냐 없느냐가 주요한 방점이다. 먼저 입력받은 이차원.. 2022. 7. 5. [링크드 리스트] Linked List내에 사이클 존재하는 지 찾기 문제 문제는 다음과 같다. LinkedList가 존재할 때, 해당 LinkedList내에 사이클이 존재하는 가? HashSet을 이용한 풀이 1 -> 2 -> 3 -> 4 -> 2 와 같이 연결이 돼 있을 때, HashSet에 포함된 코드가 순회 중에 나온다면 해당 LinkedList는 사이클이 존재하는 것이다. 투 포인터를 이용한 풀이 투포인터 투 포인터를 사용해서 푼다. 토끼는 거북이보다 2배 빠르게 이동한다. Rabbit은 Turtle보다 2배 빠르다. 거북이가 사이클에 진입했을 때 토끼는 거북이보다 사이클내에 R만큼 떨어져있는 곳에 위치한다. 이 때, 사이클내에서 거북이와 토끼는 무조건 만나게 돼 있다. 만나는 것에 대한 증명 원이 있다고 해보자. 원에서 토끼랑 거북이가 달린다. 토끼는 거북이보.. 2022. 6. 3. [Heap] BJ 1655: 가운데를 말해요 문제풀이 문제 링크 입력값이 들어오면 가운데 값을 출력하는 문제다. (Heap 자료구조를 이용해서) 중간값을 찾는 것이 문제다. 아이디어를 생각하기가 쉽지 않은 문제다. 문제의 아이디어는 다음과 같다. Heap 자료구조를 2개 선언해준다. 하나는 작은 값들의 최대값, 하나는 큰 값들의 작은 값이다. maxHeap에는 minHeap보다 작은 값들만 minHeap에는 maxHeap보다 큰 값들만 들어갔다고 가정하면 maxHeap의 root값을 매 input마다 반환해주면 된다. ( 이 때, input은 maxHeap부터 차례로 maxHeap에 하나, minHeap에 하나, maxHeap에 하나 ... 이런식으로 홀짝으로 넣어준다 ) 그렇다면 maxHeap의 값들이 어떻게 minHeap의 값들보다 작게 설정될.. 2022. 5. 26. 이전 1 2 다음
