백준99 [백준] 21608 - 상어 초등학교 (Python) 문제 출처 : www.acmicpc.net/problem/21608 21608번: 상어 초등학교 상어 초등학교에는 교실이 하나 있고, 교실은 N×N 크기의 격자로 나타낼 수 있다. 학교에 다니는 학생의 수는 N2명이다. 오늘은 모든 학생의 자리를 정하는 날이다. 학생은 1번부터 N2번까지 번호 www.acmicpc.net 문제 풀이 : 삼성전자 2021년도 상반기 오전 문제중 첫번째 문제이다. 삼성전자의 기출문제를 보았다면 대부분 BFS,DFS + 구현 문제로 이루어져 있는 것을 알 수 있다. 때문에 보통 필자는 삼성전자의 문제를 풀땐 어떤 부분들을 구현해야하는지 나누는걸 첫번째로 한다. 요즘 추세로는 구현해야하는 것들을 문제에서 친절하게 주어주는 경우도 많다. 때문에 문제를 잘 읽어보는 것이 굉장히 중.. 2021. 5. 10. [백준] 2110 - 공유기 설치 (Python) 문제 출처: www.acmicpc.net/problem/2110 2110번: 공유기 설치 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 www.acmicpc.net 문제 풀이 : 앞서 본 이분탐색과 같은 문제이다. 이런 문제류에서 바뀌는 부분은 찾는 특정값을 비교할때 사용되는 결과값을 구하는 부분인데 여기서는 아마 gap을 구하는 부분만 신경 써주면 될 것이다. 보통 for문으로 구하니까 복잡하지 않은 이분탐색 문제에선 while문 안에 있는 for문을 신경써서 보면 문제가 쉽게 이해가 된다. n, c = m.. 2021. 4. 9. [백준] 11286 - 절대값 힙 (Python) 문제 출처 : www.acmicpc.net/problem/11286 11286번: 절댓값 힙 첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 0이 아니라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net 문제 풀이: 기본 라이브러리에 있는 heap 모듈을 사용했다. abs_h에는 절대값만 넣었다. 이건 최소힙으로 사용된다. h_dict은 dict 형태로 key값에는 주어진 값의 절대값을 넣고 , value에는 값 자체를 넣는다. value에 넣은 다음엔 해당 key값의 value들만 sort한다. 이후 문제에 주어진 대로 연산을 진행한다. 0이 아닌 값이 들어오면 abs_h에.. 2021. 4. 9. [백준] 2512 - 예산 (Python) 문제 출처 : www.acmicpc.net/problem/2512 2512번: 예산 첫째 줄에는 지방의 수를 의미하는 정수 N이 주어진다. N은 3 이상 10,000 이하이다. 다음 줄에는 각 지방의 예산요청을 표현하는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 값들은 모두 1 이상 www.acmicpc.net 문제 풀이 : 특정값을 찾을때까지 이분 탐색을 계속 시행하면 된다. 이경우엔 우리가 정하고 있는 어떤 값 보다 예산이 많으면 그 값만큼으로 짜른다는 조건이 있는데 이부분만 잘 처리해주면 정답을 쉽게 구할 수 있다. 원리에 대해서 생각해보면 가장 작은 예산인 1원을 left로 두고 주어진 값중에 가장 큰 값인 max값을 right두고 탐색을 시작한다. 기준값을 토대로 예산을 정한뒤에 계산된 예.. 2021. 4. 9. 이전 1 2 3 4 5 6 ··· 25 다음 반응형
