일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | |
7 | 8 | 9 | 10 | 11 | 12 | 13 |
14 | 15 | 16 | 17 | 18 | 19 | 20 |
21 | 22 | 23 | 24 | 25 | 26 | 27 |
28 | 29 | 30 | 31 |
- C++
- Tanstack Query
- __proto__ 접근자 프로퍼티
- prototype 프로퍼티
- 백트래킹
- 백준 9610번 파이썬 문제 풀이
- backtracking
- 백준
- 자바스크립트
- 낙관적 업데이트
- 한글이 두 번 입력됨
- 한글 입력 시 이벤트 두 번 발생
- javascript
- 최소공배수
- 2522
- 파이썬
- 메타버스
- 9610
- float: right
- 함수 객체의 프로퍼티
- 시간
- dp
- 알고리즘
- 동기
- 동적 계획법
- 프로그래밍
- css
- 비동기
- python
- 유클리드 호제법
- Today
- Total
목록알고리즘 PS/Javascript (7)
염딩코
![](http://i1.daumcdn.net/thumb/C150x150/?fname=https://blog.kakaocdn.net/dn/cHULIi/btsvdq3fsKG/TLUK9q0HkwmKe3PKR7Qn00/img.png)
문제 풀이 처음에는 가장 많이 겹치는 순으로 제거하면서 겹치지 않는 선들만 남기려고 헀다. 하지만, 이 접근 방식은 DP와 거리가 있다고 생각을 했고 오히려 Greedy 알고리즘에 가깝다는 생각이 들었다. DP의 가장 중요한 특성 중 하나인 bottom-up을 고려하여 다시 생각을 해보는 시간을 가졌다. ⇒ 결과적으로 겹치지 않는 경우를 카운트 첫 번째 줄부터 마지막 줄까지 순차적으로 보면서 겹치는 경우를 고려하려고 했으나 쉽지 않았다. 처음에 입력을 받을 때, 랜덤한 순서로 받기 때문에 오름차순으로 정렬하여 우선 조금 더 쉽게 판단할 수 있도록 했다. (왼쪽을 기준으로 오름차순 정렬) 오름차순으로 정렬하여 가장 긴 수열(경우)를 찾는 것 = 가장 많이 겹치지 않는 경우
![](http://i1.daumcdn.net/thumb/C150x150/?fname=https://blog.kakaocdn.net/dn/cZHGPh/btsvlvn0TGx/hrj43WlMhKiZcMSSlwMhok/img.png)
풀이를 생각해낸 과정 이 문제는 예전에 알고리즘 과제와 유사하다는 느낌을 받았다. (그래서 예전 알고리즘 수업 자료도 보면서 다시 공부를 했다.) 목적지에 도달을 하면 경우의 수에 1을 더하는 방식을 생각을 했었고, 그 과정에서 지나온 경로들을 모두 처리해줘야 했었다. 지나온 경로는 상하좌우를 따지면서 내리막길인 경우에 다른 표기를 해야한다고 생각했다. 그렇게 목적지에 도달하면 해당 경우의 수를 1씩 증가시키면서 답을 구하려고 했다. 오렌지 부분에서 고민을 많이 했고, 시간이 너무 지체되어서 참고를 하면서 구현을 했다. 풀이에 대한 설명 세부적인 내용은 주석을 통해서 간단하게 설명을 했고 핵심적인 내용 위주로 설명을 하면 각각의 노드에 왔을 때, 상하좌우를 따지면서 범위를 벗어났다면 continue를 하..
![](http://i1.daumcdn.net/thumb/C150x150/?fname=https://blog.kakaocdn.net/dn/dvT1Vu/btstX1Khvye/I73h1Hxcjg1NetTNBqKavk/img.png)
풀이 function solution(numbers) { const arr = ['zero', 'one', 'two', 'three', 'four', 'five', 'six', 'seven', 'eight', 'nine']; for (let i = 0; i < arr.length; i++) { numbers = numbers.split(arr[i]).join(i); } return Number(numbers); } arr로 각 숫자를 구분하기 위해서 나열하는 것은 필수의 과정인 것 같다. 다만, 이것을 객체로 할 것인지 혹은 배열로 할 것인지에 따라 풀이 과정이 달라진다. 배열로 푼다면 replaceAll 메서드를 활용할 수도 있다. function solution(numbers) { const word..
![](http://i1.daumcdn.net/thumb/C150x150/?fname=https://blog.kakaocdn.net/dn/VuJXQ/btstY3ucDlK/6D0KY3GFWlryC97rJN88Nk/img.png)
DP 점령 2일차. 지난 포스팅에 간단하게 DP에 대한 특징을 정리했습니다. 그것을 기억하면서 이 문제를 풀어봅시다. 2023.09.13 - [알고리즘 PS/Javascript] - [JavaScript] 백준 1463번 문제 [JavaScript] 백준 1463번 문제 이 문제는 DP(Dynamic Programming)를 연습하기 좋은 문제입니다. DP(동적 계획법)에 대한 자세한 설명은 추후에 글을 올리겠습니다. DP에 대해서 간단하게 말씀드리면 DP는 하나의 큰 문제를 여러 개의 yeomyeom.tistory.com 처음에 주어진 것은 1인 경우에는 1가지이고, 2인 경우에는 3가지가 나오는 구나. DP의 가장 큰 특징 중 하나는 작은 단위로부터 문제를 해결하려는 것입니다. 그래서 작은 단위에서부..
![](http://i1.daumcdn.net/thumb/C150x150/?fname=https://blog.kakaocdn.net/dn/bI3ojF/btstRroUQAh/iy1HV0SVCt3nlmq23kVkT0/img.png)
이 문제는 DP(Dynamic Programming)를 연습하기 좋은 문제입니다. DP(동적 계획법)에 대한 자세한 설명은 추후에 글을 올리겠습니다. DP에 대해서 간단하게 말씀드리면 DP는 하나의 큰 문제를 여러 개의 작은 문제로 나누어서 그 결과를 저장하여 다시 큰 문제를 해결할 때 사용합니다. DP는 재귀와 매우 유사합니다. 하지만, 가장 큰 차이점은 일반적인 재귀를 단순히 사용 시 동일한 작은 문제들이 여러 번 반복 되어 비효율적인 계산될 수 있다는 점입니다. DP를 사용하기 위한 조건으로는 크게 두 가지가 있습니다. 1. Overlapping Subproblems(겹치는 부분 문제) 동일한 작은 문제들이 반복하여 나타나는 경우 2. Optimal Substructure(최적 부분 구조) 부분 문..
![](http://i1.daumcdn.net/thumb/C150x150/?fname=https://blog.kakaocdn.net/dn/bzZzhR/btspk8t0hzV/fZH3zorqPmI1XWi0Nd6p01/img.png)
이 문제는 크게 어렵지 않았는 데, 자꾸 틀렸다. 테스트케이스는 바로 맞았지만 문제는 한 구명보트에 최대로 2명만 탈 수 있다는 조건을 뒤늦게 확인했다는 점이다. 제한사항에 없는 조건도 문제에서 있기 때문에 꼼꼼하게 따져야 할 것 같다. 코드를 작성할 때, 주석으로 달아놓는 것도 좋은 습관인 것 같다. 나의 풀이 function solution(people, limit) { let cnt = 0; people.sort((a,b) => (a-b)); while(people.length > 0) { const lastPerson = people.pop(); let lastWeight = limit - lastPerson; if (people[0] b-a) for(let i =0, j = people.leng..
![](http://i1.daumcdn.net/thumb/C150x150/?fname=https://blog.kakaocdn.net/dn/onA85/btso11ui25O/WjR4wfNkEmsyEYRmcbtUQ0/img.png)
문제 설명 Leo는 카펫을 사러 갔다가 아래 그림과 같이 중앙에는 노란색으로 칠해져 있고 테두리 1줄은 갈색으로 칠해져 있는 격자 모양 카펫을 봤습니다. Leo는 집으로 돌아와서 아까 본 카펫의 노란색과 갈색으로 색칠된 격자의 개수는 기억했지만, 전체 카펫의 크기는 기억하지 못했습니다. Leo가 본 카펫에서 갈색 격자의 수 brown, 노란색 격자의 수 yellow가 매개변수로 주어질 때 카펫의 가로, 세로 크기를 순서대로 배열에 담아 return 하도록 solution 함수를 작성해주세요. 제한사항 갈색 격자의 수 brown은 8 이상 5,000 이하인 자연수입니다. 노란색 격자의 수 yellow는 1 이상 2,000,000 이하인 자연수입니다. 카펫의 가로 길이는 세로 길이와 같거나, 세로 길이보다 ..