![]()
엄청 많은 시도가 있었는데, 처음에 복잡하게 for문과 while 문 여러 개를 써서 구현했더니 시간초과 / 메모리초과가 계속 떴고, 이후 완전히 다르게 생각해 맞추었다. 일단 여기서 중력이 위에서 아래로 작용하기 때문에 이를 조금 손쉽게 처리하기 위해 list로 바꾸어 sort하려고 했다. a와 .은 문자열에서 sort시 '.'가 먼저고 'a'가 나중이기 때문에 그를 이용하였다. 그렇게 #가 나오기 전까지 .과 a를 하나의 list에 넣어 sort해주고 #는 그냥 넣어주는 식으로 구성한다. 이후 그림에 보이는 것처럼 꺼내주기 위해서 2차원을 1차원으로 압축시켜준 후 순서에 맞게 차례대로 print하였다. import sys sys.setrecursionlimit(100000) #중력 문제임!! N,M=..
https://www.acmicpc.net/problem/16713 16713번: Generic Queries 첫째 줄에는 $N, Q$가 공백을 사이에 두고 주어진다. ($1 \le N \le 10^6$, $1 \le Q \le 3 \cdot 10^6$) 둘째 줄에는 $a_1, a_2, \cdots a_N$이 공백을 사이에 두고 주어진다. ($0 \le a_i \le 10^9$) 그 후, $Q$개의 줄에 걸 www.acmicpc.net 누적합(prefix sum)알고리즘을 사용해서 O(N)시간에 답을 구하는 것이 핵심인것 같습니다. 다만 더하기(+) 연산 대신 XOR(^) 연산을 사용해서 문제를 풀어야합니다. 전체적인 알고리즘 흐름은 "11659번: 구간 합 구하기4" 문제와 비슷합니다. 누적 XOR 배..
![]()
문제 길이가 같은 두 단어가 주어졌을 때, 각 단어에 포함된 모든 글자의 알파벳 거리를 구하는 프로그램을 작성하시오. 두 글자 x와 y 사이의 알파벳 거리를 구하려면, 먼저 각 알파벳에 숫자를 할당해야 한다. 'A'=1, 'B' = 2, ..., 'Z' = 26. 그 다음 y ≥ x인 경우에는 y-x, y < x인 경우에는 (y+26) - x가 알파벳 거리가 된다. 예를 들어, 'B'와 'D' 사이의 거리는 4 - 2 = 2이고, 'D'와 'B' 사이의 거리는 (2+26) - 4 = 24이다. 입력 첫째 줄에 테스트 케이스의 수 (< 100)가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 두 단어가 공백으로 구분되어져 있다. 단어의 길이는 4보다 크거나 같고, 20보다 작거나 같으며, 알파벳 ..
![]()
오늘은 백준 알고리즘 1644번 소수의 연속합문제에 대해 알아보도록 하겠습니다 문제부터 보겠습니다. 이 문제는 소수구하기 + 투포인터가 결합된 문제입니다. 개념이랑 기본코드만 알고있으면 쉽게 풀수 있는 문제입니다. 소수를 구하는 방법은 여러가지가 있겠지만 에라토스테네스의 체라는 방식을 이용하여 구현을 합니다. 왜냐하면 이 방법의 시간복잡도가 O(root(n))이기 때문입니다. 코드는 다음과 같습니다. #include #include #include #include using namespace std; vector a; int number; long long a1[4000001]; // 에라토스테네스의 체 void primeNumber(){ for (int i = 2; i
![]()
문제링크 https://www.acmicpc.net/problem/3986 3986번: 좋은 단어 이번 계절학기에 심리학 개론을 수강 중인 평석이는 오늘 자정까지 보고서를 제출해야 한다. 보고서 작성이 너무 지루했던 평석이는 노트북에 엎드려서 꾸벅꾸벅 졸다가 제출 마감 1시간 전에 www.acmicpc.net 코드 n=int(input()) sum1=0 for i in range(n): x=list(input()) a=['one'] for i in (x): if i!=a[len(a)-1]: a.append(i) else: a.pop(len(a)-1) if len(a)==1: sum1+=1 print(sum1) 문제푼과정 스택을 이용하면 매우 쉽게 풀리는 문제인데 단어를 어떻게 짝짓는지 고민하다가 시간을 ..
문제 링크 https://www.acmicpc.net/problem/1644 1644번: 소수의 연속합 첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 4,000,000) www.acmicpc.net 풀이 에라토스테네스의 체를 사용해 n 보다 작거나 같은 소수들을 구합니다. (line 2~ line 8) 소수를 담을 배열 prime을 선언합니다. 배열 a는 소수가 아닌 수를 지우기 위해 사용됩니다. 2 ~ n 범위의 수 중에서 소수를 채택하고, 그 소수의 배수는 모두 지우게 됩니다. 투 포인터를 이용해 연속된 수열(소수)의 부분합을 구합니다. (line 9 ~ line 19) left, right의 초기 인덱스를 0,0으로 설정합니다. 우측 포인터를 가리키는 right의 인덱스가 소수를 담은 배열 pr..
링크 https://www.acmicpc.net/problem/2003 2003번: 수들의 합 2 첫째 줄에 N(1 ≤ N ≤ 10,000), M(1 ≤ M ≤ 300,000,000)이 주어진다. 다음 줄에는 A[1], A[2], …, A[N]이 공백으로 분리되어 주어진다. 각각의 A[x]는 30,000을 넘지 않는 자연수이다. www.acmicpc.net 풀이 과정 투포인터로 풀면 O(n)시간 안에 풀리는 문제이다. 다만 유의해야할점은 4 4 1 5 2 2 와 같은 예시에서 5지점에서 포인터가 역전될수도 있으므로 단순히 high>=low를 반복조건으로 두면 틀리게 된다. 따라서 포인터가 역전당했을때 다시 포인터를 옮겨주거나, 혹은 조건에서 high>=low를 제거하면 된다. 코드 #include usi..
![]()
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/15813 15813번: 너의 이름은 몇 점이니? 소윤이는 성필이에게 단단히 화가 났다. 성필이가 자꾸 소윤이의 이름을 놀리는 것이다! 극대노한 소윤이는 이름에 대해 많은 검색을 하던 도중 "이름점수"라는 것을 발견하게 된다. 이름 점수 www.acmicpc.net 코드 count = int(input()) name = list(input()) ascii_list = [] for i in name: ascii_list.append(ord(i)-64) print(sum(ascii_list)) 풀이 count는 입력을 받지만 실제로 사용하지는 않는다. 글자를 입력받아 글자 리스트로 바꿔준 후에, 아스키 코드로 A가 65임을 이용하여 모든 글자를 ..
링크 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] + ..
