특강 2주차! 🟧🟨🟩🟦
병사관리 😲
문제를 꼼꼼하게 읽고 파악하는 것이 중요
호출 횟수를 비교하여 어디에 유리하게 로직을 구현해야 할 지 파악!
특이한 부분을 찾아야 한다! 병사관리 문제에 경우 읽어보면
점수가 5점, 소속팀도 5팀까지 밖에 없다!
bestSoldier() 함수의 호출 횟수는 100 이하!
이런 힌트를 조합해서 여기에 맞게 로직을 구현!!!
가장 중요한 로직 !! 🟧
점수마다 팀마다 리스트로 구현한다..!!
5개가 한계니깐 가능한 트릭!
점수이동을 O(1) 로 가능하게 한다..!!
두번째 방법!! 🟧
단방향 연결 리스트는 삭제가 힘들다!!!
삭제가 있다면 양방향으로 연결하자!
v2 코드는 양방향으로 삭제를 간단히 구현하는데
v1은 삭제를 하는 테크닉
버전을 따로 기억하는 방식
버전을 기억하고 버전 관리를 통해 삭제와 업데이트를 간단히 구현 가능!!
연결리스트를 사용할 때 활용가능 할 것 같다!!
트리 🔔
전위 중위 후위 순회
완전 이진 트리 🟨
규칙을 이용한 1차원 배열 선언 후 활용 => 앞으로 가장 많이 활용할 것임
최저 공통 조상 🟨
LCA Lowest Common Ancient
가장 간단한 방법
x의 조상 , y의 조상을 발견해서 같은 조상 중 가장 빠른 조상
이걸 좀만 더 똑똑하게 생각을 해보자
x의 조상이랑 y의 조상을 루트부터 나열을 해보자!!
루트는 무조건 둘의 같은 조상이다! 그래서 나열을 해서 달라지는 시점이 공통조상!!
그래프 🔔
행렬 🟩
메모리 낭비 단점
리스트 🟩
인접행렬의 최대 장점인 어떠한 점과 점에 대한 연결 여부를 판단 하는 속도가 느림
생각해볼 문제 🤔
그래프가 주어지는데 삼각형의 갯수를 찾아라
삼각관계 서로다른 3 점이 이어져 있는지
정점 5천개, 간선 5천개
풀이
간선 선택 정점 선택 후 이어져 있는 지 파악
간선 선택하는 알고리즘이 간선 배열을 따로 파야함 + 이어져있는지 파악은 행렬로
DFS BFS 🟩
얘들이 왜 인접리스트 쓸까?
연결된 노드를 확인해서 들가야 하는데 그 탐색에서 빨라서
인접행렬은 그 행을 전부 다 탐색해서 들어가야하기 때문에 느림!
파핑파핑🔔
배워갈 점 🟦
모듈이 잘 쪼개서 재사용성을 확보해야 코드를 잘 적을
4방 8방 탐색 하는 dr dc 코드
문자열 입력받는 str.charAt(j) == '.'
시간복잡도 계산 🟦
탐색 성공 칸 개수
❓❔🟥🟧🟨🟩🟦🟪🟫⬜⬛🫢🔔😎😊🤔
정말 좋은 수업을 들었고 많이 배웠다 하지만 이렇게 머리로 아는 건 별로 나에게 크게 도움되지 않는다 이 수업들을 직접 쳐보면서 내 걸로 만들어야 한다! 더 열심히 해보자!
숙제
연결 리스트 구현 마스터 후
병사관리 코드 완벽 습득 후 구현 실습
중위순회, 공통조상, 파핑파핑 까지 코드보고 이해하고
안보고 직접 구현 합시당
