live the life you love

www.acmicpc.net/problem/14888 14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, www.acmicpc.net 모든 경우의 수를 전부 확인해서 원하는 답을 구하는 전형적인 완전탐색 문제였다 숫자의 위치는 고정되어있고 모든 연산자를 사용해야 하므로 연산자의 순서만 정해주면된다. 사용 할 수 있는 연산자의 순서를 정할 때는 순열을 사용한다. 연산자가 최대 10개까지밖에 없으므로 파이썬 내장 라이브러리를 활용하여 풀었다. 주의할 점은 나누기 연산의 경우 음수로 나눠지는 ..

www.acmicpc.net/problem/15655 15655번: N과 M (6) N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다. N개의 자연수 중에서 M개를 고른 수열 www.acmicpc.net 조합을 구하는 문제이다. 순열과 달리, 사용했던 원소를 체크해주는게 관건이다. # 조합 n, m = map(int, input().split()) data = list(map(int, input().split())) data.sort() result = [] checked = [False]*n def dfs(idx, count): if count == m: print(*result) return for..

www.acmicpc.net/problem/15654 15654번: N과 M (5) N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다. N개의 자연수 중에서 M개를 고른 수열 www.acmicpc.net 순열을 구하는 문제이다. N과 M(1)이 순열이었는데, 이와 다른점은 N과 M(5)의 경우 순열을 만들어야 할 숫자가 따로 주어진다는 점이다. 문제 조건에서 오름차순으로 출력하라고 했기 때문에 입력받은 숫자를 정렬해주기만 하면, 일반적인 순열을 구하는 것과 동일하다 이번에도 백트래킹으로 풀었다. n, m = map(int, input().split()) data = list(map(int, input(..

www.acmicpc.net/problem/15652 15652번: N과 M (4) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net N과 M(4)는 중복 조합을 구하는 문제이다. 이번에도 내장 라이브러리를 사용하지 않고 백트래킹 방식으로 직접 구현하였다. n, m = map(int, input().split()) result = [] def dfs(idx, count): if count == m: print(*result) return for i in range(idx, n): result.append(i+1) dfs(i, count+1)..

www.acmicpc.net/problem/15651 15651번: N과 M (3) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 백트래킹을 연습하기 위해 내장 함수를 사용하지 않고 직접 함수를 구현해서 문제를 풀었다 N과 M(3)는 중복순열을 구하는 문제이다. 순열을 구하는 것과 크게 차이는 없고 중복된 값을 따로 체크하지 않기 때문에 따로 체크할 부분은 없다. 소스코드 n, m = map(int, input().split()) result = [] def dfs(count): if count == m: print(*result) re..

www.acmicpc.net/problem/2467 2467번: 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 오름차순으로 입력되며, 이 수들은 모두 - www.acmicpc.net 이전의 문제 두 용액(paris-in-the-rain.tistory.com/59)에서는 절댓값 대소 비교로 문제를 풀었다. 두 문제의 차이는 정렬 여부인데, 두 용액 문제는 정렬이 안되어 있고, 이 문제는 정렬이 되어있다. 이 문제는 투포인터를 활용했다. 포인터의 시작점을 맨 처음 인덱스(p1), 맨 끝 인덱스(p2)로 두었다. 해당 인덱스의 숫자를 더하여 값을 확인한다. 두 숫자를 더해서 0에 가까운 값..

www.acmicpc.net/problem/19238 19238번: 스타트 택시 첫 줄에 N, M, 그리고 초기 연료의 양이 주어진다. (2 ≤ N ≤ 20, 1 ≤ M ≤ N2, 1 ≤ 초기 연료 ≤ 500,000) 연료는 무한히 많이 담을 수 있기 때문에, 초기 연료의 양을 넘어서 충전될 수도 있다. 다 www.acmicpc.net 구현사항만 잘 지키면 되는 전형적인 시뮬레이션 문제였다. 손님을 태우러 택시가 가는 것과, 손님을 태우고 목적지로 가는 것은 같은 방식으로 구현을 할 수 있으므로 flag 변수를 통해 1개의 함수로 처리했다. 문제해결 현재 손님의 위치, 목적지를 입력받고 각각 다른 배열에 저장한다. 비교함수를 만들어 문제의 조건을 처리한다. 가장 가까운 승객 / 행 번호 작은 승객 / 열..

www.acmicpc.net/problem/16236 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가�� www.acmicpc.net 문제 조건을 잘 읽고 그대로 구현하면 되는 문제이다. 구현 자체는 쉬운데, 문제를 제대로 안읽어서 놓친 조건과 문제에서 정보를 안준 것이 하나 있어서 좀 오래 걸렸다. 문제 조건을 요약하면 아래와 같다. 아기 상어의 이동 자신의 크기보다 큰 물고기가 있는 칸은 지나갈 수 없음 나머지 칸은 모두 지나갈 수 있다. 물고기 먹기 아기 상어는 자신의 크기보다 작은 물고기만 먹을 수 있다. 크기가 같은 물고기..

www.acmicpc.net/problem/2470 2470번: 두 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 1,000,00 www.acmicpc.net 처음에는 산성, 알칼리 용액을 나눠서 계산하다 보니 계속 틀려서 블로그를 참고하여 풀었다. 투 포인터를 활용해서 풀려고 했는데, 풀고나니 이 문제는 절댓값을 활용해서 푸는 것이 더 효율적이라고 생각한다. 기존 접근 방식(오답) 산성 용액과 알칼리 용액을 나눠서 저장 후 정렬한다 알칼리 용액만 있는 경우, 산성 용액만 있는 경우 각 배열의 첫번째, 두번째 원소의 값이 최솟값이므로..

www.acmicpc.net/problem/12757 12757번: 전설의 JBNU 첫 줄에는 초기 데이터의 개수인 \(N(1 \le N \le 100,000)\) 과 명령 횟수인 \(M(1 \le M \le 100,000)\), 가장 근접한 Key까지의 거리의 제한인 \(K(1 \le K \le 10,000)\)가 주어진다. 입력의 둘째 줄부터 N개의 줄에 www.acmicpc.net map과 이분탐색을 활용해서 조건에 맞게 푸는 문제이다. 8번의 시도 끝에 풀었다. 문제 해결 문제를 읽어보면 다음과 같은 조건이 있다. 1 Key Value : 해당 Key와 Value를 가진 데이터를 추가한다. Key가 이미 존재하는 입력은 주어지지 않는다. 2 Key Value : 해당 Key로 검색된 데이터를 Va..