BAEKJOON
1.[백준 10986] 나머지 합 구하기
N의 범위가 10^6까지기 때문에 구간합을 이용한다.합배열 S의 모든 구간을 M으로 나누었을 때 나머지가 0이라면 그 구간은 나누어 떨어진다는 뜻이다.ex) M = 3, S\[0] = 3, S\[1] = 5, S\[2] = 9일 때 S\[0]과 S\[2]는 3으로 나누
2.[백준 1043] 거짓말
Set을 이용한 합집합으로 진실을 아는 사람이 포함되어있는지 확인했다.진실을 아는 사람들의 번호가 주어지고 각 파티에 참여하는 사람들의 번호가 주어진다.각 파티를 순회하면서 진실을 아는 사람이 포함되어있다면, 그 파티에 참여한 사람들을 진실을 아는 사람들 목록에 추가한
3.[백준 1260] DFS와 BFS
문제 접근 Set을 이용한 합집합으로 진실을 아는 사람이 포함되어있는지 확인했다. 진실을 아는 사람들의 번호가 주어지고 각
4.[백준 2178] 미로 탐색
그래프의 좌푯값이 1인 지점은 연결되어 있기 때문에 BFS를 이용하여 최단 거리를 갱신한다. BFS를 구현할 때, \[상, 하, 좌, 우]가 연결되어 있는지 확인한다.인덱스 에러가 나지 않도록 탐색 범위를 정해줘야 한다.
5.[백준 24497] 알고리즘 수업 - 깊이 우선 탐색 1
문제에서 제공한 DFS의 의사코드를 이용한다.가중치는 모두 1이고 무방향 그래프라는 것에 유의한다.인접 정점은 오름차순으로 방문하기때문에 리스트를 정렬해야 한다.
6.[백준 2667] 단지번호붙이기
인접행렬로 구성된 그래프에서 상하좌우를 확인하여 연결되어있는지 확인한다.집(1)을 방문시 방문기록이 없다면, 그 집을 시작으로 BFS를 실행한다.BFS 실행시 집을 방문할 때 마다 개수를 세주면 BFS가 끝날때 단지가 완성된다.단지수를 오름차순으로 정렬하여 출력한다.처
7.[백준 1012] 유기농 배추
배추가 심어진 위치를 알려주기 때문에 배추가 있는 땅과 없는 땅으로 구분해 그래프를 그린다.지렁이가 이동할 수 있는 위치를 BFS로 탐색한다.BFS가 완료되었다면 한 마리의 지렁이가 커버할 수 있는 지역을 모두 확인한 것이기 때문에 BFS를 실행한 횟수가 필요한 지렁이
8.[백준 2606] 바이러스
바이러스는 연결된 컴퓨터에 전파되기 때문에 BFS 또는 DFS를 이용하여 연결된 컴퓨터를 구한다.연결된 컴퓨터를 한 쌍씩 입력받기 때문에 인접 리스트를 만들어 탐색한다.연결된 것을 확인하는 것이 중요하기 때문 1번 컴퓨터를 통해 바이러스에 걸리게 되는 컴퓨터의 수를 구
9.[백준 20529] 가장 가까운 세 사람의 심리적 거리
비둘기 집 원리n개 보다 많은 물건을 n개의 집합에 나누어 넣는다면 적어도 어느 한 집합에는 2개 이상의 물건이 속하게 된다는 내용이 비둘기집의 원리이다.mbti는 총 16개다. 즉 32(16 \* 2)개 를 넘기면 같은 mbti를 가진 학생이 3명이 된다는 말이다.그
10.[백준 18870] 좌표 압축
💡 find()를 이용하면 시간복잡도가 O(n)이 되기 때문에 시간초과가 난다.💡 lower_bound()를 이용하면 이진탐색 기반이기 때문에 O(log n)으로 통과할 수 있다.좌표의 값은 int형의 범위를 초과할 수 있기 때문에 더 큰 타입의 자료형을 사용한다
11.[백준 1253] 좋다
💡 하나씩 비교해보며 찾는다면 좋은 수 하나를 찾는데 드는 시간 복잡도는 O(n²)이 되기 때문에 시간초과가 난다.💡 투 포인터를 이용하면 좋은 수 하나를 찾는데 드는 시간 복잡도는 O(n log n)으로 줄일 수 있다.N개의 수 중에서 어떤 수가 다른 수 두개의
12.[백준 2805] 나무 자르기
💡 N의 범위가 1이상 1,000,000 이하의 정수이기 때문에 시간초과에 유의한다.💡 이분탐색 혹은 매개 변수 탐색을 이용하여 시간복잡도를 O(log n)으로 줄일 수 있다.배열에 주어진 나무들의 길이를 입력하고 매개 변수 탐색을 하기 위해 정렬을 해준다.탐색의