알고리즘

[python] 백준 - 11085. 군사 이동

🤔문제 해결 크루스칼 C에서 출발! 갈 수 있는 곳을 찾아서 우선순위 큐에 넣는다. 우선순위 큐에서 넓이가 가장 넓은 녀석을 뽑는다. 거기서 또 갈 수 있는 곳을 찾아서 큐에 넣는다. (단, 재방문 X) V를 만나면 끝! 노드를 이동하는 동안 최소값을 계속 갱신해준다. (답을 찾아야하므로) 💻소스 코드 import sys from collections import defaultdict import heapq input = sys.stdin.readline P, W = map(int, input().split()) # P개의 지점, W개의 길 C, V = map(int, input().split()) # C 백준수도, V 큐브수도 # 인접노드 만들기 nodes = [input() for _ in range..

[python] 백준 - 1174. 줄어드는 숫자

🤔문제 해결 못풀다가 문제 유형에 백트래킹이 있길래 힌트를 얻어 백트래킹으로 구현해봤다. 아이디어는 현재 숫자의 끝자리보다 낮은 숫자들을 뒤에 추가하는 재귀함수를 만들었다. 현재 764이면 7640 => 끝 7641 => 76410 => 끝 7642 => 76420 => 76421 => 764210 => 끝 마지막에 sort만 해주면 빠른 시간 내에 모든 경우의 수를 순서대로 다 얻을 수 있다. 가끔 안풀리면 다른 사람의 코드를 참고하기 전에 유형으로 힌트를 얻어보자😀 💻소스 코드 N = int(input()) # 백트래킹을 이용한 문제 풀이 def bt(cur): answer.append(int(cur)) for j in range(0, int(cur[-1])): # 현재 숫자의 끝자리보다 낮은 숫자들..

[python] 백준 - 1148. 단어 만들기

🤔문제 해결 딕셔너리에 퍼즐의 각 알파벳을 키, 그 알파벳의 개수와 사용된 횟수의 딕셔너리를 벨류로 가진다. 퍼즐에 있는 알파벳으로 낱말을 만들 수 있다면 퍼즐에서 사용될 알파벳의 used_cnt 를 +1 해준다. 위와 같은 결과가 나오게 되고, used_cnt 가 가장 적은 값들, 가장 많은 값들을 알파벳 오름차순으로 출력해준다. 💻소스 코드 import pprint import sys input = sys.stdin.readline # 인풋 받아서 단어 or 퍼즐 따로 배열로 만드는 함수 (두번 반복할거 같아서 함수로 만듦) def input_func(arr, sign): arr = [] while True: input_value = input().strip() if input_value == sig..

[javascript] 프로그래머스 - 행렬 테두리 회전하기(2021 Dev-Matching: 웹 백엔드 개발자(상반기))

🤔문제 해결 Array.from 을 이용하여 2차원 행렬 만들기 테두리 가져오기 범위 내에서 테두리만 오른쪽, 아래, 왼쪽, 위로 차례로 이동 이동하면서 값을 리스트에 저장, 2차원 배열의 값을 바꿔준다(회전) 리스트의 가장 작은 값을 answer 에 저장 💨 2차원 배열 만들기 Array.from, 배열의 최소값 구하기 Math.min.apply(null, []); 이것 보다는 Math.min(...[]); 이 좋아보임(일단 가독성) 💻소스 코드 function solution(rows, columns, queries) { var answer = []; // 1씩 증가하는 2차원 행렬 만들기 const arr = Array.from(Array(rows), () => new Array(columns));..

[javascript] 프로그래머스 - 로또의 최고 순위와 최저 순위(2021 Dev-Matching: 웹 백엔드 개발자(상반기))

🤔문제 해결 1. filter와 includes를 이용해서 로또 번호가 당첨 번호에 포함된 개수를 구함 2. filter를 이용해서 로또 번호의 0의 개수를 구함 3. 최소 당첨 개수는 그냥 당첨 개수 4. 최대 당첨 개수는 최소 당첨 개수 + 0의 개수 5. 순위를 구함 💨 💻소스 코드 function solution(lottos, win_nums) { var answer = []; var minWinningCnt = lottos.filter(number => win_nums.includes(number)).length; var maxWinningCnt = minWinningCnt + lottos.filter(number => number === 0).length; var rank = [6, 6, 5,..

[python] 프로그래머스 - 약수의 개수와 덧셈

🤔문제 해결 1. 나의 풀이 약수의 개수를 구하는 방법: 소인수 분해를 하고, 그 거듭제곱에 +1을 하면 약수가 나온다. 거듭제곱이 2개 이상이라면, 각각의 거듭제곱에 +1을 하고 그 숫자들을 서로 곱해준다. 2. 다른 좋은 풀이 모든 숫자는 약수의 개수가 짝수개이다. 예외로 제곱수는 약수의 개수가 홀수이다. 제곱이기 때문... 💨 디폴트딕트와 리듀스까지 써가면서 열심히 풀었지만, 수학을 잘하면 저렇게 쉽게 풀 수 있다....😜 💻소스 코드 from collections import defaultdict from functools import reduce def solution(left, right): """ 약수의 개수를 구하는 방법: 소인수 분해를 하고, 그 거듭제곱에 +1을 하면 약수가 나온다. 거..