수테크📱⌚️👀

문제 😵‍💫

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

• 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
*/

유튜버 딩코딩씨 보고 정리해보는 순열과 조합...

재귀, 백트래킹, dfs... 등등 정말 많이 연관되어있어서 정리하면 좋을것 같아 올려봅니다...

##### permutation(순열)

'''
순열 : permutation(포함되어 있는 수가 같은 수여도 순서가 다르면 다른걸로 친다)
dfs 트리와 체크리스트 사용

3개의 공 중에 2개를 뽑는 경우(3P2)
사용한 경우 넣으면 안되므로 체크리스트 사용하는 것임....
깊이 + 1 한후 길이에 맞는 값을 리턴을 하고나면
다시 체크리스트에 빼줘서 다시 넣을 수 있도록 해준다..

1 2
1 3
2 1
2 3
3 1
3 2
6가지
'''

def dfs(L):
    # 종료 조건
    # 리스트의 길이가 찾아야 할 개수(r)가 된다면 종료
    if L == r:
        print(result)
    else:
        for i in range(len(n)):
            # 체크리스트에 해당하는 값이 없다면
            if checklist[i] == 0:
                # result 리스트에 값을 추가
                result[L] = n[i]
                # 체크리스트에 값이 생겼다고 표시해주기
                checklist[i] = 1
                # 다음 깊이로 이동
                dfs(L+1)
                # 다음 번에 다시 사용하기 위해서 빼준다고 그냥 생각하셈 ^^;;;
                checklist[i] = 0

n = [1, 2, 3]
r = 2
result = [0] * r
checklist = [0] * len(n)
dfs(0)

이해도 이해지만 어느정도 외울만큼은 외우라고 하심...

이해해야 외우지 싶다가도 이러다가 진도가 영 안나갈거 같아서 적당히 이해시켜서 외우는것이 좋을 듯...

'''
조합 : 같은 숫자가 포함되어 있으면 같은 걸로 인정....
순열보다 경우의 수가 훨씬 작음...
순열보다 더 간단...
한번 썼으면 다시 쓰지를 않으니까 체크리스트도 필요없음...
DFS 트리를 이용해서 푼다

3C2

1 2
1 3
2 3

3가지
'''
def dfs(L, BeginWith):
    # 종료 조건
    if L == r:
        print(*result)
    else:
        for i in range(BeginWith, len(n)): # 시작하는 값부터 끝까지
            result[L] = n[i] # 해당하는 값을 넣어주기
            dfs(L+1, i+1) # 다음 깉이 다음 숫자로 이동하여 전 값을 들어오지 못하도록


n = [1, 2, 3]
r = 2
result = [0] * r

dfs(0, 0) # level, begin(어디서 시작할지)

# 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)

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

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

오늘 친 시험 문제중에 bfs, dfs  문제 해결을 하지 못해서 복습 하려다가 시험 친 기념으로(?)😂😂😂

단계별 위에 안 푼거 중에 7단계 일반수학을 마무리하기로했다!!! 

대부분 브론즈고 규칙만 찾으면 해결 가능한 간단한 문제인데 분수찾기가 골머리가 조금 아팠다 ^________^

문제🤔

내 풀🦷

# 1193. 분수 찾기
N = int(input())

line = 0 # 대각선 갯수
idx = 0 # 마지막 인덱스 (1, 3, 6, 10...)
while idx < N:
    line += 1
    idx += line # 마지막 인덱스는 라인에 있는 분자의 갯수 만큼 늘어난다

result = []
# 라인 홀수일 떼
if line % 2:
    ja = idx - N + 1     # 분자
    mo = line - idx + N  # 분모
    result.append(ja)
    result.append('/')
    result.append(mo)
else:
    ja = line - idx + N
    mo = idx - N + 1
    result.append(ja)
    result.append('/')
    result.append(mo)
    
print(''.join(map(str, result)))

뭔가 느낌적인 느낌은 알겠는데 찾기 쉽지 않았지만 분수를 하나하나 적고 뜯어보면 규칙을 찾을 수 있었다!!  ㅜㅜㅜ

N만을 가지고 분자와 분모를 어떻게 적어야할지를 제일 고민을 많이 했던 부분인것 같다.....

ja = 분자 / mo = 분모 입니다 ㅋㅋㅋ

참고함면 좋을 개념들 ✍️

• 리스트를 다양한 방법으로 출력하기

result = [1, 2, 3, 4]
# 공백없이 출력
print(''.join(map(str, result)))   # 1234
# 공백있이 출력
print(' '.join(map(str, result)))  # 1 2 3 4
# , 쉼표로 연결하여 출력
print(', '.join(map(str, result))  # 1, 2, 3, 4
# 언패킹
print(*result)                     # 1 2 3 4

5
4 1 5 2 3
5
1 3 7 9 5

1
1
0
0
1

틀린 내 풀🦷

# 1920. 수찾기
import sys
input = sys.stdin.readline

N = int(input())
arr = list(map(int, sys.stdin.readline().split()))

M = int(input())
arr_2 = list(map(int, sys.stdin.readline().split()))
result = []

for j in range(M):
    one = []
    for i in range(N):
        if arr[i] == arr_2[j]:
            one.append(1)
            break
        else:
            one.append(0)

    # print(one)
    cnt = 0
    for k in one:
        if k == 1:
            cnt += 1
    if cnt >= 1:
        result.append(1)
    else:
        result.append(0)

for k in result:
    print(k)

구직구직하게 짜기 달인이 되버린 나,,,,

단계별 풀이로 안들어가고 성공률로 들어가서 안 풀어져 있는거 풀어가지고

어떤 방식으로 풀어야하는지 힌트(이차원 배열이다, 정렬이다, 이진탐색이다 이런거)가 없어서 어카지 하다가

찾아야할 값이 주어진 arr_2 리스트를 돌라면서 arr을 돌리는 완전 탐색으로 찾아서 있으면 더해주면 되겠다..

싶었고 무슨일로 인덱스 아웃오브레인지도 안나고 한번에 성공했는디.... 했는데.... 제출했는데...

했는데 시간초과가 나버렸다 ㅋㅋ 혹시나 몰라서 import sys로도 바꿔봤는데 실패....ㅜㅜ

수정된 내 풀🦷

백준에서 풀다가 막히면 질문게시판 들어가서 종종 힌트를 얻는데

나처럼 구질구질하게 푸는 사람이 없었고 ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ

set을 사용하여 입력받아 시간을 적게 걸리게 하는 방법이나 이진 탐색을 사용하였다!!

그러고 보니 이진 탐색을 이용하면 되었는데 혼자서 브로노마스(무지성)으로 하고있었다....

그래서 먼저 해본 set() 으로 입력 받기 =>

N = int(input())
arr = set(map(int, input().split())) # 출력 시간을 줄이기 위해 set 받음

M = int(input())
arr_2 = list(map(int, input().split()))

for i in arr_2:
    if i in arr: print(1)
    else: print(0)

결과는 성공~~~~~

set을 자주 안 쓰다보니 어떤 부분에서 쓸지 몰랐는데

입력을 set으로 받아 사용한다는 점을 알게 되었다!!

이진탐색으로 풀은 내 풀🦷

또 다른 방법중에 하나인 바이너리 서치를 통한 방법도 많이 보여서 도전해 보았다~~

N = int(input())
arr = list(map(int, input().split()))
arr.sort() # 이진탐색은 정렬된 것들 탐색하는데 이 부분 기억을 못해서 무한 루프로 몇번 다녀왔다
M = int(input())
arr_2 = list(map(int, input().split()))

for i in arr_2:
    # 바이너리 서치 활용하기(이진탐색)
    result = False 
    start = 0 # 시작 인덱스
    end = N - 1 # 끝 인덱스

    while start <= end:
        mid = ((start + end) // 2) # 중간값의 위치에 해당하는 수와 목표 비교해 나감
        if i == arr[mid]: # 중간값과 목표값이 같다면
            result = True
            break
        elif i > arr[mid]:
            start = mid + 1
        else:
            end = mid - 1

    if result:
        print(1)
    else:
        print(0)

시험에도 나오기는 했지만 오랜만에 이진탐색을 사용해서 계속 틀린값이 나오고

무한루프로 잠시 먼나라이웃나라 다녀왔다....

중간값과 목표값을 비교하면서 시작점이 마지막점보다 넘어서면 종료되는 기저조건을 설정하였다!!!!

참고함면 좋을 개념들 ✍️

1) 이진 검색(Binary Search)

:  자료의 가온데에 있는 항목의 키 값과 비교하여 다음 검색의 위치를 결정하고 검색을 계속 진행하는 방법

 => 목적 키를 찾을 때까지 이진 검색을 순환적으로 반복 수행함으로써 검색 범위를 반으로 줄여가면서 보다 빠르게 검색을 수행한다

- 이진 검색을 하기 위해서는 자료가 정렬된 상태여야 한다(정렬이 아니라 뒤에 수가 앞에 수보다 커버리면 오바자나.. 찾을 수가 없음!!!!!! 주의!!!!!!!!1..)

- 검색 과정

1. 자료의 중앙에 있는 원소를 고른다
2. 중앙 원소의 값과 찾고자 하는 목표 값을 비교한다
3. 목표값이 중앙 원소의 값보다 작으면 자료의 왼쪽 반에 대해서 새로 검색을 수행, 크다면 자료의 오른쪽 반에 대해서 세로 검색을 수행
4. 찾고자 하는 값을 찾을 떄까지 1~3의 과정을 반복한다
5. 찾는다면 성공, 못 찾으면 실패

- 구현

• 검색 범위의 시작점과 종료점을 이용하여 검색을 반복 수행한다 => while의 종료 조건을 잘 설정하기
• 이진 검색의 경우, 자료에 삽입이나 삭제가 발생했을 때 배열의 상태를 항상 정렬 상태로 유지하는 추가 작업이 필요

# 이진 검색 알고리즘
def binarySweach(a, N, key):
	start = 0  # 시작점 
    end = N -1  # 종료점
    while start <= end:
    	middle = (start + end) // 2 # 몫으로 하는 이유 : 나누기 연산자를 사용하면 .0으로 float되걸랑
        if a[middle] == key: # 검색 성공
        	 return true
        elif a[middle] > key:
        	 end = middle - 1
        else:
        	start = middle + 1
    return flase # while 문을 다 돌았는데도 찾지못한다면 검색 실패

# 재귀함수로 부분집합 만들기
# bits: 해당 인덱스의 요소를 사용할지의 유무 (1은 사용하고 0은 아님)
# depth : 내가 얼마나 함수를 재귀호출했는지에 대한 카운트 값...
def recur(bits, depth):
    # 기저 조건
    if depth == N:
        for i in range(N):
            if bits[i] == 1:
                print(arr[i], end=' ')
        print()
        return

    for i in range(2): # 0, 1
        bits[depth] = i
        # 자기 자신을 호출
        recur(bits, depth + 1)


N = 4
arr = [1, 2, 3, 4]
recur([0] * N, 0)

# result
4 
3 
3 4 
2 
2 4 
2 3 
2 3 4 
1 
1 4 
1 3 
1 3 4 
1 2 
1 2 4 
1 2 3 
1 2 3 4

재귀함수 너무 어려워요오....제제제.....기.........랄,,,,

여기서 제일 중요한 포인트는 [0, 0, 0, 0] 배열을 끝까지 만들어주고 역으로 만들어져 나가는 느낌이라는거?

return을 받았을 때, 제일 처음이 아닌 자신을 호출했던 곳으로 돌아가 0이 아니라 1인 경우를 만들어준다는거??

그래서 답을 출력했을때, 리스트에 가장 먼저 저장된 1이 아니라 4가 나오는 부분이 정말 중요 포인트인거 같다...

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

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

다 풀고 싶었는데 어제 풀다 만 브루투토스에 체스가 너무 오래 걸려서 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)