https://www.acmicpc.net/problem/20366 20366번: 같이 눈사람 만들래? 높이가 (2, 5), (3, 5)로 구성된 눈사람 둘을 만드는 것이 최적의 경우 중 하나이다. |7-8| = 1 다른 경우로는 (2, 9), (5, 5)로 두 눈사람을 만드는 경우가 있다. |11-10| = 1 www.acmicpc.net # 랜덤으로 4개를 뽑아서 비교하면 nC4이므로 당연히 시간초과이다. 따라서 '세 용액'문제와 비슷하게, 미리 기준점을 하나 설정하고 나머지 2개의 원소를 '투 포인터' 알고리즘을 사용해서 비교하며 풀었다. 1. 우선 i와 j를 설정한다. (i 와 j의 차이는 3이상) -> 그래야 최소 i와 j사이에 원소 2개이상 존재 2. 기준점인 눈사람 한개를 fix로 설정 (s..
https://www.acmicpc.net/problem/3187 3187번: 양치기 꿍 입력의 첫 번째 줄에는 각각 영역의 세로와 가로의 길이를 나타내는 두 개의 정수 R, C (3 ≤ R, C ≤ 250)가 주어진다. 다음 각 R줄에는 C개의 문자가 주어지며 이들은 위에서 설명한 기호들이다. www.acmicpc.net 1. 영역을 m에 입력받고, 반복문을 돌며 현재 칸이 '#'이 아니라면 bfs함수를 실행한다. * bfs함수: 양의 수를 저장할 변수 sheep과 늑대 수를 저장할 변수 wolf를 선언해준다. 현재 칸이 v이면 wolf += 1, 현재 칸이 k이면 sheep += 1 q에 넣고 bfs를 돌리는데, 다음칸이 맵 밖을 벗어나지 않고 '#'이 아니라면 (nx, ny)를 방문처리해주고, (n..
https://www.acmicpc.net/problem/2473 2473번: 세 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 3 이상 5,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 www.acmicpc.net # 저번주에 풀었던 '두 용액'에서 한번 더 응용한 문제이다. # 당연히 전체 용액 중 3개를 뽑아 다 구하는 NC3풀이는 안되고 '두 용액' 풀이처럼 투 포인터를 사용하였다. # N이 5000이하여서 반복문을 돌며 용액을 하나 고르고 나머지 N-1개의 용액에서 투 포인터를 사용하여 답을 구했다. 이러면 처음에 용액을 고르는데 O(N), 투 포인터를 사용하면 O(N)이어서 O..
https://www.acmicpc.net/problem/16916 16916번: 부분 문자열 첫째 줄에 문자열 S, 둘째 줄에 문자열 P가 주어진다. 두 문자열은 빈 문자열이 아니며, 길이는 100만을 넘지 않는다. 또, 알파벳 소문자로만 이루어져 있다. www.acmicpc.net # KMP알고리즘을 사용하여 풀었다. # 아직 정확히 이해하진 못해서, 나중에 이해한 뒤 다시 정리할 예정이다. def KMP(): table = make_table() j = 0 for i in range(len(s)): while j > 0 and s[i] != p[j]: j = table[j - 1] if s[i] == p[j]: if j == len(p)-1: return True else: j += 1 return..
# 갑자기 프로그래머스에서 새로운 컨텐츠를 실시한다고 메일이 와서 들어가 보았다. # 이번 주 부터 프로그래머스에서 새로 실시하는 Weekly Challenge이다. 그냥 심심풀이로 매주 한 문제씩 풀면 좋을 것 같다. # 1주차 https://programmers.co.kr/learn/courses/30/lessons/82612?language=python3 코딩테스트 연습 - 1주차 새로 생긴 놀이기구는 인기가 매우 많아 줄이 끊이질 않습니다. 이 놀이기구의 원래 이용료는 price원 인데, 놀이기구를 N 번 째 이용한다면 원래 이용료의 N배를 받기로 하였습니다. 즉, 처음 이 programmers.co.kr def solution(price, money, count): answer = price *..
# 요즘 스터디에서 이분탐색을 주제로 한 문제들을 풀다 내가 풀이 하고 있는 방식이 '이분탐색'이 아니라는 것을 깨달았다. 아예 다른 것은 아니지만, 엄밀히 따지자면 '매개변수 탐색'이라는 분류가 따로 존재했다. # 이분탐색은 '정렬된 배열'에서 target의 존재여부와 존재한다면 위치를 알려주는 알고리즘이다. 우리가 찾는 target이 배열 안에 존재한다면, 그 위치를 알려준다는 것이다. # 하지만, 'target과 정확히 일치하는 값' 이 존재하지 않는다면?? -> 우리는 parametric search를 통해 최적화된 값을 찾을 수 있다. # Parametric Search는 최적화 문제를 결정 문제로 풀 수 있는 기술이다. '최적화 문제'니 '결정 문제'니 다 처음 들어보는 말이어서 어려울 수 있..
https://www.acmicpc.net/problem/2470 2470번: 두 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 1,000,00 www.acmicpc.net # 투 포인터 문제중에는 대표적인 문제로 잘 알려져 있는 문제이다. # 이분탐색을 사용해서 풀 수도 있다는데..(그건 잘 모르겠고) 1. nums에 용액들의 특성값을 입력받고 오름차순 정렬해준다. 두 용액의 최대 차이는 10억 - (-10억) = 20억이므로, tmp를 20억+1로 설정해준다. 2. 우선 nums배열을 반복문으로 돌며 용액이 모두 양수이면 가장 작..
https://www.acmicpc.net/problem/1477 1477번: 휴게소 세우기 첫째 줄에 현재 휴게소의 개수 N, 더 지으려고 하는 휴게소의 개수 M, 고속도로의 길이 L이 주어진다. N은 100보다 작거나 같으며, M도 100보다 작거나 같다. L은 100보다 크거나 같고, 1000보다 작거나 www.acmicpc.net 1. 고속도로 끝과 이미 설치된 곳에 휴게소를 세우지 못하므로 휴게소 위치를 입력받아 rest배열에 넣은다음 처음과 끝 위치도 추가해준 뒤 정렬해준다. 2. count함수: 휴게소가 세워진 위치 사이를 이분탐색을 통해 구한 mid값으로 나눈 값들을 cnt에 저장한다. cnt가 M보다 같거나 작으면 True를 리턴, M보다 크면 False를 리턴해준다. 3. lo = 0,..
모르는 사이에 조금씩 조금씩..
