![]()
문제 길이가 같은 두 단어가 주어졌을 때, 각 단어에 포함된 모든 글자의 알파벳 거리를 구하는 프로그램을 작성하시오. 두 글자 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] + ..
![]()
https://www.acmicpc.net/problem/9226 9226번: 도깨비말 도깨비말은 언어 유희 중 하나로, 글자를 특정 법칙에 따라 재구성하는 것을 말한다. 영어권에서는 피그라틴어라는 것이 있다. 주로 어린이들이 많이 쓰는 데, 남들에게 무슨 말인지 모르게 하 www.acmicpc.net import sys while True: x=input() tex=list(x) if x=='#': sys.exit() fix=['a','e','i','o','u'] s=0 for i in tex: if i in fix: s=1 break if s==0: tex.extend('ay') b=''.join(tex) print(b) continue for i in range(len(tex)): if tex[0]..
BOJ 16236번 아기 상어 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가 www.acmicpc.net * 한 게시글에 코드 블록 언어를 하나로 통일해야 해서 Python 코드는 하이라이트가 정상적이지 않습니다ㅠ Intro 처음에는 물고기들의 위치를 저장한 뒤, 각 물고기의 위치에서 현재 상어 위치까지의 거리를 구해 우선순위에서 일 순위인 물고기를 사용하는 방식으로 구현하였습니다. 그랬더니 시간 초과가 계속해서 발생했습니다. 위 풀이 방식은 가장 가까우면서 우선순위에서 일순위인 물고기를 찾기 위해, BFS를 상어가 먹을 수 있는..
