코테

[javascript] 프로그래머스 - 단어 변환

🤔문제 해결 Lv3 | BFS begin 에서 시작하여 BFS 탐색 BFS는 target과의 거리를 알 수 있으므로 target과의 최단거리를 구해서 답을 출력 아래의 코드에서는 visited와 words_obj를 사용했지만 잘 짜보면 words_obj 하나로 충분히 구현할 수 있다! 💻소스 코드 function solution(begin, target, words) { var answer = 0; // 타겟이 워드에 없는 경우 if (!words.includes(target)) { return answer } let n = words.length // visited 와 queue let visited = Array(n).fill(0) let q = [begin] // 단어의 인덱스를 객체에 저장 con..

[python] 백준 - 5430. AC

🤔문제 해결 S2 | 자료구조, 데크, 구현 리버스와 제거 두가지 오더가 있다. 리버스를 하게 되면 O(N)의 시간복잡도 발생 그러므로 리버스를 하지말고 이게 뒤집힌 상황인지 아닌지만 구분해준다. 그 후 그대로이면 맨 앞의 숫자를 제거하고 뒤집힌 상황이면 맨 뒤의 숫자를 제거한다. 💻소스 코드 from collections import deque for tc in range(int(input())): # RR이면 원래상태이므로 제거해줌 order = input().replace('RR', '') n = int(input()) number = input()[1:-1] if number: number = deque(list(map(int, number.split(',')))) # R은 뒤집지 말고 my_re..

[python] 백준 - 2004. 조합 0의 개수

🤔문제 해결 S2 | 수학 진짜 팩토리얼로 구해서 문제를 해결하게 되면 시간초과 발생 끝자리가 0이라는 것은 10의 배수 10은 2와 5로 구성되어 있음 2와 5 짝이 맞아야 10이 되므로 2의 개수와 5의 개수중 더 작은게 10의 개수이다. 💻소스 코드 N, M = map(int, input().split()) # 진짜 팩토리얼로 구해서 문제를 해결하게 되면 시간초과 발생 # 끝자리가 0이라는 것은 10의 배수 # 10은 2와 5로 구성되어 있음 # 2와 5 짝이 맞아야 10이 되므로 2의 개수와 5의 개수중 더 작은게 10의 개수이다. def count_number(n, k): count = 0 while n: n //= k count += n return count five_count = count..

[python] 백준 - 2110. 공유기 설치

🤔문제 해결 S2 | 이분탐색 특정 범위 안에서 개수를 정한다? => 이분 탐색 공유기를 설치할 수 있는 최소간격과 최대간격의 중간값부터 시작 중간값(공유기 설치 간격)으로 공유기를 설치 했을 때 설치한 공유기가 부족하면 설치 간격을 좁혀서 더 많이 설치하자 설치한 공유기가 많거나 같으면 설치한 간격을 늘려서 덜 설치하거나 최대로 간격을 늘려보자 💻소스 코드 import sys N, C = map(int, input().split()) house = [int(sys.stdin.readline()) for _ in range(N)] # 정렬 house.sort() # 와이파이 간격을 얼마나 해야할지 모르니 최대거리와 최소거리의 중간부터 시작 left = 1 right = house[-1] - house[0..

[python] 백준 - 1965. 상자 넣기

🤔문제 해결 S2 | DP [python] 백준 - 11055. 가장 큰 증가 부분 수열 🤔문제 해결 S2 | 다이나믹프로그래밍 역시 이런 문제는 DP문제이다. dp 리스트를 만든다.(1차원, 인풋값으로 받은 수열과 똑같은 값으로 만든다.) 수열에서 자신보다 앞 쪽에 있는 값 중에서 자신 deok2kim.tistory.com 위의 문제와 살짝 비슷한 느낌이다. 값이 1로 셋팅된 길이가 n 인 dp 리스트를 만든다. dp = [1, 1, 1, ... ] 각각의 값은 현재 포함한 상자의 갯수이다. 맨앞의 상자부터 하나씩 뒤로가며 앞의 상자를 몇개나 담을 수 있는 지 체크한다. 만약 내앞의 상자가 나보다 작고 그 상자가 담고 있는 상자의 갯수(본인포함)가 5개라면 지금 나의 상자는 앞의 상자까지 담을 수 있으..

[python] 백준 - 1890. 점프

🤔문제 해결 S2 | DP DFS로 해봤지만 역시나 시간초과!! 시간복잡도가 O(N^2) 인 DP로 풀어봤다. dp에는 현재 위치까지 올 수 있는 경우의 수를 담아서 해결함. 💻소스 코드 N = int(input()) field = [list(map(int, input().split())) for _ in range(N)] answer = 0 dp = [[0] * N for _ in range(N)] # i,j까지 올 수 있는 경우의 수를 저장 dp[0][0] = 1 for i in range(N): for j in range(N): if i == N - 1 and j == N - 1: # 끝에 도달했을 때 print(dp[i][j]) break cur_cnt = field[i][j] # 오른쪽으로 가기..