분류 전체보기

요세푸스 문제 풀이

문제 링크: https://www.acmicpc.net/problem/1158 백준 알고리즘 기초 1/2 200에서 7번째 - 1158번 요세푸스 문제를 풀어보았다. 풀이: 요세푸스 순열을 구하는 문제이다. C++ Python n,k=map(int,input().split()) yose=[i+1 for i in range(n)] res=[] idx=0 for i in range(n): idx+=k-1 if idx>=len(yose): idx%=len(yose) res.append(str(yose.pop(idx))) print('',sep='') # sep을 해야 앞뒤로 공백이 안붙는다 Java

큐 풀이

문제 링크: https://www.acmicpc.net/problem/10845 백준 알고리즘 기초 1/2 200에서 6번째 - 10845번 큐를 풀어보았다. 풀이: 큐를 구현하면 된다. C++ Python import sys stacks=[] def push(a): stacks.append(a) def pop(): if len(stacks)==0: print(-1) else: print(stacks[0]) del stacks[0] def size(): print(len(stacks)) def empty(): if len(stacks)==0: print(1) else: print(0) def back(): if len(stacks)==0: print(-1) else: print(stacks[-1]) de..

에디터 풀이

문제 링크: https://www.acmicpc.net/problem/1406 백준 알고리즘 기초 1/2 200에서 5번째 - 1406번 에디터를 풀어보았다. 풀이: 명령어를 받아 수행하는 에디터를 구현하는 문제이다. 파이썬은 커서와 문자열을 구현해서 풀었더니만 시간초과가 나서, https://velog.io/@tkdduf727/%EB%B0%B1%EC%A4%80-%EA%B4%84%ED%98%B8-1406%EB%B2%88-%ED%8C%8C%EC%9D%B4%EC%8D%AC-Python-%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0 여기를 참고했다. 리스트 두 개를 써서 왔다 갔다 한 풀이다. C++ Python import sys lstack=list(input()) rstack=[] n..

스택 수열 풀이

문제 링크: https://www.acmicpc.net/problem/1874 백준 알고리즘 기초 1/2 200에서 4번째 - 1874번 스택 수열을 풀어보았다. 풀이: 1부터 n까지의 수열을 스택에 넣고 빼면서 문제에서 입력받은 수열을 만들면 된다. C++ Python n=int(input()) stack=[] res=[] # 정답출력용 num=1 tf=True # 작업이 잘 수행되었는지 확인 for i in range(n): inp=int(input()) while num

괄호 풀이

문제 링크: 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