khakha's dev log

문제 https://www.acmicpc.net/problem/1182 1182번: 부분수열의 합 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net 접근 백트래킹으로 모든 경우의 수의 합을 구해준다. 합이 s와 같으면 answer ++ 해서 부분수열의 갯수를 구해주먄된당 코드 n, s = map(int ,input().split()) number = list(map(int ,input().split())) answer = 0 def dfs(i,total,number,visited): global ans..

문제 https://www.acmicpc.net/problem/1697 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 접근 큐 자료구조를 이용하는 BFS로 풀이하면 최단 경우의 수(거리?)를 구할 수 있는 것을 잘 생각하면 코드 자체는 쉽다. 1. 큐에 있는 수 중에 k가 나올 때까지 while문은 돌게 된다. 2. 이동할 수 있는 방법은 +1, -1, *2이므로 항상 세 지점에 도달하는 시간을 계산하면서 queue에 넣어준다. 코드 from collections import de..

문제 https://school.programmers.co.kr/learn/courses/30/lessons/43238 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 접근 이분탐색 풀이 범위 : 심사에 걸리는 최소 시간 ~ 심사에 걸리는 최대 시간 * 사람 수 mid : 임의의 시간, mid // time 은 임의의 시간동안 해당 심사대가 심사할 수 있는 사람 수를 계산한 것 기준 : mid 동안 심사한 사람 수(people)이 n보다 크거나 같으면 시간이 충분한 것이므로, right 조정 mid 동안 심사한 사람 수(people)이 n보다 작으면 시간이..

문제 https://school.programmers.co.kr/learn/courses/30/lessons/42885?language=python3 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 접근 투포인터 이용한 풀이 먼저 주어진 배열을 오름차순으로 정렬해준다. 몸무게가 가벼운 순으로 정렬되었기 때문에 시작포인터(가장 가벼운 사람) = 0, 끝포인터(가장 무거운 사람) = 마지막 로 설정해준다. 1. 시작 = 끝 이면 한명 태우고(cnt + 1), 모든 사람 구조한거기 때문에 종료 2. 시작 몸무게 + 끝 몸무게 limit 이면, 끝 몸무게(무거운 ..

문제 https://school.programmers.co.kr/learn/courses/30/lessons/42883?language=python3 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 접근 stack을 이용한 풀이 while문 조건으로 (k 횟수가 남았고 stack 마지막 숫자가 n보다 작을 경우), stack.pop() 을 해주면서 가장 작은 숫자를 k 횟수만큼 제거해준다. 코드 def solution(number, k): stack = [] for n in number: # stack 길이가 0일 때 stack[-1]은 인덱스에러를 뱉기 ..

문제 https://school.programmers.co.kr/learn/courses/30/lessons/43164 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 접근 1. 출발지를 key, 도착지 배열을 value로 하는 dict 생성 2. 도착지를 내림차순으로 정렬해준다. -> stack.pop()을 사용하면 알파벳 순서대로 확인할 수 있음. 3. 시작지는 ICN이므로 stack에 넣고 시작 출발지가 dict에 없거나 (출발할 수 없는 공항, 즉 맨 마지막 도착지가 되는 경우) 더이상 이동할 공항이 없거나 위 두가지 경우, path에 stack.p..

문제 https://school.programmers.co.kr/learn/courses/30/lessons/43162?language=python3 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 접근 dfs로 풀이했다. 1. 방문 배열 만들어준다. 2. 모든 노드를 탐색하면서 방문하지 않은 노드 (연결되지 않은 노드 포함)는 dfs로 탐색 시작. 3. dfs 함수를 빠져나오면 연결된 네트워크 덩어리가 하나 생겼다는 것이므로 +1 해준다. 코드 def dfs(visit, index, computers): visit[index] = 1 # 방문처리 for ..

문제 https://school.programmers.co.kr/learn/courses/30/lessons/43165 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 접근 재귀 활용. 문제에 주어진 예시는 numbers [1,1,1,1,1] target 3 return 5 이다. dfs(0,0)으로 시작하면 재귀함수를 통해서 depth 1 : (0 + 1) + (0 - 1) depth 2 : (0 + 1 + 1) + (0 + 1 - 1) + (0 - 1 + 1) + (0 - 1 - 1) depth 3 : (0 + 1 + 1 + 1) + (0 + 1 + 1..

문제 https://school.programmers.co.kr/learn/courses/30/lessons/43105 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 접근 1. dp 배열에 값을 메모이제이션 후, 삼각형 맨 마지막까지 이동하면서 dp 배열 값과 삼각형 다음 줄의 왼쪽, 오른쪽을 더한 값을 계산해준다. 2. 삼각형 마지막 줄에서 최댓값을 찾아준다. 코드 def solution(triangle): dp = [[0 for _ in range(len(triangle[i]))] for i in range(len(triangle))] dp[0][0]..

문제 https://school.programmers.co.kr/learn/courses/30/lessons/42898 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 접근 유의할점 : m,n 인덱스 값이 반대로 주어짐. 처음에 dfs로 풀었다가 답은 어찌저찌 나오는데 유효성테스트에서 시간초과로 안풀리는 듯 했다. 확통 경우의 수에서 최단 경로 구하는 방식을 dp에 적용해서 쉽게 풀리는 풀이를 참고하여 해결하였다. 위에서 아래, 왼쪽에서 오른쪽으로만 이동해서 마지막 칸까지 가장 최단 경로 경우의 수는 다음과 같이 구할 수 있다. dp[i][j] = dp[i..