[백준] 기본 탐색 - 기초 문제 (1543, 1568, 1302, 1668, 1236)

1543번 문서 검색

 

◈ 생각해야할 포인트

- 문서의 길이는 최대 2,500이고 단어의 길이는 최대 50로 다루어야할 데이터 양이 적으므로 시간복잡도에 구애받지 않고 문제를 풀면 되겠다.

- 문서의 길이 * 단어의 길이로 모든 경우를 살펴보는 시간복잡도 O(NM)의 프로그램 작성해도 괜찮겠다. 

 

 

 

 

 

 

 

 

1568번 새

 

문제이해 : 새가 14마리가 있을 때 1부터 숫자를 외치는데 1을 외칠 때는 한 마리가 날아가면서 외치고, 2를 외칠 때는 두 마리가 날아가고 하다가 4를 외칠 때에는 10마리가 날아가 4마리 밖에 안남아서 그 다음 수 5를 외칠 수가 없다. 그래서 다시 처음인 1부터 외치면서 1마리, 그 다음에 2마리가 날아가고 남은 한 마리는 다시 1을 외치며 날아가서 총 7번의 횟수를 통해 모든 새가 날아가게 된다. 

 

 

◈ 생각해야할 포인트

- 등차수열로 계산이 되기 때문에 시간복잡도는 O(n^2)이지만 그만큼씩 값을 빼주는 거기 때문에 데이터양이 그 속도로 줄어들면서 사실상 시간복잡도는 √n 루트 n에 가깝다.

 

 

 

 

 

 

 

 

1302번 베스트셀러

 

 

 

◈ 생각해야할 포인트

- 가장 많이 등장한 문자열을 출력하는 문제와 동일하다.

- 등장 여부를 알려고 할 때는 Set() 함수나 Dictionary() 함수를 활용하는데,

- 특히나 등장 횟수를 세야하는 경우에는 Dictionary 자료형을 사용하면 된다.

 

 

 

 

 

 

 

 

 

1668번 트로피 진열

 

 

 

문제이해 : 입력한 개수만큼 트로피의 높이를 알게 되는데 그 트로피들이 일렬로 놓여 있을 때 왼쪽에서 볼 때와 오른쪽에서 볼 때 보이는 트로피의 개수를 구한다.

 

 

◈ 생각해야할 포인트

- 트로피의 개수 N은 최대 50개이므로 시간복잡도에 구애받지 않고 문제를 풀면 되겠다.

 

 

 

 

 

 

 

 

 

 

1236번 성 지키기

 

 

 

 

◈ 생각해야할 포인트

- 행과 열 각각 경비원이 한 명도 없는 줄의 개수를 구한 뒤, 둘 중에 큰 수가 최소로 필요한 경비원 수가 되겠다 !