합승 택시 요금
- 플로이드 와샬 알고리즘
경주로 건설 : bfs
- val queue: Queue = LinkedList() <= 사용 필요
- mutableList.first 후에 mutableList.removeFirst()하는 것보다 queue.poll()이 더 빠름
순위
- 플로이드 와샬과 유사하게 2차원 배열 생성해서 풀이
- a와 b의 승부를 예측할 때 a와 x, x와 b의 승부를 통해 예측 가능한지 파악
- 전체 승부 파악 후 모든 상대와 승부 예측이 가능한 경우의 수 체크
자물쇠와 열쇠
- 자물쇠의 구멍 리스트와 열쇠의 돌기 리스트를 생성한뒤 비교
- 자물쇠와 돌기 리스트를 첫번째와의 간격으로 변경
- 자물쇠의 모든 구멍에 돌기 리스트가 맞으면 열쇠의 돌기가 자물쇠의 돌기와 맞물리는지 확인 (테케 23,25,33 해당)
- 자물쇠의 모든 구멍에 돌기 리스트가 맞지 않으면 열쇠 회전 후 반복
파괴되지 않은 건물
-
누적합 개념을 1차원 -> 2차원
-
x1, y1 부터 x2, y2까지 한번에 바꾸고 싶은경우 누적합 사용
n n 0
n n 0
0 0 0위와 같은 경우 누적합을 사용하면
n 0 -n
0 0 0
-n 0 n으로 계산한뒤 좌 -> 우, 상 -> 하 순으로 누적 계산하면 됨
110 옮기기
- StringBuilder() 사용 필요
표 편집
- 조립은 분해의 역순
- 삭제된 인덱스를 신경쓰지 말고
- (전체 리스트 크기 - 삭제 리스트) 만큼만 'O'를 생성 하고
- 삭제 리스트의 마지막 값에 'X'를 추가해주면 됨
부대복귀
- 1차원 다익스트라, bfs
금과 은 운반하기
- 이분 탐색
- 범위 증가시 min = avg + 1
- 범위 감소시 max = avg
등대 : dfs(queue), stack
- dfs(queue)를 통해 그래프를 탐색하는 리스트를 stack으로 반환
- stack의 pop()을 사용해 역방향 탐색 이용
- 두개의 등대 모두 꺼져있으면 그래프의 위쪽에 위치한 등대 켜기
사라지는 발판 : 재귀 함수 리턴 값 타이밍이 중요
- 재귀의 끝에 도달하면 값을 리턴하는 것을 앞에 배치 시켜야 됨
- 하위 재귀가 특정값(모두 false인지 true인지 등)을 리턴하는지 확인하기 위해서는 재귀 직후에 체크해야 됨 -> 체크 후 for문 밖의 변수에 체크 결과를 저장해야 됨
등산코스 정하기: 다익스트라
- 다익스트라 문제 + 출입구, 산봉우리는 경유하지 않도록 조건 추가
- 다익스트라는 플로이드 와샬과는 달리 모든 경로를 탐색하는 것이 아니라 시작점이 정해져 있음
- 방문하지 않은 노드 중 가장 비용이 적은 노드를 선택 -> 그곳을 경유하였을 때 최소 비용으로 업데이트 -> 반복
- PriorityQueue 사용 필요 <= 가장 비용이 적은 노드를 알기위해
- 오름차순
1) PriorityQueue()
2) PriorityQueue() { a, b -> a - b } - 내림차순
1) PriorityQueue(reverseOrder())
2) PriorityQueue() { a, b -> b - a } - graph(map) 생성시 연결 번호 및 비용을 함께 추가해야 함
ex) Pair(연결 번호, 비용)
코딩 테스트 공부 : 동적 계획법
- 피보나치 수열을 생각하면 됨 => 큰 범위의 문제를 작은 범위의 여러 문제로 쪼개서 푸는 방식
- queue를 통해 최초 시작점 부터 범위를 증가시키면서 해결
- 같은 위치의 값이 갱신 되었을땐 다시 탐색
호텔 방 배정
- mutableMap을 통한 노드 갱신
무지의 먹방 라이브
- 정렬 후 순차적으로 반복해야됨
- 횟수와 인덱스를 같이 저장 후 정렬하는 것이 포인트
올바른 괄호의 갯수 : 카탈란 수
- 공식
- 분자 = 2n!
- 분모 = n! x (n + 1)!
뒤에 있는 큰 수 찾기
- 자신의 뒤에 나오는 자신보다 큰 수로 변환
- for (i in lastIndex downTo 1) 으로 반복문 실행
- Stack을 사용해 자신의 수보다 작거나 같은 pop 시키기
- 큰 수가 나오면 peek로 값을 answer 배열에 입력
- 자신의 값을 Stack에 추가
안드로이드 개발 공부 블로그