링크 https://www.acmicpc.net/problem/4134 난이도(solved.ac 참고) 실버5 풀이 while True 문에서 소수면 그 값을 print하고 아니면 값을 1 더해주고 다시 소수 여부를 판단하는 함수를 돌린다. 여기서 소수의 범위를 줄여줘야 했다. def is_prime(x): if x == 0 or x == 1: return False for i in range(2, x): if x % i == 0: return False return True 이렇게 하면 시간초과가 뜬다. x까지 전부 다 돌기 때문에 시간이 상당해 오래 걸린다. 8을 예로 들어보자. 8의 약수는 1, 2, 4, 8이 있다. 근데 1 * 8 = 2 * 4이다. 즉 대칭을 이룬다는 것이다. 따라서, 해당하는..

링크 https://www.acmicpc.net/problem/3613 난이도(solved.ac 참고) 실버5 풀이 이 문제는 에러를 띄우는 조건이 상당히 많다. 왜 실버5밖에 안되는지 의문인 문제였다. from string import ascii_uppercase를 한 다음에 list(ascii_uppercase)를 하면 ['A', 'B', 'C', ..., 'Z']의 리스트가 완성된다. Java에서 C++로 바꾸는 경우 (ex. isImport -> is_important) - 첫 글자가 대문자면 에러 - 대문자가 들어가면 에러 - input의 첫번째 값을 temp로 저장하고 대문자면 '_+소문자', 대문자가 아니면 그대로 넣어주면 된다. C++에서 Java로 바꾸는 경우(is_important ->..

링크 https://www.acmicpc.net/problem/5052 난이도(solved.ac 참고) 골드4 풀이(오답) 처음에 접근을 잘못해서 여러번 틀렸다. sort를 한 뒤 처음 값을 기준으로 그 다음 값들부터 접두사에 처음 값이 들어가는지 여부로 판단을 했는데, 그렇게 하면 두번째 접두어가 세번째 입력의 접두어로 들어가있을 수 있기 때문에 접근이 잘못되었다. 1010 1234 12345 이런 경우가 있다고 해보면, 1010을 기준 값으로 잡고 1234부터 반복문을 진행하게 되는데, 이 경우 전부 1010이 들어가지는 않지만 1234는 12345에 들어가기때문에 NO가 나오는 게 정답이다. 근데 이전 코드대로 따르면 YES가 나왔다. 풀이(정답) 위와 같은 반례가 있을 수 있기 때문에, 저 예시의..

링크 https://www.acmicpc.net/problem/12904 난이도(solved.ac 참고) 골드5 풀이 나는 역으로 접근해서 B에서 A를 만들 수 있는지를 확인하였다. 두 가지 연산 모두 A 또는 B가 추가되는 연산이다. 따라서 역으로 생각하면 이것들을 하나씩 지워주면서 B의 길이를 줄여나가면 되는 것이었다. BtoA라는 함수를 만들어서 b의 값을 이 함수를 적용시킨 값으로 해주었다. 마지막 값이 A라면 그 A값을 지운 새로운 new_b를 return하였고, 마지막 값이 B라면 b의 길이가 1보다 큰 때와 1일 때를 나눴다. 이유는 이렇게 나누지 않으면 계속 줄어들어서 결국 0이 되기 때문이다. b의 길이가 1보다 큰 경우라면 마지막 값을 없앤 값을 reverse하고 그것을 리스트로 바꿔준..

링크 https://www.acmicpc.net/problem/4358 난이도(solved.ac 참고) 골드5 풀이 딕셔너리로 구했는데 자꾸 시간 초과가 떠서 defaultdict를 사용해서 풀었다. 처음에는 try except로 하려고 했는데 생각해보니까 input값에서 공백을 제거한 값이 아무것도 없으면 더이상 진행하지 않으면 되는 것이었다. defaultdict(int)를 주게 될 경우, 값을 부여했을 때 숫자 형태로 저장이 된다. 아래 예시를 보면 이해가 될 것이다. from collections import defaultdict a = defaultdict(int) b = defaultdict(list) c = input() a[c] += 1 b[c] = ['steadily', 'worked']..

링크 https://www.acmicpc.net/problem/15654 난이도(solved.ac 참고) 실버3 풀이 다르게 풀 수도 있겠지만, 나는 permutations(순열) 모듈을 불러와서 사용했다. 순열은 수학에서 nPr이다. n개 중에 r개를 뽑는 경우의 수이다. from itertools import permutations a = [1, 2, 3, 4] for i in permutations(a, 2): print(i) # (1, 2) # (1, 3) # (1, 4) # (2, 1) # (2, 3) # (2, 4) # (3, 1) # (3, 2) # (3, 4) # (4, 1) # (4, 2) # (4, 3) 사전 순서로 증가하는 순으로 출력해야 되었기 때문에 a를 정렬한 값을 기준으로 순열..

링크 https://www.acmicpc.net/problem/17626 난이도(solved.ac 참고) 실버5 풀이 input값 n을 받았을 때, 우선 9행에서 이 수가 특정 수의 제곱수인지 여부를 걸러낸다. 처음에는 무조건 그 수와 가장 가까운 제곱수를 찾아내 그 수를 더하고 남은 값을 DP 처리하는, 그리디 방식으로 생각했다. 근데 그렇게 하자니, 12라는 훌륭한 반례가 있다. 12 = 3^2 + 1^2 + 1^2 + 1^2 (총 4개) = 2^2 + 2^2 + 2^2 (총 3개) 그 수와 가장 가까운 제곱수를 항상 더하는 방식으로 가져간다면 위의 12처럼 12와 가장 가까운 제곱수인 3을 가져갔을 때의 개수가 2를 세 개 가져갔을 때의 개수보다 더 많다. 그렇기 때문에 그리디와 같은 방식으로 풀면..

링크 https://www.acmicpc.net/problem/1013 난이도(solved.ac 참고) 골드5 풀이 파이썬 정규표현식 문제이다. re(regular expression) 모듈을 불러와서 사용한다. (100+1+ | 01)+ 을 해석해보려고 했는데, 이게 리스트로 하나하나 나열하는 게 불가능하다는 판단 하에 정규표현식에서 compile을 사용해서 풀어보기로 하였다. +와 (), | 등은 실제로 정규표현식에서 많이 쓰이는 연산자이다. 이 세 표현에 대해 잠깐 정리하자면 +: + 앞에 붙은 요소가 최소 하나는 들어가야 한다는 뜻이다. 예를 들면, ab+c라고 해보자. 이것을 만족하는 배열은 { abc, abbc, abbbc, abbbbc, ... } 이렇게 있다. (): 괄호 안의 요소들을 하..

백준 문제를 풀다가 제출 현황을 보면 자주 볼드체 + 색상 처리가 되어있는 아이디를 볼 수 있었다. 내 아이디는 반면에 너무 심심해서 한번 색상을 입혀봐야겠다는 생각이 들어 찾아봤다. 찾아보니까 외국 알고리즘 대회 사이트에서 주최하는 대회에 참여해서 문제를 풀었을 때 부여되는 레이팅에 해당하는 색상이 입히고 백준에서 그 대회 사이트와 계정 연동을 했을 때 백준에도 반영이 되는 것이다. (레이팅 부여 후 색상 입혀지기까지 1-2일 소요) 나는 Codefordes에서 하는 대회를 참여했다. 여기에 들어가면, 위 사진처럼 예정되어있는 대회들을 확인할 수 있고, Before registration 시간이 다 지나면 등록 버튼이 활성화된다. UTC를 기반으로 하기 때문에 KST 기준으로는 +9시간 뒤에 시작된다...

링크 https://www.acmicpc.net/problem/11279 난이도(solved.ac 참고) 실버2 풀이 Python의 heapq 모듈만 알고 있으면 너무 쉬운 문제이고, 나 또한 그것을 알고 있어서 금방 풀었지만 포스팅을 하는 이유는 최소힙이 아니라 최대힙이므로, 이를 만드는 쉬운 방법을 공유하기 위함이다. heapq 모듈을 사용하면서 약간의 트릭을 넣음으로써 최대 힙을 구현할 수 있다. heapq.heappush를 할 때 -의 값으로 집어넣는 것이다. 그렇다면, 기본적으로 heapq 모듈은 최소힙을 가정하므로 - 값이 가장 클 수록 상위에 위치하게 된다. 이것을 출력할 때 절댓값만 씌워주면 최대힙과 똑같다. (물론 음수는 들어가지 않는다는 전제하에. 이 문제는 음수는 입력하지 않는다고 했..