본문 바로가기

알고리즘

 (54)
127. Word Ladder 문제의 조건에서 중요한 점 시작 단어는 리스트에 들어가지 않는다. 한번에 하나의 단어만 바뀔 수 있다. 끝 단어가 단어리스트에 존재해야만 한다. 없을시 0 리턴 bfs인데 다음 원소가 조건에 따라 달라지는 형태의 bfs 한번의 bfs에서 될 수 있는 모든 단어를 찾아야한다. 따라서 for문의 첫번째는 단어 두번째는 모든 알파벳에 대하여 탐색한다. 그리고 변할 수 있는 단어를 찾으면 그 단어를 set에서 지운다. const ladderLength = function (beginWord, endWord, wordList) { // 없으면 컷. if (!wordList.includes(endWord)) return 0 const wordSet = new Set(wordList) let queue = [begi..
136. Single Number 느낌이 다른 풀이 3가지 const singleNumber = function(nums) { const obj = {} for (let num of nums) { obj[num] ? obj[num]++ : obj[num] = 1 } for (const [k, v] of Object.entries(obj)) { if (v == 1) { return k } } };function singleNumber(nums) { const map = {}; for (let n of nums) { if (map[n] == null) map[n] = 0; map[n]++; } for (let n in map) { if (map[n] === 1) return Number(n); } }const singleNumber = fu..
1189. 컴백홈 우선 이 문제는 뜻깊은 문제이다. 백준에서 문제를 푼 개수가 600개가 되었다. 이문제는 그 600번째이다. 600개를 풀면서 드는 생각들은 회고로 적어 놓아야 겠다. 이문제는 dfs를 떠올릴 수 있는 구조이다. k의 거리로 이동한 것을 찾으니까 리턴조건은 당연히 거리가 k인것 + '그 위치에 도착했는가' 이다. 자스 풀이 const input = require("fs") .readFileSync("./dev/stdin") .toString() .trim() .split("\n") const [r, c, k] = input[0].split(" ") const dy = [-1, 0, 1, 0], dx = [0, 1, 0, -1] const visited = Array.from({ length: r }, (..
49. Group Anagrams 결국 알파벳 같은게 있으면 되니까. 가장 효율적인 비교 방법은 정렬이다. const groupAnagrams = function(strs) { let obj = {} for (let str of strs) { let letters = str.split("").sort().join("") obj[letters] ? obj[letters].push(str) : obj[letters] = [str] } return Object.values(obj) }; map set 은 이터러블이라 아래 느낌도 가능하다. const groupAnagrams = function(strs) { let m = new Map(); for (let str of strs) { let sorted = str.split("").sort()..
48. Rotate Image 문제: 한바퀴 돌리기 (90도) 일단 n n 행렬이니까 대칭 시켜주고 각 행을 reverse 시켜준다. const rotate = function(matrix) { let n = matrix.length; for (let i = 0 ; i < n; i ++) { for (let j = i ; j < n ; j++) { let temp = matrix[i][j] matrix[i][j] = matrix[j][i] matrix[j][i] = temp } } for (let i = 0 ;i < n ; i++) { matrix[i].reverse() } return matrix }; reverse 가 싫으면 하나하나 바꿀 수도 있을 것 같다. for(let i = 0; i< n; i++){ for(let j = ..
2468. 안전 영역 탐색만 하면 되니까 dfs bfs 모두 가능하다. 높이 보다 높으면 탐색 시작 점이 될 수 있고 그 시작점에서 그래프 탐색을 시작한다. JavaScript bfs const fs = require("fs") const input = fs.readFileSync("./dev/stdin").toString().trim().split("\n") const n = +input[0] const board = input.slice(1).map((e) => e.split(" ").map((e) => +e)) const max = Math.max(...board.flat()) let dx = [0, 0, 1, -1], dy = [1, -1, 0, 0] function bfs(x, y, h, visited) { cons..
1826. 연료 채우기 현재 연료로 갈 수 있는 거리에 포함되는 아이들을 heap에 넣는다. 그리고 연료가 가장 큰 아이를 택해서 p에 더해주고 cnt를 증가시킨다 -> 방문 import heapq n = int(input()) oil = [] for _ in range(n): oil.append(tuple(map(int, input().split()))) l, p = map(int, input().split()) oil.sort() hq,i,cnt = [],0,0 while p < l: while i < n and oil[i][0]
14500. 테트로미노 최근 코딩테스트에서 이 테트로미노와 비슷한 문제를 접했다. 백준에서 문제를 찾아보니 비슷한 문제들이 몇개 있어서 풀어보자! 탐색을 한다고 했을 때 처음 블록을 깊이 1 두번째 블록을 깊이 2라고해보자. 깊이 2에서는 탐색 방법 살짝 다르다. ㅗ 모양 같은 경우는 탐색하려면 아래와 같이 해야한다. 그냥 무작정 전진해버리면 ㅗ 모양은 탐색할 수 없다. N,M = map(int,input().split()) board = [list(map(int,input().split())) for _ in range(N)] ans = 0 dx,dy = [0,1,0,-1],[1,0,-1,0] visited = [[0]*M for _ in range(N)] max_value = max(map(max,board)) def df..

티스토리툴바