📁문제 풀이

[JAVA] 백준 2961 도영이가 만든 맛있는 음식

~목차~ 문제 문제 해결 포인트 작성 코드 문제 https://www.acmicpc.net/problem/2961 2961번: 도영이가 만든 맛있는 음식 첫째 줄에 재료의 개수 N(1 ≤ N ≤ 10)이 주어진다. 다음 N개 줄에는 그 재료의 신맛과 쓴맛이 공백으로 구분되어 주어진다. 모든 재료를 사용해서 요리를 만들었을 때, 그 요리의 신맛과 쓴맛은 www.acmicpc.net 문제 해결 포인트 - DFS, 완전 탐색 - 신맛과 쓴맛을 저장한 배열을 하나씩 방문하며 넣을지 안 넣을지 확인한다 - 모든 음식을 넣을지 안 넣을지 확인하였을 때, 쓴맛과 신맛의 차이가 answer보다 작다면 answer를 업데이트 - 완전 탐색 후 answer를 출력 작성 코드 import java.util.*; import..

[Python] 백준 1654 랜선 자르기 | 이진 탐색 | 시간 초과

~목차~ 문제 문제 해결 포인트 작성 코드 문제 https://www.acmicpc.net/problem/1654 1654번: 랜선 자르기 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 www.acmicpc.net 문제 해결 포인트 - N의 범위가 크므로 이진탐색으로 풀이해야 한다. - 길이가 가장 긴 랜선을 end값, 0을 start값으로 두고 중간 값으로 mid를 선언한다. - start와 end가 교차되는 지점에서 종료하는 while문을 작성하여 최대 길이를 찾는다. - mid를 기준으로 모든 랜선 별 생성되는 랜선 개수를 모..

[Python] 프로그래머스 괄호 변환 | DFS

~목차~ 문제 작성 코드 문제 https://school.programmers.co.kr/learn/courses/30/lessons/60058 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 작성 코드 def check(par): # 올바른 괄호 문자열인지 확인하는 함수 stack = [] for p in par: if p == '(': stack.append('(') # '('라면 스택에 삽입 elif p == ')' and stack: stack.pop() # ')'이면서 스택에 괄호가 있으면 출력 else: return False # ')'이면서 s..

[Python] 프로그래머스 피보나치 수 | DP

~목차~ 문제 문제 해결 포인트 작성 코드 문제 https://school.programmers.co.kr/learn/courses/30/lessons/12945 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 해결 포인트 - 전형적인 DP(Dynamic Programming, 다이나믹 프로그래밍) 문제 한 번 계산한 결과에 대해 저장해두어 이후 다시 계산하지 않는다 - 0 ~ n 피보나치 수를 저장할 리스트 선언 후 0과 1에 대하여 초기값 설정 - 2 ~ n까지 f(n) = f(n-1) + f(n-2)를 수행 - dp[n]을 반환하되 1234567..

[Python] 프로그래머스 다음 큰 숫자

~목차~ 문제 문제 해결 포인트 작성 코드 문제 https://school.programmers.co.kr/learn/courses/30/lessons/12911 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 작성 코드 def solution(n): cnt1 = str(bin(n)[2:]).count("1") for answer in range(n + 1, 1000001): if cnt1 == str(bin(answer)[2:]).count("1"): return answer bin 내장 함수에 대해 더 알고 싶다면 다음 글 참고하세요! 2023.02.1..

[Python] 프로그래머스 단어 변환 | BFS

~목차~ 문제 문제 해결 포인트 작성 코드 문제 https://school.programmers.co.kr/learn/courses/30/lessons/43163 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 작성 코드 from collections import deque def solution(begin, target, words): if target not in words: return 0 wordlen = len(begin) def diff1(w1, w2): # 두 단어가 알파벳 하나만 다른지 판별하는 함수 cnt = 0 for i in range(..

[Python] 프로그래머스 숫자의 표현 | DP

~목차~ 문제 문제 해결 포인트 작성 코드 문제 https://school.programmers.co.kr/learn/courses/30/lessons/12924 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 해결 포인트 - 1 ~ 10000를 표현할 수 있는 연속된 수를 모두 찾아 그 개수를 각 리스트에 저장한다. - 본인 자신으로 표현할 수 있으므로 표현 가능한 연속 수는 1개 이상이다. - 연속 수로 표현할 수 있는 수는 2중 for문으로 찾아 각 인덱스 리스트에 +1 수행 가장 바깥 for문은 연속 수의 첫번째 수 두번째 for문은 숫자를 순..

[Python] 프로그래머스 이진 변환 반복하기

~목차~ 문제 작성 코드 문제 https://school.programmers.co.kr/learn/courses/30/lessons/70129 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 작성 코드 풀이 1 def solution(s): answer = [0, 0] def binary_trans(x): # 입력된 숫자를 2진수로 변환 하는 함수 answer = "" while x > 0: answer += str(x % 2) x //= 2 return answer while s != "1": # 1이 되기 전까지 반복 temp = s.count("0"..

[Python] 백준 9655 돌 게임 | DP

~목차~ 문제 문제 해결 포인트 작성 코드 문제 https://www.acmicpc.net/problem/9655 9655번: 돌 게임 상근이가 게임을 이기면 SK를, 창영이가 게임을 이기면 CY을 출력한다. www.acmicpc.net 문제 해결 포인트 - DP(다이나믹 프로그래밍) - 기록을 위한 dp 배열 : 0은 SK, 1은 CY를 의미 - N이 1일 때 : SK N이 2일 때 : SK -> CY N이 3일 때 : SK 또는 SK -> CY -> SK 이므로 결론적으로 SK N이 4일 때 : 1일 때 결과와 다른 사람 또는 3일 때 결과와 다른 사람, 결론적으로 CY ...... - 점화식 N이 4이상일 때, ai = (ai-1 + 1) % 2 또는 ai = (ai-3 + 1) % 2 작성 코드 ..