[알고리즘] 3 x N 타일링
2022. 10. 31. 16:18
알고리즘
개요 바로 전에 풀었던 2 x N 타일링과 유사합니다. [알고리즘] 2 x n 타일링 js 개요 2 * n 직사각형이 주어질 때 1 * 2 타일을 꽉 차게 배치할 수 있는 모든 경우의 수를 찾는 문제이다. 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 choiblog.tistory.com 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 홀수의 경우는 타일을 가득 채울 수 없다는 것은 금방 알아챘는데 점화식을 구현해내는 과정이 상당히 어려웠다. 케이스에서는 4까지밖에 주어지지않았고 그 이상을 찾아보려고할 때 풀이..
[알고리즘] 2 x n 타일링 js
2022. 10. 30. 19:25
알고리즘
개요 2 * n 직사각형이 주어질 때 1 * 2 타일을 꽉 차게 배치할 수 있는 모든 경우의 수를 찾는 문제이다. 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 처음 문제를 봤을 땐 모든 걸 탐색하라고 해서 DFS로 접근하려다가 수가 너무 크기도 해서 다른 방법을 조금 고민했다. 사실 이때 DFS가 안된다면 DP로 한번 생각해볼 수 있었는데 쉽게 생각을 못했다. DP로 풀 경우는 아래와 같다 만약 n의 길이가 1일때를 생각해보자 2 * 1의 직사각형에는 타일을 세로로 하나밖에 넣지 못한다. 만약 n의 길이가 2라면 2 * 2 직사각형에는 타일을 세로..
[알고리즘] 124나라의 숫자 js
2022. 10. 30. 17:29
알고리즘
개요 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 대충 3진법처럼 변환된다고 한다 풀이 숫자를 나눠보면 3으로 나누어 떨어질 때 4가 출력되는 것을 확인할 수 있고 나머지가 1이면 1, 나머지가 2면 그대로 2가 된다 따라서 나머지를 바로 대응할 수 있도록 [4,1,2]순서로 만들었고 인덱스 번호로 매핑시킨 뒤 주어진 숫자를 나누기 했다 그런데 아무리 돌려도 정답처리가 안되어 구글링을 해서 확인해보았다 -1로 왜 빼는지 이해를 잘 못했었는데 이 글을 보고 https://yabmoons.tistory.com/692 0의 유무 때문이고 그 이유로 몫을 하나..
[알고리즘] 키패드 누르기 js
2022. 10. 29. 23:03
알고리즘
개요 순서대로 누를 번호가 담긴 배열 numbers, 왼손잡이인지 오른손잡이인 지를 나타내는 문자열 hand가 매개변수로 주어질 때, 각 번호를 누른 엄지손가락이 왼손인 지 오른손인 지를 나타내는 연속된 문자열 형태로 return 하도록 solution 함수를 완성해주세요. 키패드를 누르는데 어느 손으로(왼손, 오른손) 눌렀는지를 순서대로 만들어 return하면 된다 이때 중간 2580에 있는 숫자들은 가까운 키패드를 눌렀던 손이 누르고 만약 길이가 같다면 왼손잡이인지 오른손 잡이인지에 따라 누르면 된다 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이..
[알고리즘] 햄버거 만들기 js
2022. 10. 29. 22:52
알고리즘
개요 상수에게 전해지는 재료의 정보를 나타내는 정수 배열 ingredient가 주어졌을 때, 상수가 포장하는 햄버거의 개수를 return 하도록 solution 함수를 완성하시오. 1,2,3,1으로만 햄버거를 만들 수 있다 그리고 딱히 명시하진 않았지만 햄버거가 계속 쌓이고있다고 가정했으니 스택 자료구조를 떠올릴 수 있다. 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 이제 스택을 만들어 넣고 빼면 되는데 1(빵)이 나오는 경우만 체크해보고 나머지 경우는 전부 스택에 넣은 뒤 만약 빵이 나왔다면 가장 위 3개를 pop으로 빼서 tmp 배열에 넣어 비..
[알고리즘] 게임 맵 최단거리
2022. 10. 29. 22:44
알고리즘
개요 게임 맵의 상태 maps가 매개변수로 주어질 때, 캐릭터가 상대 팀 진영에 도착하기 위해서 지나가야 하는 칸의 개수의 최솟값을 return 하도록 solution 함수를 완성해주세요. 단, 상대 팀 진영에 도착할 수 없을 때는 -1을 return 해주세요. 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 시작지점과 끝점이 정해져있는 미로찾기로 가장 빠른 길을 return하면 된다 풀이 최단거리를 찾는 문제는 보통 BFS를 사용하여 해결한다. DFS로 어려워보이진 않아서 처음엔 DFS로 구현해봤는데 실행시간 초과, 효율성 테스트에서 하나도 통과하지 못했..
동적 계획법과 냅색 알고리즘
2022. 10. 28. 21:58
알고리즘
동적 계획법이란 하나의 큰 문제를 아주 작은 단위의 문제로 해결하는 것으로 직관적으로 쪼개야 한다. 답을 기록해놓고 구해놨던 답을 사용하면서 문제를 조금씩 넓힌다 특징으로는 점화식의 관계가 있기때문에 점화식을 파악하는게 중요하다고 한다 다이나믹 테이블 dy를 선언한 뒤 dy를 통해 구하는데 직관적으로 볼 수 있는 부분은 dy에 넣어서 구현을 했다 DP는 두가지 조건을 만족해야 사용할 수 있다고 한다 1. 겹치는 부분 문제 2. 최적 부분 구조 겹치는 부분 문제 동일한 작은 문제들이 반복적으로 나타나야한다. 예시로써 DFS로 구현한 코드를 보면 이미 구해놓았던 작은 계산들이 계속 반복된다. 최적 부분 구조 부분 문제의 최적 결과 값을 사용해 전체 문제의 최적 결과를 낼 수 있는 경우를 말한다 예시로 피보나..
BFS(너비 우선 탐색)
2022. 10. 24. 20:05
알고리즘
BFS DFS와는 다르게 그래프의 인접노드부터 탐색하는 방식입니다. BFS는 상태트리로 이해하면 쉬운데 상태 트리란 문제의 모든 가능한 상태를 노드로 구성하여 초기 상태를 루트로 에서 최종 상태로 리프로 상태 전환을 통해 연결된 트리라고 하는데 당장 BFS를 이해하기 위해 중요한건 아니라 따로 읽어보았습니다. [Algorithms] State Space Tree Search | 상태 공간 트리 탐색 State Space Tree Search 상태 공간 트리 탐색 - 문제 해결 과정의 중간 상태들을 모두 Node로 구현해놓은 트리이다. - 상태 공간 트리의 Leaf Node는 해당 문제의 해(Solution)에 해당된다. - Optimum(최적해)는.. dad-rock.tistory.com BFS의 구현 ..
자주 나오는 정렬 알고리즘
2022. 10. 24. 17:51
알고리즘
선택 정렬 선택 정렬이란 오름차순, 내림차순에 따라 하위 인덱스부터 하나씩 위치를 정렬시켜 나가는 방법으로 이중 for 문을 통해 구현됩니다. function solution(arr) { /* 선택 정렬이란 최솟값부터 하나씩 위치 변경을 시켜주는 것이다 이중for문을 돌면서 i번 위치에 올 최솟값, i + 1 위치에 올 최솟값... 이렇게 정렬시켜나간다 */ let answer = arr; for (let i = 0; i arr[j]) idx = j; // 자리바꾸기 } // 이렇게 하면 아래와 똑같이 자리가 바뀐다 아래 tmp 변수를 활용하는 것과..
Leetcode - 807. Max Increase to Keep City Skyline
2022. 6. 17. 20:31
알고리즘
문제 설명 Input: grid = [[3,0,8,4],[2,4,5,7],[9,2,6,3],[0,3,1,0]] Output: 35 Explanation: The building heights are shown in the center of the above image. The skylines when viewed from each cardinal direction are drawn in red. The grid after increasing the height of buildings without affecting skylines is: gridNew = [ [8, 4, 8, 7], [7, 4, 7, 7], [9, 4, 8, 7], [3, 3, 3, 3] ] 건물의 최대 높이는 이미 정해져있고 사방에서 ..