전체 글

괄호 풀이

문제 링크: https://www.acmicpc.net/problem/9012 백준 알고리즘 기초 1/2 200에서 3번째 - 9012번 괄호를 풀어보았다. 풀이: 스택을 이용해 푸는 문제다. 파이썬 if else가 반복문 넘어서도 적용이 될 수 있다는 것을 알게 되었다. C++ Python import sys n=int(input()) for i in range(n): stack=[] inp=sys.stdin.readline().strip() for j in inp: if j=='(': stack.append(j) elif j==')': if stack: stack.pop() else: print("NO") # 스택에 아무것도 없는데 )입력이면 break else: if stack: print("NO"..

단어 뒤집기 풀이

문제 링크: https://www.acmicpc.net/problem/9093 백준 알고리즘 기초 1/2 200에서 2번째 - 9093번 단어 뒤집기를 풀어보았다. 풀이: 문장을 받아, 단어마다 역순으로 출력하면 된다. 파이썬은 [::-1]을 썼다. C++ Python import sys n=int(input()) for i in range(n): inp=list(sys.stdin.readline().split()) for j in inp: print(j[::-1],end=' ') # 역순으로 출력 Java

스택 풀이

문제 링크: https://www.acmicpc.net/problem/10828 백준 알고리즘 기초 1/2 200에서 1번째 - 10828번 스택을 풀어보았다. 풀이: 명령어를 받고 수행하는 코드를 짜면 된다. 파이썬은 리스트로 구현했다. 시간초과가 나서 input()대신 sys.stdin.readline().strip()을 사용했다. C++ Python import sys stacks=[] def pop(): if len(stacks)==0: print(-1) else: print(stacks[-1]) del stacks[-1] def size(): print(len(stacks)) def empty(): if len(stacks)==0: print(1) else: print(0) def top(): ..

조합 0의 개수 풀이

문제 링크: https://www.acmicpc.net/problem/2004 백준 정수론 및 조합론 12단계 - 2004번 조합 0의 개수를 풀어보았다. 풀이: 팩토리얼 0의 개수 문제와 비슷하다. 5와 2의 개수를 세면 되는데, a! 에서 b가 몇 번 나타나는지 알고 싶으면 a//b를 하면 된다는 것을 알게 되었다. C++ Python def count(a,b): cnt=0 while a: a//=b cnt+=a return cnt n,m=map(int,input().split()) fives=count(n,5)-count(m,5)-count(n-m,5) twos=count(n,2)-count(m,2)-count(n-m,2) print(min(fives,twos)) Java

팩토리얼 0의 개수 풀이

문제 링크: https://www.acmicpc.net/problem/1676 백준 정수론 및 조합론 11단계 - 1676번 팩토리얼 0의 개수를 풀어보았다. 풀이: 0은 10이 몇 번 곱해지느냐로 나타내지고, 10은 2와 5의 곱이므로 팩토리얼에서 2와 5가 몇 번 나타나는지 알아내면 된다. C++ Python n=int(input()) fives=0 # 5의 개수 twos=0 # 2의 개수 while n>1: nn=n while nn%5==0 or nn%2==0: if nn%5==0: fives+=1 nn=nn//5 if nn%2==0: twos+=1 nn=nn//2 n-=1 print(min(fives,twos)) # 둘 중 적은거 출력 Java

패션왕 신해빈 풀이

문제 링크: https://www.acmicpc.net/problem/9375 백준 정수론 및 조합론 10단계 - 9375번 패션왕 신해빈을 풀어보았다. 풀이: 조합의 수를 세는 문제이다. 옷 종류마다 1을 더해주고 곱한 다음, 1을 빼주면 된다. C++ Python from collections import Counter t=int(input()) for i in range(t): n=int(input()) cloth=[] for j in range(n): a,b=input().split() cloth.append(b) cnt=Counter(cloth) # 종류마다 개수 셈 res=1 for key in cnt: res*=cnt[key]+1 print(res-1) # 아무것도 입지 않는 경우 빼기 Java

다리 놓기 풀이

문제 링크: https://www.acmicpc.net/problem/1010 백준 정수론 및 조합론 9단계 - 1010번 다리 놓기를 풀어보았다. 풀이: dp로 풀어볼까 했지만, 그냥 계산하는 게 나은 거 같았다. C++ #include using namespace std; int main() { int t; cin>>t; for(int i=0;i>n>>m; int nn; if(n>=m-n) nn=n; else nn=m-n; long long res=1; for(int j=1;j

이항 계수 2 풀이

문제 링크: https://www.acmicpc.net/problem/11051 백준 정수론 및 조합론 8단계 - 11051번 이항 계수 2를 풀어보았다. 풀이: 범위가 크기 때문에 dp를 사용해 풀어야 한다. (https://cocoon1787.tistory.com/220 를 참고했다.) 파이썬의 경우 이항 계수 1보다 범위가 크기 때문에, 풀이 형식을 조금 바꾸었다. C++ #include using namespace std; int main() { int dp[1001][1001]; int n,k; cin>>n>>k; dp[0][0]=1; dp[1][0]=1; dp[1][1]=1; for(int i=2;i