문제 😵‍💫

하나 이상의 연속된 소수의 합으로 나타낼 수 있는 자연수들이 있다. 몇가지 자연수의 예를 들어 보면 다음과 같다.

• 3: 3(한 가지)
• 41 : 2+3+4+7+11+13 = 11+13+17 = 41(세 가지)
• 53 : 5+7+11+13+17 = 53(두 가지)

하지만 연속된 소수의 합으로 나타낼 수 없는 자연수들도 있는데, 20이 그 예이다. 7+13을 계산하면 20이 되기는 하나 7과 13이 연속이 아니기에 적합한 표현이 아니다. 또한 한 소수는 반드시 한 번만 덧셈에 사용될 수 있기 때문에, 3+5+5+7과 같은 표현도 적합하지 않다. 

자연수가 주어졌을 때, 이 자연수를 연속된 소수의 합으로 나타낼 수 있는 경우의 수를 구하는 프로그램을 작성하시오.

내 풀🦷

# 1644. 소수의 연속합

import sys
input = sys.stdin.readline

N = int(input())
prime = []
arr = [True for _ in range(N+1)] 
arr[0] = arr[1] = False
for i in range(2, N+1):
    if arr[i]:
        prime.append(i)
        # i의 2배 이상 부터는 다 false...
        for j in range(2*i, N+1, i):
            arr[j] = False

result = start = end = 0
while end <= len(prime):
    each = sum(prime[start:end])
    if each == N:
        result += 1
        end += 1
    elif each < N:
        end += 1
    else:
        start += 1
print(result)

골드 3 요량하고는 엄청 어려운 문제는 아니지만 비교적 빠른 시간에 소수를 구하고 또 투포인터를 써야 하기 땨문에 두가지 알고리즘 개념을 알고 있어야 한다... 그래서 이거전에 풀 문제로 소수 구하는 문제 추천한다!!!!

참고하면 좋을 개념들 ✍️

• 에라토스 테네스의 체(소수 판별 알고리즘 : 소수들을 대량으로 빠르고 정확하게 구현할 수 있다)

// 에라토스테네스의 체를 사용하여 소수 구하기

// 주어진 범위 내에 있는 각 숫자에 대해 초기에는 모두 True인 리스트를 생성한다
arr = [True for _ in range(N+1)] 
// 0과 1은 소수가 아니므로 False로 값을 설정한다
arr[0] = arr[1] = False
// 2부터 N까지의 각 숫자에 대해 소수인지 판별한다
for i in range(2, N+1):
	// 현재 숫자가 소수인 경우, 해당 숫자를 소수 목록에 추가하고,,,
    // 현재 숫자의 배수들을 모두 False로 설정한다... (적어도 i를 포함하니까 소수가 아니다)
    if arr[i]:
        prime.append(i)
        # i의 2배 이상 부터는 다 false...
        for j in range(2*i, N+1, i):
            arr[j] = False

• 투 포인터 (리스트에 순차적으로 접근해야 할 때 두 개의 점의 위치를 기록하면서 처리하는 알고리즘 ex) 특정한 합을 가지는 부분 연속 수열 찾기 )

// 투 포인터 구현하기

// 다 더했을 경우 N이 되는 결과와 시작, 끝 점을 0으로 초기화
result = start = end = 0
// 끝 포인터가 소수의 길이보다 작서나 같은 동안 수행
while end <= len(prime):
	// 현재 시작부터 긑가지의 소수 합을 계산
    each = sum(prime[start:end])
    // 합이 N과 같다면 결과를 1 증가, 끝 포인터 또한 1 증가
    if each == N:
        result += 1
        end += 1
    // 합이 N보다 작다면 끝 포인터 1 증가
    elif each < N:
        end += 1
    // 합이 N보다 크다면 시작 포인터 1 증가
    else:
        start += 1

문제 😵‍💫

독일 로또는 {1, 2,...,49}에서 수 6개를 고른다.

로또 번호를 선택하는데 사용되는 가장 유명한 전략은 49가지 수 중 k(k>6)개의 수를 골라 집합 S를 만든 다음 그 수만 가지고 번호를 선택하는 것이다.

예를 들어, k=8, S={1, 2, 3, 5, 8, 13, 21, 34}인 경우 이 집합 S에서 수를 고를 수 있는 경우의 수는 총 28가지이다.

{[1, 2, 3, 5, 8, 13], [1, 2, 3, 5, 8, 21], [1,2,3,5,8,34], ..., [3,5,8,13,21,34])

집합 S와 k가 주어졌을 때, 수를 고르는 모든 방법을 구하는 프로그램ㅇ을 작성하시오.

입력

입력은 여러 개의 테스트 케이스로 이루어져 이싿. 각 테스트 케이스는 한 줄로 이루어져 있다, 첫 번째 수는 k(6 < k < 13)이고, 다음 k개 수는 집합 S에 포함되는 수이다. S의 원소는 오름차순으로 주어진다.

입력의 마지막 줄에는 0이 하나 주어진다.

출력

각 테스트 케이스마다 수를 고르는 모든 방법을 출력한다. 이때, 사전 순으로 출력한다.

각 테스트 케이스 사이에는 빈 줄을 하나 출력한다.

내 풀🦷

# 6603. 로또
def backtracking(depth, beginwith):
    if depth == 6:
        print(*result)
        return

    for i in range(beginwith, k):
        if not visited[i]:
            result[depth] = nums[i]
            backtracking(depth+1, i+1)
            visited[i] = False


while True:
    lotto = list(map(int, input().split()))
    k = lotto[0]
    nums = lotto[1:]
    result = [0] * 6
    visited = [False] * k
    backtracking(0, 0) // 깊이, 어디서 부터 시작할건지

    if k == 0:
        quit()
    print()

N과 M으로 다진 백트래킹 개념을 다른 문제에도 적용시키고 싶어서 로또라는 문제를 풀어보았습니다!!!!

어려웠던 점....

1. 테스트 케이스마다 한줄 뛰우는걸 어떻게 하지....

2. 마지막 0이 나왔을 때 종료를 어떻게 하지...

3. 테스트 케이스의 수가 안주어졌는데 어떻게 하지...

백트래킹 개념적인부분 보다는 다른것들에 더 시간을 많이 잡아먹었다....

순,조에 대한 개념은 👇👇👇

https://jeniffer0812techstory.tistory.com/94

참고하면 좋을 개념들 ✍️

• exit() : 프로그램 강제 종료

for i in range(100):
    if i == 5:
        quit()
    print(i)
    
/* 
0
1
2
3
4
*/

# 11651. 좌표 정렬하기2

N = int(input())
result = []
for _ in range(N):
    x, y = map(int, input().split())
    result.append([x, y])

# for k in result:
#     print(k[-1])

for i in range(N-1):
    if result[i][-1] > result[i+1][-1]:
        result[i], result[i+1] = result[i+1], result[i]
        # print(result)
for i in range(N-1):
    if result[i][-1] > result[i+1][-1]:
        result[i], result[i+1] = result[i+1], result[i]

for s in result:
    print(*s)

처음에는 앞에것부터 비교하면서 앞에값이 뒤에값보다 크면 바꿔주는 느낌으로 로직을 구성했는데... for문을 두번 돌리니까 테스트 케이스의 답은 나왔는데 아마 히든케이스들은 다 걸려서 페일을 받았다...

아마 다른 애들은 두번으로 안되겠지..

그래서 어떤 방법으로 하면 좋을까 다시 생각해보다가...

y값을 차례로 정렬하면 되니까 먼저 받아서 소트??

내 풀 🦷

# 11651. 좌표 정렬하기2
import sys
input = sys.stdin.readline
N = int(input())
result = []

# y 값의 오름차순으로 정렬 
for _ in range(N):
    x, y = map(int, input().split())
    result.append([y, x])

result.sort()
# print(result)

for y, x in result:
    print(x, y)

결과는 성공이었다!!!! 생각보다 너무 간단하게 해결 ㅋㅋㅋㅋㅋ

그러고 다른 사람들의 풀이를 봤는데 정말 많은 사람들이 람다를 많이 사용하셨다...

잘 몰라서 못 쓰기도 했어서 이번기회에 공부하기로 했다 ^^

참고하면 좋을 개념들 ✍️

- sorted()에서 key lambda 사용 (오름차순이 기본)

• 단순히 sorted만 사용한 경우

a = [(0, 4), (1, 2), (1, -1), (2, 2), (3, 3)]
b = sorted(a)  # a.sort()와 동일
print(b)

# [(0, 4), (1,  -1), (1, 2), (2, 2), (3, 3)]
# 사실 굳이 람다로 어렵게 안 쓰고... 거꾸로 받아서 정렬하는게 더 좋은듯 ^^^^^^^^

• key 인자에 함수를 넘겨준 경우

1. 첫번째 들어있는 값을 오름차순 정렬해준 경우

a = [(0, 4), (1, 2), (1, -1), (2, 2), (3, 3)]
c = sorted(a, key = lambda x : x[0])
print(c)

# [(0, 4), (1, -1), (1, 2), (2, 2), (3, 3)]
# 앞의 인자의 오름차순으로 정렬되는것을 볼 수 있다

  2. 두번째 들어있는 값을 오름차순 정렬해준 경우

a = [(0, 4), (1, 2), (1, -1), (2, 2), (3, 3)]
d = sorted(a, key = lambda x : x[1])
print(d)

# [(1, -1), (1, 2), (2, 2), (3, 3), (0, 4)]
# 뒤의 인자의 오름차순으로 정렬되는것을 볼 수 있다

   3. 첫번째 들어있는 값은 오름차순, 두번째 들어있는 값은 내림차순 정렬해준 경우

# 내림차순은 앞에 -를 붙여주면 된다!!
e = sorted(a, key = lambda x = (x[0], -x[1]))
print(e)

# [(0, 4), (1, 2), (1, -1), (2, 2), (3, 3)]

# 11651. 좌표 정렬하기2
import sys
input = sys.stdin.readline
N = int(input())
result = []

# x값에 상관없이 y 값을 정렬 => y 값 정렬
for _ in range(N):
    x, y = map(int, input().split())
    result.append([x, y])

ans = sorted(result, key = lambda x : (x[1], x[0]))
for x, y in ans:
    print(x, y)

배운 것을 토대로 람다를 사용하여 다시 문제를 풀면 이러한 코드를 얻을 수 있다!!

다음 정렬 문제는 람다로 도전해봐야겠다 😂😂😂

오늘은 싸피에서 스택에 관해 배웠다

복습으로는 백준에 있는 스택 문제 풀기..

다 풀고 싶었는데 어제 풀다 만 브루투토스에 체스가 너무 오래 걸려서 2문제 남았다...

내일 해야지;;;;; 다음에 체스도 시간나면 적어보는걸로

서론이 너무 길었고 오늘 소개해 드릴 문제는 백준 9012. 괄호입니다!!!

오늘 swea에서도 비슷한 문제를 풀었는데 조금 쉬운 버전입니다 ^^

그럼 고 🌟🌟

6
(())())
(((()())()
(()())((()))
((()()(()))(((())))()
()()()()(()()())()
(()((())()(

NO
NO
YES
NO
YES
NO

# 9012. 괄호 - 오늘 나를 지겹게 한 ^^ : 오늘 학교에서 이거 비슷한 문제 한 2시간 머리 싸맸거덩요...
stack = [] 						# 괄호를 담을 리스트를 만들어 줬습니다
def gal(text): 					# 함수로 만드는게 조금 편해져서 만들었습니다
    for ch in text: 			# 텍스트 내부를 순회하면서
        if ch == '(': 			# 문자'('가 있으면
            stack.append(ch)	# 문자를 리스트에 추가해줍니다
        elif ch == ')':			# 문자')'가 있으면
            if len(stack) == 0: # 리스트의 길이를 확인해줘야 하는데 0이라면 열린기호가 없어서 틀린 text입니당
                return 'NO'		# 고로 NO를 반환해 줬어요
            else:				# 길이가 0이 아니라면...
                if stack[-1] == '(': 	# 스택의 마지막에 (가 있으면 
                    stack.pop()			# 마지막 (를 삭제하고
                    continue			# 계속해서 다음 문자를 확인해 줬습니다
                else:
                    return 'NO'			# 하지만 열린기호 '('가 아닌 다른게 들어있으면 틀린 문장이겠죠

    if len(stack) == 0: # 결론적으로 ')'가 나올떄 '('을 지웠으므로 쌍이 맞는다면 
    					#스택에 남아있는게 없어야 하니까
        return 'YES'	# YES를 반환합니다
    else:
        return 'NO' 	# 아니면 'NO'

import sys						# 스택 문제를 풀고 처음으로 시간초과가 떠서 알아왔습니다.. 
T = int(sys.stdin.readline())
for _ in range(T):
    bracket = sys.stdin.readline()
    stack = []  ########사실 저 위에 함수가 아니라 이부분이 틀렸는데요....
    #스택을 할때마다 초기화해줘야해요.... 틀린 값이 들어있다면 다음 사례도 틀리거등요..... 기초적인 부분이니까 꼭 기억하기!!!!

    result = gal(bracket)
    print(result)

오랜만에 백준 풀이로 돌아왔습니다 ~~~~

풀다가 제 이름 나와서 반가웠걸랑여 ^ ___________- ^

1 3 -1 4 1 7

2 -1

2 5 8 3 -4 -11

-1 2

내풀 🦷

# 19532. 수학은 비대면 강의입니다
# 연립방정식의 x, y 값을 구하라
a, b, c, d, e, f = map(int, input().split())
x = -999
y = -999
answer = []
for x in range(-999, 1000):
    for y in range(-999, 1000):
        if a * x + b * y == c and d * x + e * y == f:
            answer.append(x)
            answer.append(y)

result = ' '.join(map(str, answer))
print(result)

너무 무식하게 브루트 포스를 잘 적용해야 했다고 해야하나요 ㅋㅋㅋㅋㅋㅋㅋㅋㅋ 환장..

-999부터 999까지 중에 있다고 해서 한번 넣어봤어라 ㅋㅋㅋㅋㅋㅋ

x, y에 해당하는 값을 answer 리스트에 넣어줬고요

리스트의 대괄호 없이 나와야 하니까 조인함수를 통해 풀어줬습니다...

다른 분들 풀이를 보니까 

x와 y를 a, b, c, d, e, f를 사용해서 한쪽으로 분배를 한 후에 

for 문 없이 바로 푸셨더라구요 !!

한 수 배웠습니다👍👍

2차원 배열에서 오늘 수업 복습용으로 스터디원이 추천해줘서 풀어봤는데..

재밌는(?) 문제였습니다 🤣🤣🤣🤣🤣🤣🤣

오늘 배웠던 브루트 포스에 관해 잠시 소개해 드리며는...

고지식한 알고리즘(Brute Force)

  : 문자열을 처음부터 끝까지 차례대로 순회하면서 패턴 내의 문자들을 일일이 비교하는 방식으로 동작

 +) 고지식한 패턴 검색 알고리즘의 시간 복잡도

  : 최악의 경우 시간 복잡도는 텍스트의 모든 위치에서 패턴을 비교해야 하므로 O(MN)이 됨

  M : 찾을 패턴의 길이 / N : 전체 텍스트의 길이

# 브루토 포스 함수로 구현하기
def BruteForce(p, t):
    M = len(p)
    N = len(t)
    for i in range(N-M+1):
        for j in range(M): # 패턴의 길이만큼 순회
            # 패턴 매칭
            if t[i + j] != p[j]:
                break  # 매칭 실패
            else:
                # 검색 성공
                return i  # t인덱스 반환

    # 검색 실패
    return -1

p = 'is'
t = 'This is a book~!'

result = BruteForce(p, t) 
print(result) # 2

다음에 또 재밌는 문제 가지고 돌아올께영

10952번 A+B - 5

while True:
    # A, B = map(int, input().split())
    # print(A + B)

    # if (A == 0 & B == 0):
    #     break

    try: 
        A, B = map(int, input().split())
        print(A + B)
    
    except:
        break

주석에 있는 부분이 제가 처음에 풀었던 방법인데...

마지막에 0 출력 없이 끝나야 하는데 계속 나오더라구요...

근데 그래도 break 했으면 안 나와야 하는거 아니냐구ㅠㅠㅠㅠ

다른 방법이 있는거 같아서 다른 사람들 방법을 보니까

다들 try ~ except 를 사용하시더라구요..

처음 보는 파이썬 문법이라 찾아보았습니다

try : 에러가 발생할 것 같은, 예외처리를 하고 싶은 곳을 찾아서 try 구문에 코드를 작성합니다.
except : 에러가 발생했을 때 처리할 코드를 작성합니다.

  try:
     오늘 학교 밥이 맛없다
  except 고기가 안 익었다:
     테이크 아웃 제품 먹는다
  except 마라가 나온다:
     마트가서 사먹는다

++)

else 는 에러가 발생하지 않았을때 거치는 구문입니다. else만 단독으로 try + else 는 불가능합니다.

finally 는 에러가 발생해도, 발생하지 않아도 무조건 거치는 구문입니다.
       except 없이 try + finally 만 사용한다면
      에러가 발생한 후에 finally 구문까지만 실행이 되고 프로그램이 중간에 죽게 됩니다.

정리본 입니다...

처음으로 질문해봤습니다 ㅋㅋㅋㅋ

아시는 분 답변 달아주 3

15552번 빠른 A+B

import sys

T = int(input())
for i in range(T):
    A, B = map(int, sys.stdin.readline().rstrip().split())
    print(A+B)
    i += 1

i) 한개의 정수를 입력받을 때

import sys
a = int(sys.stdin.readline())

ii) 정해진 개수의 정수를 한줄에 입력받을 떄

import sys
a,b,c = map(int,sys.stdin.readline().split())
# map()은 반복 가능한 객체(리스트 등)에 대해 각각의 요소들을 지정된 함수로 처리해주는 함수입니다.

strip()은 문자열 맨 앞과 맨 끝의 공백 문자를 제거합니다!!

rstrip()은 오른쪽, lstrip은 왼쪽!!

빠른 입출력 방식을 알고만 있다면 정말 쉬운 문제입니다 💪

오늘 스터디 목표는 파이썬으로 조건문 문제 다 풀기 ;;

다행히 7문제고 자바로 한번씩 했던 기억이 있어서 그렇게 어렵지는 않았는데

지금 소개해드릴 문제가 좀 시간이 오래 걸렸습니다 😂😂😂

2525번 오븐 시계

# 현재 시각 한줄에 띄워서 입력
A, B = map(int, input().split())
# 걸린 시간 입력
C = int(input())

# 요리 후 시간 정의 
h = (A + ((B + C)// 60)) % 24
m = (B + C) % 60

# 출력
print(h, m)

요리 후의 시간을 정의하는 구간에서 정말 애를 많이 먹었는데...

이렇게 푸는 것도 좋은데 조건문이다 보니 if를 사용하고 싶었는데

제가 적은 코드가 VSCODE에서 출력은 나오는데 백준에서 그냥 틀렸다고 하니까 결국 조건문 없이 해결했습니다ㅜㅡㅜ

내일은 반복문 들어가보겠습니다 !!

12문제라 좀 무서운데요... 해볼 수 있는데까지 한번 해보겠습니다