정리

백준 1251번: 단어 나누기 1251번: 단어 나누기 알파벳 소문자로 이루어진 단어를 가지고 아래와 같은 과정을 해 보려고 한다. www.acmicpc.net - 그리디 알고리즘을 활용하여 품. 세 단어로 쪼갤 수 있는 경우의 수를 모두 실행하여 그 중 사전순으로 가장 앞서는 단어를 출력함 이중 for문을 활용하여 단어를 세 단어로 나눈다(아래 코드에서 i와 j가 세 단어로 나누는 일종의 경계선). 나눈 뒤에 문제처럼 뒤집어 준다. 이는 reverse()를 활용한다 뒤집은 세 단어를 합한 뒤에 tmp 리스트에 저장한다 tmp 리스트에는 세 단어가 따로 저장 돼 있으므로 join()을 통해 하나의 단어로 만든 뒤에 sort한다 가장 처음에 있는 단어가 정답이다 아래는 파이썬 코드

백준 1654번: 랜선 자르기 1654번: 랜선 자르기 집에서 시간을 보내던 오영식은 박성원의 부름을 받고 급히 달려왔다. 박성원이 캠프 때 쓸 N개의 랜선을 만들어야 하는데 너무 바빠서 영식이에게 도움을 청했다. www.acmicpc.net - 1789번: 수들의 합 문제와 매우 유사한 문제이다. 마찬가지로 이분탐색으로 접근하면 된다. start = 0, end = 2147483648(2^31 - 1) 으로 초기화한다. start가 end보다 작거나 같을 때까지 while문을 돌린다 mid = (start + end) // 2 rep은 각 랜선을 mid 길이만큼 잘랐을 때 나오는 랜선의 개수이다. for문을 통해서 long 리스트에 저장된 랜선들을 mid로 나눴을 때의 몫을 구한다 rep이 n보다 크거..

백준 1789번: 수들의 합 1789번: 수들의 합 서로 다른 N개의 자연수의 합이 S라고 한다. S를 알 때, 자연수 N의 최댓값은 얼마일까? www.acmicpc.net - 이분 탐색을 활용하여 풀면 되는 전형적인 문제이다. start = 1, end = s(입력받은 수) mid = (start + end) // 2 만약 (mid * (mid + 1) // 2) 가 s보다 작거나 같으면 answer에 mid를 저장하고 이분탐색을 계속 이어 나간다. 참고로, 여기서 (mid * (mid + 1) // 2) 는 1부터 mid까지의 합이다. 만약 (mid * (mid + 1) // 2) 가 s보다 크면 end = mid - 1 로 하여 mid 값을 줄인다. start가 end보다 작거나 같을 때까지 whi..

백준 2493번: 탑 2493번: 탑 KOI 통신연구소는 레이저를 이용한 새로운 비밀 통신 시스템 개발을 위한 실험을 하고 있다. 실험을 위하여 일직선 위에 N개의 높이가 서로 다른 탑을 수평 직선의 왼쪽부터 오른쪽 방향으로 차례로 세우고, 각 탑의 꼭대기에 레이저 송신기를 설치하였다. 모든 탑의 레이저 송신기는 레이저 신호를 지표면과 평행하게 수평 직선의 왼쪽 방향으로 발사하고, 탑의 기둥 모두에는 레이저 신호를 수신하는 장치가 설치되어 있다. 하나의 탑에서 발사된 레이저 신호는 가장 먼저 만나는 단 하나의 탑에서만 수신이 가능하다. www.acmicpc.net - 배열과 스택을 사용하여 풀었다. height배열에 빌딩의 높이를 저장한다. height[i] > height[i-1] 일 경우 (i = N..

백준 14488번: 준오는 급식충이야!! 14488번: 준오는 급식충이야!! 심술쟁이 해커 임준오(동탄 주민)는 오늘도 점심시간을 기다리고 있다. 준오와 친구들은 매일 복도 어딘가의 한 지점에 모여서 함께 밥을 먹으러 간다. 선린의 복도는 직선형으로 되어있고, 준오와 친구들은 이 복도 어딘가에 위치한 교실에서 종이 치기만을 기다리고 있다.‘띵~ 디딩~ 띵디딩디딩~’. www.acmicpc.net 각 좌표에서 이동할 수 있는 범위를 구한 뒤, 모든 데이터의 교집합이 있으면 1을 출력하고 교집합이 없으면 0을 출력한다. - 다음 예제를 3 2.5 1 7 5 2 1 1 을 살펴보자. 1에서는 2.5초 동안 [-4, 6] 사이를 이동할 수 있다. 마찬가지로 7과 5에서는 각각 [4.5, 9.5], [2.5, 7..

백준 2109번: 순회강연 2109번: 순회강연 문제 한 저명한 학자에게 n(0≤n≤10,000)개의 대학에서 강연 요청을 해 왔다. 각 대학에서는 d(1≤d≤10,000)일 안에 와서 강연을 해 주면 p(1≤p≤10,000)만큼의 강연료를 지불하겠다고 알려왔다. 각 대학에서 제시하는 d와 p값은 서로 다를 수도 있다. 이 학자는 이를 바탕으로, 가장 많은 돈을 벌 수 있도록 순회강연을 하려 한다. 강연의 특성상, 이 학자는 하루에 최대 한 곳에서만 강연을 할 수 있다. www.acmicpc.net - 정렬과 그리디 알고리즘을 활용하는 문제이다. - 2차원 배열, 정렬, 우선순위 큐를 통해 아래로 같은 방법 같이 문제를 해결할 수 있다. 먼저 a[N][2], 2차열 배열을 만든 후에 입력을 받는다. a배..

백준 1461번: 도서관 - 정렬과 그리디 알고리즘을 활용한다. - 예제로 나온 7 2 -37 2 -6 -39 -29 11 -28 를 살펴보자. 좌표를 음수와 양수로 나누어 서로 다른 LinkedList에 저장한다. LinkedList를 내림차순으로 정렬하면 위의 사진처럼 될 것이다. (-39) 좌표는 원점으로부터 제일 먼 곳이므로 제일 마지막에 가야 된다. 왜냐하면 마지막에는 책을 가져다 놓고 다시 원점으로 돌아올 필요가 없기 때문이다. 따라서 두 LinkedList의 0번째 인덱스의 값을 비교하여 절댓값이 더 큰 좌표는 편도 거리만 계산한다. 이 때 -39에 가면서 -37에 들렸다가 가야 된다. 따라서 해당 LinkedList(여기서는 A LinkedList)를 m-1번 poll() 해 준다. 그러면..

백준 2473번: 세 용액 - 정렬과 투 포인터를 활용한 문제입니다. 용액의 값을 저장한 리스트를 오름차순으로 정렬합니다. tmp를 inf로 선언하고 세 용액의 합이 0에 더 가까우면 세 용액의 합을 tmp에 저장합니다. 기준점 i 를 잡습니다. left = i + 1, right = n - 1 로 투포인터를 잡습니다. liquid[i] + liquid[left] + liquid[right], 세 용액을 더한 값을 sum으로 합니다. sum의 절댓값이 tmp의 절댓값보다 작으면 현재의 세 용액의 합이 0에 더 가까운 것이므로 tmp의 값을 sum으로 해줍니다. i) sum 0 - sum이 0보다 크..

백준 2470번: 두 용액 - 리스트에 용액들의 특성값을 입력합니다. - 리스트를 오름차순으로 정렬합니다. - left = 0, right = N - 1로 설정하고 이분탐색을 위해 left < right 일 때까지 while문을 반복합니다. i ) 두 용액의 특성값의 합이 0인 경우 - while문을 break하고 결과를 출력합니다. ii) 두 용액의 특성값의 합이 음수인 경우 - 음의 특성값의 절댓값이 양의 특성값의 절댓값보다 크기 때문에 left += 1 을 통해 두 용액의 특성값의 합이 0에 가까워 질 수 있도록 합니다. iii) 두 용액의 특성값의 합이 양수인 경우 - 양의 특성값의 절댓값이 음의 특성값의 절댓값보다 크기 때문에 right -= 1를 통해 두 용액의 특성값의 합이 0에 가까워질 수..

백준 1946번: 신입 사원 - 정렬을 사용하는 문제입니다. - 지원자들의 점수를 입력 받은 뒤 서류심사 성적 순위를 오름차순으로 정렬합니다. - 서류심사 성적을 1등 한 지원자의 면접 성적 순위를 기준(pivot)으로 삼습니다. - for문을 통해 나머지 지원자들의 면접 성적 순위와 비교합니다. 만약 i번째 지원자의 면접 성적 순위가 pivot보다 작다면(등수가 높다면) 합격자의 인원을 추가하고 pivot을 i번째 지원자의 면접 성적 순위로 바꿉니다.