Language

2470번: 두 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 1,000,00 www.acmicpc.net 해당 문제는 투 포인터 알고리즘으로 해결하였습니다. 두 용액의 합이 0과 가장 근사한 한 쌍을 찾아야 하는 문제입니다. 입력받은 용액의 배열을 정렬을 시키고 왼쪽 인덱스의 값과 오른쪽 인덱스의 값을 더해서 절댓값이 minValue보다 작으면 출력 값(ans1, ans2)과 minValue를 업데이트합니다. 만약 minValue가 0이면 ans1과 ans2를 출력시키고 return 해줍니다. 왼쪽 인덱스의 값과 오른쪽 인덱스의 값..

풀이 과정 해당 문제는 단순한 투 포인터 문제이다. 두 값의 합이 0과 가까운 쌍을 찾으면 끝이다. 1. 주어진 x 배열을 정렬시킨다. 2. 문제에서 수들의 합이 매우 크기 때문에 minV를 매우 큰 값으로 설정하였다. 3. 투 포인터를 사용하기 때문에 0번째 인덱스와 n-1 인덱스부터 시작한다. 4. 오른쪽 인덱스 s와 왼쪽 인덱스 e의 합을 m으로 지정한다. 5. 절댓값 m이 minV보다 작을 경우 minV를 m으로 업데이트해준다. ans를 현재 x [s], x [e]로 업데이트해준다. 6. minV이 0이면 반복문을 종료하고 현재 ans을 출력한다. 7. m 값이 0보다 작을 경우 오른쪽 인덱스를 증가시키고 반대일 경우 왼쪽 인덱스를 감소시킨다. 풀이 코드 n,*x= map(int,open(0).r..

풀이 과정 본 문제는 전형적인 BFS문제이다. 왜냐하면 연결되어 있는 방의 개수를 물어봤기 때문이다. 부가적으로 특이한 요소를 첨가하였다. 각 좌표들 간에 연결되었는지를 15 이하의 값으로 주어져있다. 0~15 (?) 문제에서 언급한 힌트대로 이 문제는 좌표 이동을 비트 마스킹을 해준다. 하지만 비트 마스킹이 익숙하지 않아서,,, 나는 문자열로 표시를 하였다. 물론 하는 방법은 비트 마스킹이랑 똑같다..! "0000" ~ "1111" 맨 왼쪽부터 서북 동남을 의미하고 1은 이동 불가(벽으로 연결)를 의미하고 0은 이동 가능을 의미한다. 1. m*n 만큼 반복문을 돌려서 해당 (i, j) 위치를 방문하지 않을 경우 BFS 탐색을 한다. 2. 현재 위치 값을 bin함수를 이용하여 이진수를 나타내고 크기를 4..

2212번: 센서 첫째 줄에 센서의 개수 N(1 ≤ N ≤ 10,000), 둘째 줄에 집중국의 개수 K(1 ≤ K ≤ 1000)가 주어진다. 셋째 줄에는 N개의 센서의 좌표가 한 개의 정수로 N개 주어진다. 각 좌표 사이에는 빈 칸이 하나 있 www.acmicpc.net 문제 설명은 밑에 링크를 타시고 보시면 됩니다. 😶‍🌫️ [Python][백준 2212][정렬][그리디] 센서 - 컴도리돌이 풀이과정 해당 문제는 좌표를 단순히 정렬시켜서 센서들 간의 거리를 저장하고 정렬하여 n-k까지 합을 구하면 된다. 여기서 n-k까지 합을 구하는 이유를 물어본다면,, 문제를 그리면서 푸는 것을 comdolidol-i.tistory.com import java.io.BufferedReader; import java...

풀이과정 해당 문제는 좌표를 단순히 정렬시켜서 센서들 간의 거리를 저장하고 정렬하여 n-k까지 합을 구하면 된다. 여기서 n-k까지 합을 구하는 이유를 물어본다면,, 문제를 그리면서 푸는 것을 추천한다. 🙄 1. 센서 위치를 정렬시킨다. 2. x의 0번째 인덱스부터 n-1 인덱스까지 다음 좌표까지의 거리를 저장한다. 3. 다음 좌표까지의 거리들을 정렬시킨다. 4. 정렬된 좌표 간의 거리 리스트에서 n-k까지 합을 구하여 출력한다. 풀이 코드 n,k,*x = map(int,open(0).read().split()) ;x.sort() print(sum(sorted([x[i+1] - x[i] for i in range(n-1)])[:n-k]))

풀이과정 해당 문제는 뭔가 일단 규칙성을 찾아야 하게끔 생겨 버렸다. 😶‍🌫️😶‍🌫️ 일단 n이 홀수이면 0인 거 알겠지만, n이 짝수일 때 규칙성을 찾는데 애를 먹었다. 일단 n이 2일 때는 3이다. 그다음 n이 4일 때는 11이다. 근데 여기서 n이 2일 때 경우의 수 각각 2,2이기 때문에 2 * 2에 새로운 모양 2개를 더해준 값이다. 그렇다면 일단 dp [2] * dp [2] + 2라고 표현할 수 있다. 그다음 n이 6일 때는 41이다. dp [4] * dp [2] + dp [2] * 2 + 2 그다음 n이 8일 때는 dp [6] * dp [2] + (dp [4] + dp [2] ) * 2 + 2 그다음 n이 10일 때는 dp [8] * dp [2] + (dp [6] + dp [4] + dp [..

20437번: 문자열 게임 2 첫 번째 문자열에서 3번에서 구한 문자열은 aqua, 4번에서 구한 문자열은 raquator이다. 두 번째 문자열에서는 어떤 문자가 5개 포함된 문자열을 찾을 수 없으므로 -1을 출력한다. www.acmicpc.net 자세한 풀이과정은 다음 링크에 걸어놓았습니다. 물론 파이썬으로 해결해서 코드가 조금 더 간결하고 쉽게 해결했지만, 전체적인 흐름은 똑같습니다. 1. 주어진 문자열을 반복문을 돌려서 해당 문자열이 몇 번째 인덱스에 나왔는지 저장을 합니다. 2. 인덱스 정보가 담긴 문자열 배열을 알파벳의 개수(26)만큼 반복문을 돌립니다. 3. 배열의 크기가 주어진 개수보다 작을 경우 continue 개수를 포함할 경우 인덱스 간에 거리를 구해서 min, max를 업데이트 합니다..

풀이과정 해당 문제는 시간 초과를 걸리 줄 알았는데, 생각보다 쉽게 해결되어서 허무(?)했던 문제였다. (원래 시간 초과 4개 걸리고 해결해야 짜릿한데,,🙄🙄) 1. 입력받은 w를 enumerate로 인덱스 번호(i), 문자열(str)로 열거하여 dictionary(ww)에 문자열의 인덱스를 삽입해준다. 2. 각 알파벳의 인덱스 정보를 담고 있는 ww를 반복문을 다음과 같이 수행한다. 3. 해당 알파벳의 인덱스 리스트를 'str_idx_list'라고 설정하였다. 4. 해당 리스트의 크기가 k보다 작으면, 문제에서 주어진 3,4번 조건을 만족하지 못하기 때문에 continue를 시킨다. 5. len_list는 k개를 포함하는 문자의 문자열 길이를 담는 리스트이다. len_list에 str_idx_list ..