![]()
https://www.acmicpc.net/problem/2467 2467번: 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 오름차순으로 입력되며, 이 수들은 모두 - www.acmicpc.net 문제 풀이 첫번째 줄에는 전체 용액의 수를 입력으로 받고, 두번째 줄은 각 용액의 특성값을 받아 liq라는 리스트를 생성한다. liq의 값들은 정렬된 순서로 주어졌기 때문에 두 용액의 합이 0에 가까운 정도를 구하기 위해서 투 포인터를 이용한다. 가장 작은 값과 가장 큰 값부터 시작해서 점차 안쪽의 용액 특성값의 합을 구하는 방식으로, 이를 위해 p1은 liq의 앞부분에서, p2는 liq의 ..
문제 링크 문제 하나 이상의 연속된 소수의 합으로 나타낼 수 있는 자연수들이 있다. 몇 가지 자연수의 예를 들어 보면 다음과 같다. 3 : 3 (한 가지) 41 : 2+3+5+7+11+13 = 11+13+17 = 41 (세 가지) 53 : 5+7+11+13+17 = 53 (두 가지) 하지만 연속된 소수의 합으로 나타낼 수 없는 자연수들도 있는데, 20이 그 예이다. 7+13을 계산하면 20이 되기는 하나 7과 13이 연속이 아니기에 적합한 표현이 아니다. 또한 한 소수는 반드시 한 번만 덧셈에 사용될 수 있기 때문에, 3+5+5+7과 같은 표현도 적합하지 않다. 자연수가 주어졌을 때, 이 자연수를 연속된 소수의 합으로 나타낼 수 있는 경우의 수를 구하는 프로그램을 작성하시오. 첫째 줄에 자연수 N을 연속..
링크 https://www.acmicpc.net/problem/14465 14465번: 소가 길을 건너간 이유 5 첫 줄에 N, K, B (1 ≤ B,K ≤ N)가 주어진다. 그 다음 B줄에는 고장난 신호등의 번호가 하나씩 주어진다. www.acmicpc.net 풀이 과정 1 (실패) 처음 문제를 풀 때에는 벡터에 고장난 신호등의 리스트를 집어넣고, sort함수로 정렬해서 해당 신호등을 고쳤을 때 연속된 신호등의 개수가 K개 이상인지 확인하는 방식으로 문제를 풀었다. 하지만 그러다 보니 인덱싱의 문제도 있고, 무엇보다도 100%에서 계속해서 오답처리가 돼서 결국 방법을 바꿨다. 우선은 처음 했던 방식을 설명해 보겠다. cont: 연속된 신호등의 개수 num: 고쳐야 하는 신호등의 개수 min: 현재 가장..
링크 https://www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 풀이 작년에 dp 공부를 처음하면서 풀지 못했다가 다시 도전해서 푼 문제이다. 최장 공통 부분 수열, 최장 공통 부분 문자열이 다른 것으로 알고 있는데 다음에는 예전에 심심해서 찾아보다가 발견한 최장 공통 부분 문자열 문제를 찾아서 풀어 볼 생각이다. 2차원 dp를 차례대로 채워가면서 s1[i] == s2[i]이면 d[i - 1][j - 1] + ..
BOJ 16236번 아기 상어 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가 www.acmicpc.net * 한 게시글에 코드 블록 언어를 하나로 통일해야 해서 Python 코드는 하이라이트가 정상적이지 않습니다ㅠ Intro 처음에는 물고기들의 위치를 저장한 뒤, 각 물고기의 위치에서 현재 상어 위치까지의 거리를 구해 우선순위에서 일 순위인 물고기를 사용하는 방식으로 구현하였습니다. 그랬더니 시간 초과가 계속해서 발생했습니다. 위 풀이 방식은 가장 가까우면서 우선순위에서 일순위인 물고기를 찾기 위해, BFS를 상어가 먹을 수 있는..
![]()
문제 풀이 입력 : 학생 수 N, 친구 관계 수 M, 가지고 있는 돈 k가 주어진다. 두번째 줄 부터 학생 N의 학생이 원하는 친구비 An 이 주어진다. M개의 친구 관계가 주어진다. M개의 친구 관계를 이용하여 서로 친구 관계인 집합을 구합니다. 유니온 파인드를 이용하였는데 배열 내에서 같은 값(친구 관계 중에서 가장 낮은 번호)을 가지면 친구 관계이므로, 이 들중에서 가장 적은 친구비를 총합에 더합니다. 모든 집합에서 한 명씩 친구비를 구하여 초기에 주어진 k와 비교하여 결과를 출력합니다. 코드 import java.io.*; import java.util.*; import java.math.*; class Main { static int arr[]; static int find(int x) { if..
https://www.acmicpc.net/problem/14465 14465번: 소가 길을 건너간 이유 5 첫 줄에 N, K, B (1 ≤ B,K ≤ N)가 주어진다. 그 다음 B줄에는 고장난 신호등의 번호가 하나씩 주어진다. www.acmicpc.net 해당 문제를 투포인터의 아이디어를 차용해서 풀어봤습니다.(사실 이중 for문으로 풀었다고 해도 맞는 말인것 같습니다) 문제 설명부터 하겠습니다. 신호등의 개수가 N으로 주어지고 부서진 신호등의 개수가 B로 주어집니다. 부서진 신호등은 수리가 가능하고, 최소한의 수리 횟수로 연속한 K개의 신호등을 만들어야 합니다. 해당 문제를 푼 아이디어를 나열하면 다음과 같습니다. 총 두개의 포인터를 사용합니다 (편의상 각각 Anchor와 Move로 명명했습니다) A..
![]()
풀이 n = int(input()) total = [0, True,False,True,True] + [0]*(n-4) for _ in range(5,n+1): if False in [total[_-1],total[_-3],total[_-4]]: total[_]= True else: total[_]=False if total[n]: print("SK") else: print("CY") c언어에서는 생각 조차 할 수 없었던 [0]*(n-4) 라는 표현을 구글링을 통해 알게 되었는데 파이썬은 내 생각보다 무지 대단한 놈 같다. 어쨋든 total 리스트는 본인 차례에 가져갈 수 있는 구슬의 개수에 따라 패배 혹은 승리가 결정되는 것을 미리 1,2,3,4개의 돌에 대한 승 패 값으로 지정해놓았다. 이 수보다 더 ..
![]()
문제 링크 https://www.acmicpc.net/problem/16395 16395번: 파스칼의 삼각형 파스칼의 삼각형은 이항계수를 삼각형 형태로 배열한 것인데, 블레즈 파스칼(1623-1662)을 따라 이름 붙여졌다. 단순한 형태로, 파스칼의 삼각형은 다음과 같은 방법으로 만들 수 있다. N번째 행 www.acmicpc.net 풀이 바로 위 행의 인접한 두 수의 합을 구하기 위해 다음과 같은 형태로 배열을 만들었습니다. 파란색 삼각형 부분은 n 이 5일때 나오는 형태입니다. [n+1][n+1] 크기만큼의 배열을 선언하고 0으로 초기화합니다. (1,1) 위치의 값을 1로 초기화하면 세번째 행부터 모든 값은 바로 위 행의 인접한 두 수의 합으로 구할 수 있습니다. 세번째 행은 배열에서는 2에 해당하므..
![]()
https://www.acmicpc.net/problem/2193 2193번: 이친수 0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다. 이친수는 0으로 시작하지 않 www.acmicpc.net 이친수의 성질은 0으로 시작하지 않고, 1이 연속해서 나오지 않는 수를 의미한다. N을 나열하면서 예를 적어보면서 점화식을 쉽게 찾을 수 있었다.N=1 → 1N=2 → 10N=3 → 100, 101N=4 → 1000, 1001, 1010N=5 → 10100, 10110, 10000, 10001, 10010 이친수의 성질에 의해서 반드시 처음 두자리 수는 1과 0이 차례로 오게되고, 이후..
![]()
오늘은 백준 알고리즘 5582번 공통 부분 문자열문제를 풀어보는 시간을 가져보겠습니다. 이 문제는 다이나믹프로그래밍으로 접근하면 수월하게 풀 수 있습니다. 문제 먼저 보겠습니다. 이 문제는 행렬테이블을 그려서 규칙성을 발견하여 점화식을 만들어 풀 수 있습니다 위의 그림처럼 문자열 두 개의 문자가 같을 때 이전에 같았던 dp[i-1][j-1] + 1 임을 파악할 수 있고 이를 토대로 arr1[i] == arr2[j]같다면 dp[i][j] = dp[i-1][j-1] +1 임을 이끌어낼 수있습니다. 코드는 다음과 같습니다. #include using namespace std ; string arr1; string arr2; int dp[4001][4001]= {}; int ans; int max_res..
문제 https://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 풀이 집의 개수가 최대 20만개이고 집의 좌표가 10억까지 가능하므로 이진탐색으로 풀어야 한다. 1. 공유기 좌표를 정렬 2. 정렬된 공유기 좌표에서 가장큰 좌표와 가장 작은 좌표의 차이가 가능한 최대값 3. st = 1, ed = (가장 큰 집의 좌표 - 가장 작은 집의 좌표)로 두고 이진 탐색을 한다. 4. 첫번 째 집에는 무조건 공유기..
