개인적으로 공부한 내용을 정리중입니다.

정답은 heap이다... 그런데 string은 value 타입임. 즉 swift에서 저장 공간과 value, reference 타입은 관계가 없다. 즉 value 타입이라고 항상 스택에 저장되는게 아니다. 하지만 string은 짧은 문자열은 스택에 저장되기도 한다 함(16바이트 이하)...? string이 heap에 저장되는 이유에 대해 알아보자. array, dictionay, set, string(collection of char)과 같이 가변 길이의 Collection들은 내부 데이터를 힙에 저장한다. 컴파일 타임에 그 사이즈를 정확히 알기 어려워 heap에 할당 후 사이즈를 조절한다. 주로 스택에 저장되는 경우는 변수의 생명주기가 static한 경우고, value type의 사이즈가 컴파일 타임에..

내가 전에 면접 문제로 풀어본 문제다 난 히스토그램 문제랑 비슷하게 생각해서 했는데 탈락했다 ㅋㅋ 다시 풀어보자 여러 방법으로 과연 내가 왜 틀렸던 것인가 풀이가 틀린게 아니라면 내가 못알아 듣게 말한게 큰거 같다. 면접에서 일단 첫구현인 내가 생각했던 방법이다. 틀렸따. ㅋㅋ class Solution { public: int trap(vector& height) { int cur; int sum=0; for(int i=0;i=0 && height[left-1] > height[left]){ left -= 1; } while(right+1 < height.size() && height[right] < height[right+1]){ right += 1; } cout

2504번 괄호의 값. 내 코드 #include #include #include #include #include using namespace std; using li = long long int; string str = ""; int idx = 0; stack st; bool flag =true; void pushStack(char x) { if (x == ')') { if (st.size() > 0) { if (st.top() == '(') { st.pop(); } else { flag = false; } } else { flag = false; } } else if(x==']'){ if (st.size() > 0) { if (st.top() == '[') { st.pop(); } else { flag..

이 문제를 스택으로 해결했었다. 그런데 음 스택으로도 다시 풀어보고, 분할 정복으로도 풀 수 있던데 두가지로 풀어보겠다. 이전에 스택했으니 일단 분할정복으로 하자. 보통 분할 정복은 절반씩 분할하는거 같다. 계속 분할해서 한개가 되고 두개로 합칠때 음? 어떻게 생각해야되는 걸까.... 음 분할해서 해당 영역의 가장 큰 넓이를 찾으면 된다고 생각한다. 그리고 이제 두개를 합치면 되는거 같은데, 그렇다면 합칠때 양쪽 중에 더 작은 높이 * 양쪽 갯수 랑 두개 영역을 비교해서 가장 큰 넓이를 선택하게 한다. 이때 합병하면서 저장해야 되는 값은 가장 작은 높이, 합친 넓이이다. 가장 작은 높이랑 갯수를 알면 왼쪽 오른쪽을 합칠때 합쳐질 넓이를 알 수 있다. 재귀함수를 사용할텐데 매개 변수로 시작,끝 인덱스를 넘..

스택은 진짜 그냥 맨날 나오는 문제 유형이다. 면접에서도 중요한 개념으로서 이용하라고 문제 냈는데 틀렸다.... 탑 사실전에 백준에서 풀어본 문제다. 그럼에도 풀이가 기억나지는 않음 스택을 쓴다는 것 정도 ㅋㅋ. 코딩테스트에서도 실제로 만났던 문제인데 그 당시에는 풀 줄 몰랐다. [6,9,5,7,4] [0,0,2,2,4] 예제를 분석해보면 6은 맨 왼쪽이라 0 , 9는 왼쪽에 자기보다 큰게 없어서 0, 5는 왼쪽에 9가 있으니 2, 7도 왼쪽에 5는 스킵되고 9가 있으니 2, 4는 7이 바로 왼쪽에 있으니 4이다. 그럼 목표는 모든 위치에서 왼쪽에 가장 먼저 자기보다 큰 기둥을 찾는 것이다. 스택에 넣다가 해당 위치에서의 답을 구하려면 스택에서 빼면서 먼저 만나는 자기 보다 큰 값을 확인하면 될거 같은데..