.png&blockId=5f7573ad-6867-4d59-999e-722aced04aeb)
2206 벽 부수고 이동하기
한번의 BFS탐색으로 변경하더라도 queue 배열로 할 시 시간 초과나므로 연결리스트로 구현한 queue로 풀이해야 함
7576 토마토
이것도 역시 시간초과가 발생하는 queue를 사용한 bfs다.
7569 토마토
9466 텀 프로젝트
Cycle을 찾는 문제
2636 치즈
while문을 통해 미리 구해놓은 total에 다다를 떄까지 time과 result를 업데이트하면 된다.
BFS에서는 공기일 때만 방문하도록 조건을 준다.
2583 영역 구하기
받은 직사각형의 좌표를 가지고 반전시켜 배열의 좌표에 매핑시킨다.(규칙을 발견하면 됨)
BFS탐색은 직사각형에 포함되지 않으면서 방문한 적 없는 좌표다. 이것은 무조건 답안에 포함될 것이다. 분리된 영역의 넓이에 해당되기 때문이다.(즉, 큐에 들어온 좌표들은 분리된 영역의 넓이에 포함된다.
외부의 visit 배열을 통해 확실하게 들어가도 되는 좌표라고 판단되면 이것은 result로 추가될 좌표가 되고 여기서 상하좌우를 방문해보면서 check와 visit 모두를 1로 바꾼다.(다음 BFS에 이 좌표가 들어올 일은 없게 한다음 큐에 집어 넣는다.)
이런 식으로 발견된 0을 따라 막힐 때까지 check 배열에 의존해 탐색을 한다음은 다시 외부의 BFS를 호출시켜야 한다. 0이 뭉쳐있는 분리된 영역이기 떄문이다.
이때는 함수 내의 일시적인 방문 배열인 check이 아닌 외부의 visit 배열에 의존할 수 밖에 없다.
2293 동전 1
Node.js는 아무리 해도 안 풀림. Java로 해결
11047 동전 0
큰 액수부터 나눠내려간다. quot와 rem를 밖에 선언해두고 제때 업데이트해주면 된다.
1931 회의실 배정
현 회의의 끝나는 시간과 다음 회의의 시작하는 시간이 같거나 더 커야한다. 그래야 이어서 회의를 시킬 수가 있어 최대 개수가 된다.
이 규칙대로 검사하기 위해서 sort가 중요한데, 정렬 기준은 끝나는 시간을 기준으로 한다. 빨리 끝나는 회의일수록 다음 회의를 시작할 수 있을 가능성이 높기 때문이다.
2217 로프
로프의 개수를 줄이면서 계산하는 것은 최소중량이 높아지기 때문이다.
2869 달팽이는 올라가고 싶다
나누기만 해도 구할 수 있다는 규칙을 찾는다. 반복문은 시간초과.
2512 예산
총 예산이 M이하가 되게 하는 상한액을 정하는 것이다. 구하고자 하는 상한액을 mid로 정하면 된다.
적어도 가장 큰 예산보다는 같거나 작을 것이므로 budget[N-1]을 준 다음 범위를 좁혀가면서 mid를 추적한다.
2110 공유기 설치
Binary Search 집들간의 거리를 변경된 mid가 적합한지 매번 검사한 뒤 그 누적된 값을 보고 조건에 따라 업데이트
1927 최소 힙
11279 최대 힙
11286 절댓값 힙
1715 카드 정렬하기
우선순위큐를 사용해 합을 다시한번 넣어서 재사용하는 방식
1655 가운데를 말해요
시간초과) 최대힙과 최소힙을 두고 최대힙의 top을 peek해서 그 값을 중간값으로 판단한다.
1202 보석 도둑
java로 풀리는 로직을 maxheap을 직접 구현해 js로 제출하게 되면 실패한다.
9576 책 나눠주기
1.
b를 기준으로 오름차순으로 정렬한다.
2.
a,b를 리스트에서 꺼낸다.
3.
a부터 b까지 반복을 돌리는데, books[i]번째 책을 안나눠주었으면 True로 바꾸고 cnt변수를 1증가 시키고 break한다.
4.
1 ~ 3을 반복한다.
13305 주유소
n의 최댓값이 10^5, 거리와 가격은 10^9로 매우 크므로, BigInt를 사용
1826 연료 채우기
python
1422 숫자의 신
python
