[ 짧은 ] 5 - 알고리즘 문제 하나 이해 하려다

 

 

 

내가 좋아하는 월레스와 그로밋에 나오는 펭귄 악당🔫

 

5️⃣ 번 글을 시작하며

구글링을 하다 보면 정말 많은 블로그 글을 보게 되는데, 편하게 적은 듯 하면서도 내용 전달이 잘 되는 글을 보면 '이 글을 쓸 때 얼마나 많은 시간을 들였을까' 생각이 들어 좋아요를 꼭 누르고 나온다. 이런 생각이 드는 만큼 나는 블로그 글을 쓸 때 오래 걸리는데, 그래도 항상 아쉬움이 남는다. 그래서 항상 '공부를 기록한다' 에 생각하며 글을 계속 써 왔는데 지금까지 글이 꽤 쌓여 뿌듯하다! 

짧은 카테고리는 더 부담을 내려놓고 글을 쓰기 위해 만들었는데, 편하게 쓰려다 보니 더 어려운 것 같아 글이 잘 안 써진다. 그럴 수록 더 부담을 내려 놓고 편하게 쓰려 한다.

 

 

 

 

 

🍔 햄버거 알고리즘 문제

작년 말부터 프로그래머스 0 레벨부터 차근차근 풀어가고 있는데 올해 초부터 1 레벨에 입성해 절반 가량 풀었다! 아직 갈 길이 멀다는걸 알지만 1 레벨까지 올라온 것에 기뻐하기로 했다.

아무튼 오늘은 햄버거 문제를 풀었다. 문제 해결은 아주 쉬웠다. 하지만 시간 초과에 애를 먹었다. 하나씩 스택을 쌓아가는 방법을 시작으로 replacingOccurrences부터 정규식까지 생각나는 방법을 다 해봤는데, 점점 코드는 가독성이 떨어지고 실행 시간이 늘어가는 걸 보면서 이건 아니다 싶었다. 이미 계획했던 하루 풀이 시간이 훌쩍 넘어갔기 때문에 구글링으로 아이디어를 얻고 내일 다시 풀어보려 했다. 근데 구글링을 하자마자 나랑 똑같이 풀고 통과한 글을 보았다. 그 분의 코드와 내 코드의 차이점은 ArraySlice 인스턴스로 Array 인스터스를 만들어 사용한 것이었다. 그 분도 문제를 풀며 이 두 객체의 속도 차이를 알게 되었다고 한다. 그래서 이건 정리할 필요가 있다고 생각이 들어 공부를 시작했다.

 

프로그래머스

[프로그래머스] Swift - 햄버거 만들기(LV.1)

 

 

 

🤔 Array와 ArraySlice

다른 언어들과는 다르게 Swift에서는 Array가 값 타입이다. 그래서 할당을 하면 참조되는 것이 아니기에 별개의 Array 인스턴스가 생성된다. 이렇게 들으면 자칫 비효율적이지 않을까 생각할 수도 있지만, 공식문서를 읽어보면 Swift가 효율적인 언어라는 것을 알 수 있다.

Array는 copy-on-write 최적화, 즉 복사 된 후 수정된다. Array 인스턴스를 가진 변수1을 변수2에 할당하면 별개의 Array라서 변수1의 변경사항에 변수2는 영향을 받지 않는다. 하지만 수정이 일어나기 전까지는 변수1과 변수2는 모두 같은 저장소를 공유(share)한다.

주의해야할 것은 reference가 아니라 share라고 표현한 것이다. 영어로된 문서를 읽으면서 느낀 점은 그냥 개발 내용도 어려운데 영어까지 해석해야하니 더욱 어렵다는 것이다. 여기서 이해에 도움이 되는 건 단어이다! 일부러 그 단어를 쓴 이유가 있기 때문에 단어로 내용을 연결해가면 공부에 도움이 된다!

다시 돌아가서 Array는 이렇게 copy-on-write 최적화를 통해 메모리 공간을 절약한다. 물론 값 타입인만큼 수정이 발생하면 해당 Array가 복사되어야 하기 때문에 비용이 들지만 변경사항이 없는데 여러 개의 복사본이 생긴다면 정말 낭비일 것이다.

 

ArraySlices는 Array.prefix 처럼 Array의 일부분을 조각(slice)내게 되면 얻게 된다. 하지만 위의 Array가 저장소를 공유(share)했던 것처럼 무조건 조각내진 않는다. ArraySlice는 원래 Array의 저장소 전체를 참조(reference)한다. 그리고 해당하는 범위를 "view"를 통해 제공한다. 그래서 Array에서 사용했던 작업들을 그대로 사용할 수도 있다. 주의해야 할 점은 "전체"를 참조한다는 것이다. 그래서 만약 원래 Array를 가리키던 변수의 LifeTime이 끝나 해당 Array를 더 이상 사용할 수 없게 되더라도, ArraySlice의 참조로 인해 메모리에서 할당 해제되지 못하고 남게 될 수도 있다. 이건 강한 참조 사이클처럼 메모리 누수(memory leak)를 발생시킬 수 있다.  

 

 

 

 

 

 

⁉️ Reference 타입은 Heap

공식문서를 통해 여기까지 잘 공부했다. 하지만 그걸로 Array와 ArraySlice 간의 속도 차이가 이해되지 않았다. 그래서 처음 이 둘의 차이를 보게 된 블로그를 다시 읽었다. 그리고 '참조 타입은 Heap영역을 사용.."한다는 말에 집중했다. 그리고 저 멀리 아득히 있던 운영체제 수업에서의 기억을 떠올렸다. 그래서 전공 서적을 꺼내 찾아 읽었다. '프로세스와 그 프로세스가 메모리에 적재되었을 때..' 설명을 읽으며 Stack과 Heap 영역을 발견했다. 이런 내용을 배웠었지 생각하며 읽었지만 정확하게 Heap영역에 참조 타입이 할당된다는 말은 없었다. 이해를 위해 구글링을 통해 다른 책 설명, 블로그 공부 글 등을 읽었다. 그러면서 나온 결과는 꼭 값 타입, 참조 타입이 어떤 영역에 들어가는건 아니라고 보았다. 하지만 참조 타입이 Heap 영역에 할당되는 건, Heap 영역이 동적영역이기 때문이라 판단했다. 그리고 Stack은 이름 그대로 LIFO 규칙을 가져 작동되어야 하니깐 지역 변수, 함수의 매개변수 처럼 LifeTime이 정확한 것들이 저장되어야 한다고 생각했다. 

그래도 이건 내 생각이라 잘못 이해한 거면 어쩌지 싶었다. 그래서 다들 어떻게 참조 타입이 Heap 영역이라고 확신했을까 생각해 블로그 글에 연결 된 링크에 집중했고, 항상 도움이 되는 블로거의 글에서 WWDC2016 영상을 발견했다.

 

[iOS] Swift의 Type과 메모리 저장 공간

Understanding Swift Performance - WWDC16 - Videos - Apple Developer

 

 

 

 

 

 

🍏 WWDC2016

2016년은 Swift 3.0이 발표된 해이다. 영상이 정확히 언제 시기인지 모르겠지만, 해당 영상을 살펴보니 Swift의 수행과 관련해 Stack과 Heap을 다루고 있었다. 내가 찾던 영상이었다! 하지만 근본을 설명하는 영상이다 보니... 1시간 분량이었다. 그것도 모두 영어로..!

그래도 Apple은 개발자들에게 친절해서 대본도 다 있었고, 문장을 클릭하면 해당하는 부분으로 이동도 해준다. 전자로는 글읽기가 너무 힘드니깐 일단 대본을 전부 출력했다. 잘 읽어보자...🫨

 

 

 

 

 

 

 

😴 마무리

그래서 하루종일 알고리즘 한 문제로 정말 많은 한국어와 영어를 읽었다.. 하지만 결과는 하나도 없어서 약간 허무해 짧은 글이라도 남겨 이 하루를 마무리하고 싶었다. 이렇게라도 글을 남기니 정말 하루가 마무리되는 기분이 들고, 오늘 정말 다양한 정보를 얻었구나 생각이 든다. 그리고 머릿속이 좀 정리된다. 실제로도 글을 쓰면서 이해한 부분도 있다. 내일은 1시간 짜리 영어 + 개발 을 이해하며 글까지 정리해야지.. 화이팅!!!