수테크📱⌚️👀

문제 😵‍💫

https://school.programmers.co.kr/learn/courses/30/lessons/68935?language=java

문제 설명

자연수 n이 매개변수로 주어집니다. n을 3진법 상에서 앞뒤로 뒤집은 후, 이를 다시 10진법으로 표현한 수를 return 하도록

solution 함수를 완성해주세요

제한사항

- n은 1이상 100,000,000 이하인 자연수입니다.

입출력 예

내 풀🦷

class Solution {
    public int solution(int n) {
        String sam = Integer.toString(n, 3);
        String reverse_sam = new StringBuilder(sam).reverse().toString();
        int decimal = Integer.parseInt(reverse_sam, 3);

        return decimal;
    }
    
}

다시 알고리즘 하기로 하고 처음으로 유나가 골라준 문제라 그런지 쉬운 문제였다!!

이해력이 안 좋은데 프로그래머스는 예시를 설명해줘서 좀 더 풀기 좋은 듯 하다

10진법을 3진법 으로 바꾸고 3진법을 뒤집어서 다시 10진법으로 바꾸어서 도출!!

뒤집는 메서드인 reverse()는 파이썬과 동일하게 있다

그리고 Intger,toString()으로 바로 진법 변환할 수 있다는 것을 알게되었다!!!

다른 사람 풀이

class Solution {
    public int solution(int n) {
        String a = "";

        while(n > 0){
            a = (n % 3) + a;
            n /= 3;
        }
        a = new StringBuilder(a).reverse().toString();


        return Integer.parseInt(a,3);
    }
}

깔끔하다!!

변수명을 한 단어로 하는것도 좋은 방법일듯!!

참고하면 좋을 개념들 ✍️

• Integer.parseInt(String s) : 문자열(s)을 인자값으로 받으면 해당 값을 10진수의 Integer 형으로 변환
  ex) Integer.parseInt("1004")    // 1004
• Integer.parseInt(String s, int radix) : 숫자형의 문자열을 첫번째 인자값으로 받고 변환할 진수값을 입력하면 해당 진수에 맞춰서 Integer 형으로 변환
  ex) Integer.psrseInt("45", 3)    // 1200
• Integer.toString() : 숫자를 문자로 변환하는 형 변환 방법!!!
  ex) int num = 123;
        String str1 = Integer.toString(num);  .// 숫자가 아니고 문자 123임

문제 😵‍💫

매일 아침, 세준이는 학교에 가기 위해서 차를 타고 D 킬로미터 길이의 고속도로를 지난다. 이 고속도로는 심각하게 커브가 많아서 정말 운전하기도 힘들다. 어느 날, 세준이는 이 고속도로에 지름길이 존재한다는 것을 알게되었다. 모든 지름길은 일방통행이고, 고속도로를 역주행할 수는 없다. 세준이가 운전해야 하는 거리의 최솟값을 출력하시오

내 풀🦷

# 1446. 지름길
import sys
import heapq
input = sys.stdin.readline
INF = 1e9

n, d = map(int, input().split())
graph = [[] for _ in range(d + 1)]
distance = [INF] * (d + 1)

for i in range(d):
    graph[i].append((i + 1, 1))

# 지름길 있는 경우 인접 리스트에 추가해주기
for _ in range(n):
    s, e, l = map(int, input().split())
    # 마지막 도착지점이 실제 고속도로 보다 멀면 넘긴다
    if e > d:
        continue
    graph[s].append((e, l))

# print(graph)
distance[0] = 0
heap = [[0, 0]]
while heap:
    dist, now = heapq.heappop(heap)

    if dist > distance[now]:
        continue

    for i in graph[now]:
        mn_dist = dist + i[1]
        if mn_dist < distance[i[0]]:
            distance[i[0]] = mn_dist
            heapq.heappush(heap, (mn_dist, i[0]))

print(distance[d])

역주행이 안되는데 들어오기는 실제 고속도로보다 먼곳도 들어오고해서 어떻게 처리해줘야 할지 고민을 오래했다... 그리고 지름길이 있지만 더 멀어서 이용을 안 하는 경우는 어떻게 처리해야할까 고민을 했다...

가장 먼저 모든 두 길이1만큼 갈때 1이 걸린다고 초기화해줬고... 지름길 값을 입력하면서 역주행은 할 수 없으므로 마지막 값이 고속도로의 끝을 넘어버리는 경우는 넣어주지 않았다... 

그리고 나머지는 우리가 아는 다익스트라를 사용해서 구현하면 끝!!! 😊😊😊

참고하면 좋을 개념들 ✍️

Dijkstra

1. 작동원리

• 간선 : 인접 리스트, 거리 배열 : 초기값 무한대로 설정, 힙 시작점 추가
• 힙에서 현재 노드 빼면서, 간선 통할 때 더 거리가 짧아진다면 거리 갱신 및 힙에 추가해준다
• 힙 : 최댓값, 최솟값을 빠르게 찾을 수 있는 자료 구조

2. 기본 코드

# 더익스트라 구현하기

# k : 시작점
# dist : 거리배열

dist[k] = 0 
heapq.heappush(heap, (0, K))

while heap:
	w, y = heapq.heappop(heap)
    if w > dist[v] : continue
    for nw, nv in edge[v]:
    	if dist[nv] > dist[v] + nw:
        	dist[nv] = dist[v] + nw
            heapq.heappush(heap, dist[nv], nv))

3,  아이디어

• 한점에서 다른 모든 점으로의 최단 경로 > 다익스트라 사용
• 모든 점 거리 초기값 무한대로 설정
• 시작점 거리 0 설정 및 힙에 추가
• 힙에서 하나씩 빼면서 수행할 것
• 현재 거리가 새로운 간선을 거칠때보다 크다면 갱신
• 새로운 거리힙에 추가!!!

문제 😵‍💫

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

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

문제 😵‍💫

수빈이는 동생과 숨바꼭질을 하고있다. 수빈이는 현재 점N에 있고 동생은 점 K에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다, 순간이동을 하는 경우에는 1초 후에 2 * X의 위치로 이동하게 된다

수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오.

입력!

첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다.

출력!

수빈이가 동생을 찾는 가장 빠른 시간을 출력한다.4

내 풀🦷

# 1697. 숨바꼭질
from collections import deque
def bfs(start, depth):
    visited = [0] * 100001
    q = deque()
    q.append((start, depth))
    visited[start] = 1
    while q:
        s, d = q.popleft()

        if s == K:
            return d

        for nxt_s in [s-1, s+1, s*2]:
            if 0 <= nxt_s <= 100000 and (not visited[nxt_s] or visited[nxt_s] > d+1):
                q.append((nxt_s, d+1))
                visited[nxt_s] = d+1

N, K = map(int, input().split())
visited = [0] * K
result = dfs(N, 0)
print(result)

 처음에 도대체가 어떻게 접근해야할지도 모르겠고 dp나 while문으로 풀어야겠다 싶었는데 알고보니 bfs 문제였다ㅜㅜ

시작점과 깊이를 넣어서 시작점이 끝점과 같아지면 return으로 깊이를 받아주면 최소값을 구할 수 있다!!

어려웠던 부분은 방문 했던 곳 또는 깊이가 더 깊은곳과 그전까지의 깊이에 해당하는 값이 같았을때는 배제해 주어야 한다는 것이었다... 다른 분들 코드를 보았을때는 이미 방문한곳을 continue로 넘겨서 간단히 해결해 주는것을 볼 수 있었다...어떻게 풀어야할지까지 고민한 문제는 오랜만이라 더욱 힘들었다 😂😂😂😂

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

재귀, 백트래킹, 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