오늘은 bfs/dfs 문제 푼 날! 역시 bfs가 만만해 ... 재귀함수 짜는 건 여전히 어렵다ㅠ
그래서 나는 둘 중에 하나 선택할 수 있다하면 bfs로 푼다 ...
그치만 dfs가 간단한 건 사실이지만...
내일 다시 코딩테스트 치는 날이 되었다ㅠㅠ 이번에는 4시간에 4문제라고 한다. 내일 시험 잘 쳐보자~
- 오늘 진행된 강의에서 학습한 내용은 무엇인가요?
bfs / dfs
- 이번 주 진행된 팀 스터디에서 얻은 인사이트는 무엇인가요?
기술 매니저님 피드백
- 인접 리스트, 인접 행렬 시간 복잡도 차이 나는 이유는?
리스트는 연결되어있고 행렬은 하나하나 전부 넣어줘야하기 때문에 - 순서에 의한 자료구조 활용 1, 2번 우선순위큐나 treeSet 사용하면 좀 더 쉽게 풀 수 있었을 것임
만약 정렬을 해야한다면 자료구조부터 생각해보아라 - 한 번에 정렬 vs 들어갈 때마다 정렬 시간 차이가 그렇게 많이 나진 않을 것이다.
내가 사용하기 편한 걸 쓰는 게 좋다. 실수를 줄이기 위해 - dfs 풀 때 스택으로도 한 번 풀어봐라 이유: 재귀는 메서드 호출 시 call stack에 계속 쌓여서 깊게 쌓이다 보면 exception이 발생할 수 있다. depth가 깊어지면 스택을 사용해서 풀어라 (이 문제는 꼭 스택으로 풀어야한다!라는 문제가 있는 경우도 있다.)
- visited 배열 boolean으로 사용하는 게 좋음 boolean 1 byte, int 4 byte 조심!
최대한 작게 쓸 수 있는 단위부터 사용하는 게 좋다. - String은 몇 바이트인가?
String 클래스와 메모리 할당
Java에서 String 객체는 주로 문자열의 길이와 인코딩 방식에 따라 메모리 크기가 달라집니다. String 객체는 내부적으로 문자 배열(char[])을 사용하여 문자 데이터를 저장하며, 이 배열의 크기는 문자열의 길이에 따라 결정됩니다. 또한, String 객체 자체에는 추가적인 메타데이터가 포함되어 있어, 객체 헤더와 길이 필드 등으로 인해 기본적으로 약 24바이트의 고정 오버헤드가 발생합니다.
String 객체의 메모리 할당
기본 오버헤드: String 객체는 약 24바이트의 기본 오버헤드를 가집니다. 이는 객체 헤더와 길이 필드 등에 사용됩니다.
문자 데이터 저장: 문자열의 실제 데이터는 내부적으로 char 배열을 사용하여 저장되며, 이 배열의 크기는 문자열의 길이에 따라 달라집니다.
한글 백만개를 포함한 String 객체
메모리 사용량: 한글 문자는 일반적으로 UTF-16 인코딩에서 2바이트를 차지합니다. 따라서, 한글 백만 개를 포함하는 String 객체는 대략적으로 2MB(백만 * 2바이트)의 메모리를 사용하게 됩니다. 여기에 기본 오버헤드 24바이트를 더하면, 총 메모리 사용량은 약 2MB 조금 넘는 수준이 됩니다.
String 객체의 메모리 할당량은 문자열의 길이와 인코딩 방식에 따라 달라지며, 한글과 같은 다국어 문자를 다수 포함할 경우 메모리 사용량이 증가합니다.
- bfs dfs 중 하나를 꼭 써야한다는 제약이 없는 문제라면 자기가 편한 방식을 사용하면 된다.
- 배열 vs 객체 사용 지금은 x, y좌표인 걸 알고 있기 때문에 상관없지만 여러가지 데이터가 필요하다면 자기만 알고 있다.
이 코드를 모르는 사람이 본다고 가정하고 구현하라 - 다른 곳으로 이동할 수 있을지 없을지 체크-> 메서드로 빼주는 게 가독성 측면에서 좋다.
재사용성 측면에서도 만약 여러군데에서 사용했을 때 그 부분이 잘못된 걸 깨닫게 됐다면 다른 곳에 작성한 걸 놓칠 수도 있다.
댓글