활동일시 : 4일차 2023-07-26 21:30-23:30
목표
python, c++로 백준 실버5 티어 이상의 알고리즘 문제 풀기
문제
N장의 카드가 있다. 각각의 카드는 차례로 1부터 N까지의 번호가 붙어 있으며, 1번 카드가 제일 위에, N번 카드가 제일 아래인 상태로 순서대로 카드가 놓여 있다.
이제 다음과 같은 동작을 카드가 한 장 남을 때까지 반복하게 된다. 우선, 제일 위에 있는 카드를 바닥에 버린다. 그 다음, 제일 위에 있는 카드를 제일 아래에 있는 카드 밑으로 옮긴다.
예를 들어 N=4인 경우를 생각해 보자. 카드는 제일 위에서부터 1234 의 순서로 놓여있다. 1을 버리면 234가 남는다. 여기서 2를 제일 아래로 옮기면 342가 된다. 3을 버리면 42가 되고, 4를 밑으로 옮기면 24가 된다. 마지막으로 2를 버리고 나면, 버린 카드들은 순서대로 1 3 2가 되고, 남는 카드는 4가 된다.
N이 주어졌을 때, 버린 카드들을 순서대로 출력하고, 마지막에 남게 되는 카드를 출력하는 프로그램을 작성하시오.
입력
첫째 줄에 정수 N(1 ≤ N ≤ 1,000)이 주어진다.
출력
첫째 줄에 버리는 카드들을 순서대로 출력한다. 제일 마지막에는 남게 되는 카드의 번호를 출력한다.
코드
N = int(input())
lst = list(range(1, N+1))
for i in range(N-1):
print(lst[0], end=" ")
del lst[0]
t = lst[0]
del lst[0]
lst.append(t)
print(*lst)풀이
1부터 받은 정수 N까지의 리스트를 생성한다.
리스트의 첫번째 원소를 지우고, 지웠던 원소를 출력한다.
첫번째 원소를 지운 뒤 그 다음에 오는 리스트의 맨 앞 원소를 맨 뒤에 삽입 한 뒤, 맨 앞의 원소를 또 삭제한다. 이 과정을 N-1번 반복하고, 마지막에 하나 남은 원소를 출력한다.
문제
다솜이는 0과 1로만 이루어진 문자열 S를 가지고 있다. 다솜이는 이 문자열 S에 있는 모든 숫자를 전부 같게 만들려고 한다. 다솜이가 할 수 있는 행동은 S에서 연속된 하나 이상의 숫자를 잡고 모두 뒤집는 것이다. 뒤집는 것은 1을 0으로, 0을 1로 바꾸는 것을 의미한다.
예를 들어 S=0001100 일 때,
전체를 뒤집으면 1110011이 된다.
4번째 문자부터 5번째 문자까지 뒤집으면 1111111이 되어서 2번 만에 모두 같은 숫자로 만들 수 있다.
하지만, 처음부터 4번째 문자부터 5번째 문자까지 문자를 뒤집으면 한 번에 0000000이 되어서 1번 만에 모두 같은 숫자로 만들 수 있다.
문자열 S가 주어졌을 때, 다솜이가 해야하는 행동의 최소 횟수를 출력하시오.
입력
첫째 줄에 문자열 S가 주어진다. S의 길이는 100만보다 작다.
출력
첫째 줄에 다솜이가 해야하는 행동의 최소 횟수를 출력한다.
코드
S = input()
flag = True
cnt1 = 0
cnt2 = 0
for i in range(len(S)):
if S[i] == '0':
flag = True
else:
if flag:
cnt1 += 1
flag = False
flag = True
for i in range(len(S)):
if S[i] == '1':
flag = True
else:
if flag:
cnt2 += 1
flag = False
print(min(cnt1, cnt2))
풀이
문자열 S를 받아서 먼저 0을 기준으로 시작해서 1을 만나면 카운트를 해주고, 다음 0이 나올때까지 카운트를 하지 않는다.
그 다음 1을 기준으로 0을 만나면 카운트를 해주고, 다음 1이 나올때까지 카운트를 하지 않는다. 둘 중 카운트가 더 작은쪽을 출력한다.
느낀점
첫번째 문제
실버5 난이도의 문제라고 느껴지지 않을 정도로 쉬웠다. 그래서 최근 공부하기 시작한 c++로 코드를 변경해 보았다. c++은 Visual Studio의 오류 때문에 문서로만 학습을 하고 실제로 코드를 직접 작성해 보는 게 오늘이 처음이었는데, 파이썬으로 풀었을 때와 완전히 같은 로직이지만 문제를 푼 시간보다 c++로 바꿔서 작성하는 시간이 훨씬 오래 걸린 것 같다.
파이썬보다 c++이 훨씬 크기도 작고 빨라서 앞으로는 파이썬이 아닌 c++로 연습해 보고 싶다.
두번째 문제
시간이 많이 남아서 같은 난이도의 다른 문제를 추가로 풀어보았다. 복잡한 로직은 아니었지만, 그리디 알고리즘은 유독 풀이가 잘 떠오르지 않아서 조금 시간이 걸렸던 것 같다. 그리디 알고리즘 관련 문제를 더 풀어보야겠다.
