'PS/BOJ&Programmers' 카테고리의 글 목록 (6 Page)

[백준/1343] 폴리오미노

2022.12.31·

PS/BOJ&Programmers

🐤 처음 짠 코드 - 실패 board = list(input().split('.')) ans = str() for i in range(len(board)): target = len(board[i]) if target % 2 !=0: # X의 개수가 홀수인 게 하나라도 존재하면 print(-1) exit() if board[i] == '': ans += '.' else: if target % 4 == 0: ans += 'AAAA' elif target % 2 == 0: ans += 'BB' # 여기서 그리디 else: 문제는 이해 했는데 그리디 작성에서 실패했다. 만약 길이가 6이나 10인 X문자열을 만난다면 먼저 'AAAA'를 먼저 채워주고, 남은 2자리에 'BB'를 채워준다는 로직을 생각했는데 실패 💻..

[백준/1712] 손익분기점

2022.12.31·

PS/BOJ&Programmers

🐤 처음 푼 코드 a,b,c = map(int, input().split()) n = 0 #가변 비용이 수익 보다 큰 경우 if b > c: print(-1) exit() while True: income = a+b*n cost = c*n n += 1 if income == cost: print(n) break 시간 초과가 떠서 입력 문젠가~ 했는데 제한시간이 0.35초인거다.(일단 로직도 100% 정답도 아님.) 이건 입력 문제가 아니고 수학적 트릭이나 알고리즘이 존재할 거라는 생각이 들었다. 📝 간단한 항등식 종이에 쓰면서 풀어서 대놓고 항등식을 적었고, n을 구하는 문제인 걸 알았음에도 불구하고 식을 정리하지 않은 나! 반성해야한다. 식을 정리해주면 간단한 코드로 빠른 시간 내에 구할 수 있다. 항..

[백준/11723] 집합

2022.12.31·

PS/BOJ&Programmers

💻 전체 코드 import sys n = int(sys.stdin.readline()) s = set() for _ in range(n): words = sys.stdin.readline().split() command = words[0] if command == 'add': s.add(int(words[1])) elif command == 'remove': s.discard(int(words[1])) elif command == 'check': if int(words[1]) in s: print(1) else: print(0) elif command == 'toggle': if int(words[1]) in s: s.discard(int(words[1])) else: s.add(int(words[1])..

[백준/1934] 최소공배수 feat. 유클리드 호제법

2022.12.27·

PS/BOJ&Programmers

📝 정수론_ 최소공배수 정수론은 정수를 다루는 학문으로, 약수와 배수/몫과 나머지에 대해 탐구한다. 컴퓨터 발달 이후 정수론의 유용성은 급상승했다. 현대 암호의 원리가 두 개의 큰 소수를 곱하는 것은 쉽지만, 이 결과를 다시 소인수분해하는 것이 어렵다는 것이 기반이기 때문이다. 뿐만 아니라 컴퓨터를 이용한 계산이나 메모리 설계 등에서도 정수론은 다양하게 쓰인다! 최소공배수(LCM, Least Common Multiple)는 최대공약수(GCD, Greateast Common Division)와 함께 정수론의 첫 번째 내용이다. 앞의 유클리드 호제법에서 유클리드 알고리즘을 통해 GCD와 LCM을 다루었으니, 이 포스팅에서는 내장함수를 기록하겠다. 💻 전체 코드 import sys import math n =..

[백준/2609] 최대공약수와 최소공배수| 유클리드 호제법 | 확장 유클리드 알고리즘

2022.12.27·

PS/BOJ&Programmers

유클리드호제법(최대공약수와 최소공배수) 두 양의 정수, 혹은 두 다항식의 최대공약수를 구하는 방법이다. 호제법이라는 말은 '서로 나눈다'라는 뜻. 일반적으로 우리는 최대공약수를 구할 때 소인수분해를 하고 두 수의 공통인 소인수를 곱한다. 이 방법은 수가 커질수록 소인수분해하기 어려워진다는 단점이 있다. 이를 극복하기 위한 방법이 유클리드 호제법이다. 그렇다면, 유클리드 알고리즘을 어떻게 구현할 수 있을까? 바로 mod 연산(나머지 구하기 : %)을 반복하는 방법이다. why mod p? 답이 큰 정수인 경우, Overflow 에러를 막기 위해서 문제에서 큰 소수(보통 1,000,000,007)로 나눈 나머지를 요구 자연수 a, b에 대해 a를 b로 나눈 나머지는 r이다. (단 a>b) r에 대해, b를 ..

[백준/1929] 소수 구하기 | 에라토스테네스의 체

2022.12.26·

PS/BOJ&Programmers

개요 백준 소수 문제들이 눈에 들어와서 푸는데,, 이 문제만 같은 방식으로 해결이 안되는 거다. 서칭한 결과 소수 구하기 문제는 시간초과를 주의해야 하고, 소수 문제에서 시간초과를 피하기 위해 에라토스테네스의 체라는 개념을 알아두면 유용하다는 결론을 내렸다. (하지만 공부한 결과 모든 소수 문제에 적용되는 것은 아니다..! 끝까지 글을 읽어보자) 📝 에라토스테네스의 체 에라토스테네스의 체란? 어떤 수 n 이하의 모든 소수를 찾는 간단하고 빠른 방법으로, 자기 자신을 제외한 배수를 모두 차례대로 지우는 방식이다. 더이상 지울 수 없을 때 남아있는 수들이 소수이다. 에라토스테네스의 시간복잡도는 O(n log(logn))이다. 에라토스네네스의 체는 '특정 범위 내의 소수'를 판정하는 데에만 효율적이다. 만약 ..

[백준/1110] 더하기 사이클

2022.12.24·

PS/BOJ&Programmers

🔎 처음 쓴 코드 num = input() key = num cycle = 0 while True: if len(num) == 1: num = '0' + num result = int(num[0]) + int(num[1]) ended = str(result) num = num[-1] + ended[-1] # 결과값의 끝자리 더하기 cycle += 1 if key == num: print(cycle) break 무조건 완전탐색으로 풀려고 해서 시간 초과 자릿수에 대한 문제가 나오면 몫과 나머지를 떠올려 보자..! num = int(input()) key = num cycle = 0 while True: first = num // 10 second = num % 10 result = (first + seco..

[백준/1927] 최소 힙

2022.12.23·

PS/BOJ&Programmers

문제를 잘 이해하면 구현은 어렵지 않다. ✍️ 첫번째 시도 import sys n = int(sys.stdin.readline()) heap = [] # 자연수라면 in heap 0이라면 출력 + out heap for _ in range(n): x = int(sys.stdin.readline()) if x == 0 and len(heap) != 0: print(min(heap)) heap.remove(min(heap)) elif x != 0: heap.append(x) else: print(0) 혼자서 문제에 따라 잘 구현한 것같은데,, 시간 초과ㅠㅠ 구글링 후 알게된 점은 파이썬에서 따로 heappush, heappop을 제공한다는 것이었다..! (from heapp 모듈) 📝 파이썬 heapq 모듈..

[백준/2747] 피보나치 수 with 동적 계획법

2022.12.22·

PS/BOJ&Programmers

이 내용은 알고리즘 수강 시간에 배웠던 내용이라 눈치를 챌 수 있었다. def fibo(n): if n == 0: return 0 elif n == 1 or n == 2: return 1 else: result = fibo(n-1) + fibo(n-2) return result print(fibo(int(input()))) 단순히 이렇게 재귀형식으로 피보나치 수열을 만들 수 있지만, 이렇게 되면 fibo(10)을 구하기 위해 fibo(9)와 fibo(8)을 구해야 한다. fibo(9)를 구한 다음, fibo(8)을 구하려면 다시 처음부터 구해야 한다. 따라서 시간 복잡도는 T(n) = T(n-1) + T(n-2) 결국 T(n) >= 2^n/2T(1)으로, 지수 시간이 걸리게 된다. 😱 이를 해결하기 위해..

[백준/1874] 스택 수열

2022.12.22·

PS/BOJ&Programmers

📝 문제 이해 입력 받은 수열의 첫번째 항까지 모두 stack에 넣고, 스택의 마지막 원소를 pop하면 수열의 첫번째 항이 완성된다. 예컨대 4 3 6 8 7 5 2 1 수열이 있으면 ,2,3,4까지 stack에 push하고 pop을 하면 4가 pop 되면서 수열의 첫번째 항이 완성된다. 만약 stack의 top(가장 마지막에 push된 값)이 입력 받은 수열과 같다면 pop해주고, 또 다시 다음 항의 수열만큼 stack에 push하고 조건문을 통해 검사하고.. 다음항이 stack의 top에 없다면 'NO'를 출력해준다. 🔎 내가 처음 짠 코드 #중간 단계 메모메모 n = int(input()) sequence = range(1,n+1) num, stack = [], [] for _ in range(n)..

[백준/14912] 숫자 빈도수

2022.12.21·

PS/BOJ&Programmers

개요 문제 풀면서 int형을 str형으로 바꿔서 비교하는 건 여러번 해본 것같은데 기억이 나질 않아 이번엔 제대로 정리해보려 한다! int > str for i in range(1, n+1): for j in str(i): 위 코드의 의미는 1부터 n까지의 숫자(int)를 만들고, 그 숫자들을 str로 변형한다는 뜻이다. 숫자 빈도수 문제에서는 입력된 d에 해당하는 숫자와 같은 숫자의 빈도를 체크하라고 했으니, 이중 for문 아래에 다음과 같이 작성해주면 된다. 전체 코드 n,d = map(int, input().split()) cnt = 0 for i in range(1, n+1): for j in str(i): if j == str(d): cnt += 1 print(cnt) 프로그래밍을 C로 시작해서..

[백준/1157] 글자 공부

2022.12.19·

PS/BOJ&Programmers

처음 쓴 코드 str = input() size = len(str) cnt = [0 for i in range(size)] # 입력 받은 문자열의 size 만큼 배열 선언 (카운팅을 위해) for i in range(size): for j in range(i+1, size): if str[i] == str[j]: # 이중 포문으로 문자열 서로서로 비교 cnt[i] += 1 # 같은 문자열이 나오면 cnt 배열을 + 해준다. for i in range(len(cnt)): if cnt[i] == cnt[i+1]: print('?') exit() m = max(cnt) if m == 1: print(str.upper()) else: print(str[m].upper()) 사실 알고리즘 시간에 kmp, 실패함수..

[백준/2420] 사파리월드

2022.12.18·

PS/BOJ&Programmers

x, y = map(int, input().split()) print(abs(x-y)) 이렇게 파이썬에서 제공하는 절댓값 함수 abs()를 사용해도 되지만, 새싹 문제의 조건문 분야인 만큼 조건문을 통해 문제를 풀어보자. x, y = map(int, input().split()) if y>x : print(-(x-y)) else: print(x-y)

[백준/1001] A-B

2022.12.18·

PS/BOJ&Programmers

문제 두 정수 A와 B를 입력받은 다음, A-B를 출력하는 프로그램을 작성하시오. 입력은 첫째줄에 한번에 A와 B가 주어진다. 파이썬에서 두 정수 한번에 입력 받는 방법 ! a, b = map(int, input().split()) 이 코드의 뜻은 입력 받은 값을 공백을 기준으로 나누고, 입력받은 값들을 int형으로 변환하여 변수 a, b에 저장하라는 것이다. 파이썬 map 함수 입력 받을 때 사용한 map은 파이썬의 내장함수이다. 데이터의 형태를 변환하기 위해 사용한다. 위 코드에서는 입력 받은 수를 한번에 int형으로 변환하기 위해 사용하였다. 문제에서 a, b를 한번에 입력 받고, 뺄셈한 값을 출력하라고 했으니까 코드는 다음과 같이 쓰면 된다. a, b = map(int, input().split(..

[백준/10171] 고양이

2022.12.17·

PS/BOJ&Programmers

방학에 들어서서 새싹 문제를 모두 풀어보는 목표를 세웠다 ! 이번 포스팅에서는 아주 귀여운 이 아이를 출력해보려 한다.ㅎㅎ print('\\ /\\') #백슬래시 출력은 이스케이프 문제를 써야 한다 print(" ) ( ')") print("( / )") print(" \\(__)|") 백슬래시는 이스케이프 문자를 써야한다는 것도 몰랐던 나 🥲 방학 동안 정말 열심히 공부를 해야겠다는 생각이 또 들었다.. 자료 출처: https://dojang.io/mod/page/view.php?id=2465

티스토리툴바