백준/구현

https://www.acmicpc.net/problem/5347 코드def gcd(n, m): while m > 0: n, m = m, n % m return nt = int(input())for _ in range(t): n, m = map(int, input().split()) print(n * m // gcd(n, m)) 풀이유클리드 호제법을 다시 복습하였는데 오랜만에 하느라 익숙하지가않았다. 그동안 너무 개발만해서 그런가 싶기도하고 반복문으로 구현된 유클리드 호제법 def gcd(n, m): while m > 0: n, m = m, n % m return n 재귀문으로 구현된 유클리드 호제법 def gcd(n, m): if m == 0: return n ..

https://www.acmicpc.net/problem/1972 문제 풀이주어진 문자열의 간격을 이중 for문 혹은 while과 for문으로 구성해서 풀 수 있습니다.그리고 만들어진 쌍은 집합에 저장하여 효율적인 공간을 구성해주었습니다. 코드# 1972번 놀라운 문자열ALERTS = ['is surprising.', 'is NOT surprising.']while 1: word = input() if word == "*": break ALERTS_idx = 0 # 문자열 확인 코드 작성. # 이중 for문을 활용하여서 for j in range(i, num) # 그러고 나서 set에 저장. 그러나 이미 존재한다면 break D = 1 while D..

https://www.acmicpc.net/problem/13717 13717번: 포켓몬 GO 첫 번째 예제에서 지우가 어떻게 뿔충이(Weedle)를 진화시켰는지 보자. 처음 진화를 위해 지우는 12개의 사탕을 사용하였지만 2개를 돌려받아 32개의 사탕이 남는다 (42-12+2). 두 번째 진화 후엔 22 www.acmicpc.net 문제 모바일 게임을 즐겨 하는 지우는 Jetpack Joyride 에 금새 질렸고 포켓몬 GO를 시작했다! 이 게임의 재미있는 점은 포켓몬을 진화시킬 수 있다는 것이다. 지우가 Pi 라는 포켓몬을 진화시키기 위해서는 해당 포켓몬의 Ki 개의 사탕이 필요하다. 진화가 된 후에는 2개의 사탕을 돌려받는다. 각 포켓몬은 그들 종의 사탕으로만 진화할 수 있다. 지우는 N종의 포켓몬..

문제 https://www.acmicpc.net/problem/14503 14503번: 로봇 청소기 첫째 줄에 방의 크기 $N$과 $M$이 입력된다. $(3 \le N, M \le 50)$ 둘째 줄에 처음에 로봇 청소기가 있는 칸의 좌표 $(r, c)$와 처음에 로봇 청소기가 바라보는 방향 $d$가 입력된다. $d$가 $0$인 경우 북쪽 www.acmicpc.net 풀이 주어진 지문을 그대로 구현하려고 노력했다. 다만 지문에 큰 오류가 있다. 지문의 "현재 칸의 주변 4칸 중 청소되지 않은 빈 칸이 없는 경우"은 이미 청소를 한 구역이어도 지나갈 수 있다. 청소를 한 곳을 다시 방문하지 않게 코딩을 하다가 테스트 케이스를 통과하지 못해서 너무나도 고생했다.... 실제로 아래 짠 코드도 중복되는 코드도 많..

https://www.acmicpc.net/problem/2493 2493번: 탑 첫째 줄에 탑의 수를 나타내는 정수 N이 주어진다. N은 1 이상 500,000 이하이다. 둘째 줄에는 N개의 탑들의 높이가 직선상에 놓인 순서대로 하나의 빈칸을 사이에 두고 주어진다. 탑들의 높이는 1 www.acmicpc.net 풀이 이중 for문을 사용하면 시간초과가 발생할 수 있다. 파이썬은 1초당 2000만 번의 연산이 가능하다. 그렇기에 n은 최대 500,000이 입력 값으로 주어질 수 있다. 500,000,000,000 -> 5천억 번의 횟수는 주어진 시간제한인 1.5초에 위배된다. 그렇기에 스택을 사용해서 시간 복잡도를 줄여야 한다. 아래의 코드의 시간 복잡도는 O(n)이기에 50만 번의 연산이 이루어진다. ..

https://www.acmicpc.net/problem/1062 1062번: 가르침 첫째 줄에 단어의 개수 N과 K가 주어진다. N은 50보다 작거나 같은 자연수이고, K는 26보다 작거나 같은 자연수 또는 0이다. 둘째 줄부터 N개의 줄에 남극 언어의 단어가 주어진다. 단어는 영어 소문 www.acmicpc.net 풀이 기본적으로 가르쳐야할 알파벳은 남극의 기본문법인 "a", "c", "i", "t", "n" 총 5개이다. (위의 5개의 알파벳을 가르치지 않으면 어떠한 단어도 읽을 수 없다.) combinations로 조합을 통해 추가로 가르칠 알파벳을 골라주었다. 이를 통해서 완전탐색으로 단어를 읽을 수 있는지 없는지 확인해주었다. 시간초과 문제로 인해 PyPy3로 제출해주었습니다. 코드(PyPy3..

https://www.acmicpc.net/problem/2776 2776번: 암기왕 연종이는 엄청난 기억력을 가지고 있다. 그래서 하루 동안 본 정수들을 모두 기억 할 수 있다. 하지만 이를 믿을 수 없는 동규는 그의 기억력을 시험해 보기로 한다. 동규는 연종을 따라 다니며, www.acmicpc.net 풀이 이분탐색 방법을 이용해서 풀어주어도 괜찮겠지만, 집합을 이용해서 문제를 풀어주었습니다. 코드 # 2776번 암기왕 t = int(input()) for _ in range(t): _ = int(input()) note_1 = set(input().split()) _ = int(input()) note_2 = input().split() for i in note_2: if i in note_1: p..

https://www.acmicpc.net/problem/11653 11653번: 소인수분해 첫째 줄에 정수 N (1 ≤ N ≤ 10,000,000)이 주어진다. www.acmicpc.net 풀이 소인수분해를 구현해주는 문제이다. 나누는 값을 1씩 추가해서 더 이상 나눌 수 없을 때까지 나눠준다. 코드 # 11653번 소인수분해 n = int(input()) ans = [] def calc(c_n): for i in range(2, c_n): if n % i == 0: c_n = c_n // i ans.append(i) break return c_n if n != 1: while True: t = calc(n) if n == t: ans.append(n) break n = t print("\n".join..