본문 바로가기

전체 글657

[leetcode][84] Largest Rectangle in Histogram 문제 : leetcode.com/problems/largest-rectangle-in-histogram/ 히스토그램 바의 높이가 저장된 배열이 주어진다. 히스토그램들로 만들수있는 직사각형의 최대 크기를 구하라. 예시로 주어진 배열로 아이디어를 구체화해보자. 인덱스별 막대바의 높이를 직사각형의 세로길이라 할 때, 구할 수 있는 직사각형의 최대값들을 구한 뒤 이들 중 최대값이 정답이 된다. 직사각형의 세로길이를 배열 값이라 가정해놨기 때문에 하나를 예로 들어서 특정 바의 세로길이로 고정해놨을 때, 최대 직사각형을 구할 수 있는 가로길이를 어떻게 구할수있는지 찾아야한다. 인덱스가 5인 경우를 예로 들어보면 인덱스 5를 포함해서 만들 수 있는 최대 직사각형은 파란색 점선과 같다. 이 때, 인덱스 2를 기준으로 .. 2021. 1. 24.
[Java] 멀티쓰레드 프로세스(Process), 스레드(Thread) 동작중인 프로그램을 프로세스(Process)라 한다. 스레드(Thread)는 프로세스의 작업 단위이다. 하나의 프로세스는 복수개의 스레드를 가질 수 있으며 이 스레드들은 자원을 공유한다. Thread 클래스 // ThreadImpl.java public class ThreadImpl extends Thread { private static int threadCnt = 1; private int cnt; public ThreadImpl() { super(); cnt = threadCnt++; } @Override public void run() { System.out.println(cnt + " run"); try { Thread.sleep(500); } c.. 2021. 1. 23.
[leetcode][1657] Determine if Two Strings Are Close 문제 : leetcode.com/problems/determine-if-two-strings-are-close/ 1. 문자열에서 어떤 두 문자의 위치를 바꾼다. ex) abcde -> aecdb (b, e 교환) 2. 문자열에 존재하는 두 문자들을 모두 바꾼다. ex) aacabb -> bbcbaa (a, b 교환) word1 문자열에 위 두 연산을 해서 word2 문자열을 만들 수 있는지 구하라. word1 문자열을 앞에서부터 탐색하면서 두 연산을 실행시켜가면서 word2 문자열을 구해봐야하나 싶지만 더 간단한 방법이 있다. 1번 연산은 문자열의 문자 위치는 변경가능하므로 위치는 무의미하다는 것을 의미한다. 즉, word1, word2의 문자들의 개수(a의 개수, b의 개수 ... )만 맞출 수 있다면.. 2021. 1. 22.
[leetcode][10] Regular Expression Matching 문제 : leetcode.com/problems/regular-expression-matching/ 문자열 s와 패턴 p가 주어질 때 문자열 s가 패턴 p에 매칭되는지 판단하라. 패턴의 경우 나올 수 있는 문자는 총 3가지로, . * 소문자 알파벳 이 있다. . : 어떤 문자가 와도 매칭된다. * : 바로 앞에 나온 패턴 문자와 0개 이상 매칭된다. 소문자 알파벳 : 동일한 문자인 경우 매칭된다. . backtracking으로 구현. 2차원 배열을 만들어 memoization 해줬다. . 과 알파벳 소문자의 패턴인 경우는 문제될게 없다. . 는 무조건 통과이므로 s, p 모두 다음 문자를 확인한다. 소문자 알파벳은 다르다면 false, 같다면 다음 문자를 확인한다. 문제는 *. s = "aaaabb". .. 2021. 1. 22.
[C++/STL] stack을 vector로 변환하기 STL에서 stack은 컨테이너에 대한 접근을 제어하는 목적으로 사용된다. 따라서 iterator를 제공해주지 않기 때문에 iterator을 사용해서 vector를 만들어낼 수 없다. 요소를 제거하면서 vector 생성 stack st; st.push(1); st.push(2); st.push(3); vector arr(st.size()); int index = arr.size() - 1; // copy st to arr while(!st.empty()){ arr[index--] = st.top(); st.pop(); } stack에서는 top을 통해서만 요소를 가져올 수 있기 때문에 top을 이용해서 vector의 뒤에서부터 값을 채워준다. 단, 이 방법을 쓰면 기존 stack에는 요소가 더 이상 남아.. 2021. 1. 21.
[leetcode][1673] Find the Most Competitive Subsequence 문제 : leetcode.com/problems/find-the-most-competitive-subsequence/ 부분 시퀀스들이 있을 때, 앞의 요소들부터 비교해나갔을 때, 사전 정렬과 비슷하게 가장 작은 수를 가지는 부분 시퀀스가 더 경쟁력 있다고 가정한다. ex) [1,3,4,2], [1,3,5,3]는 앞에 두 요소는 동일한 값이고 세 번째 요소는 첫 번째 배열의 요소가 더 작기 때문에 (4 < 5) 첫 번째 배열이 두 번째 배열보다 더 경쟁력있다. 정수 배열 nums, 양의 정수 k가 주어졌을 때, 크기가 n인 nums 배열의 가장 경쟁적인 부분 시퀀스를 구해라. stack을 사용한다. nums배열의 i번째 요소인 num를 stack에 추가한다고 해보자. 1. num을 stack의 적절한 위치.. 2021. 1. 21.

티스토리툴바