Algorithms

자바스크립트로 백준문제를 처음풀어봐서 입력방식에 당황했다....일단 전체코드는 이렇다.자바스크립트는 app.js 파일로 작성하여 저장한다.입력부분을 보면,node.js에서 fs 모듈을 사용하여 입력을 받는다.fs모듈의 속도가 빠르지만 fs의 경우 예제 입력 파일에 접근

백준 9093번 단어뒤집기를 풀이했는데,스택문제라서 직접 스택 클래스를 구현해보는 풀이로 접근했다.전체 코드는 다음과 같다.constructor()stack 클래스에서 구현한 메소드는 push, top, pop, isEmpty이다.이 문제에 필요한 메소드들만 구현하였다

백준 1158번 요세푸스 문제를 푸는데,linked list를 활용해서 원형을 구현할 수 있을 것 같았다.어레이와 비교해서, 링크드 리스트는 index로 노드를 찾아내는데에 느리다는 단점을 가지고 있다.하지만 이 문제에서는 index가 최대 5000정도밖에 되지 않기

잘 정리된 글을 찾았다.결론적으로, 퀵소트는 캐쉬 메모리의 지역성 덕분에, 하드웨어의 도움으로 더 빠른 정렬이 가능하다.https://medium.com/pocs/locality%EC%9D%98-%EA%B4%80%EC%A0%90%EC%97%90%EC%84%9C

dp로 풀수있고, dp의 공간복잡도 개선을 위해 투포인터로 풀수있다.2d 배열을 DP 저장소로 사용한다.다만, 대각선 오른쪽만 사용한다. 공간절반이 버려지는 셈이라 비효율적이다.모두 초기값 0으로 설정해두고 오른쪽 아래부터 왼쪽위로 순회한다.현재 인덱스 i와 j에 대해

413. Arithmetic Slices DP문제인데 DP테이블까지 만들건없고 변수 두개로 가능하다. DP 길이 3이상의 등차수열(?)의 갯수를 알아내야하는 문제이다. 예외처리로 숫자가 3개가 안되면 바로 0으로 끝내버리고 시작함 3개가 기준이니까 한개전꺼랑 두

문제푸는데 화가났으므로 칙칙한 배경ㅠ우선 s길이가 1이거나 S: s.lengthW: wordDict.lengthslice와 indexOf하는데에 s길이만큼 시간이 소요되므로 O(SW) \* O(S) 만큼 소요된다.time O(S^2 \* W), space O(S)

DP에는 해당인덱스를 포함한 LIS 길이를 저장하고,count에는 그 LIS와 같은 길이의 LIS가 몇개가 있는지 저장한다.max에는 가장 긴 LIS 길이를 저장하고, 이 LIS길이를 가지고 있는 인덱스의 count의 총합이 정답이 된다.count의 총 합을 정답으로

숫자들을 순회하면서, 해당값까지 가능한 LIS길이를 dp어레이에 저장한다.해당 인덱스 이전값을 순회하면서 가장 긴 값을 찾아 1 증가시켜준다. 나보다 작은값이 없어서 LIS갱신이 불가능한 경우에도 "나 자신"으로 이루어진 길이1짜리 LIS가 존재하므로 max초기값 0에

위와 같은 어레이를 만들어서 가장 끝에 위치한 값이 답이 될것이다.예를들어, dp2이 의미하는 것은 "ac"와 "ab"의 LCS이다.위 테이블에서 dp2=1 이 나오는 이유는 a 하나만 공통이기 때문이다.인덱스 실수를 하지않기 위함이다.https://leetc

LCS를 구할 수 있다면 바로 풀수있는 문제다!두 스트링이 같아지기 위해, 최소한만 삭제하라는 문제인데, 두 스트링의 LCS를 구하고, 각각 LCS와 얼마나 차이가 나는지만 계산하면 된다.이전 포스팅 \[JavaScript] 1143. Longest Common Sub

72. Edit Distance 풀이 두 스트링일 같게 만드는데 최소한의 연산 횟수를 구하는 문제이다. 추가, 삭제, 교체 이렇게 3가지 연산이 가능하다. 잘 생각해보면 이것도 순차적으로 char을 하나씩 추가해가며 이전 결과를 활용할 수 있다. 1. 이전 결과

다익스트라를 사용하여, 출발노드(k)에서 모든 노드로가는 최소값을 구하는 문제이다. 각 노드로 가는 최소값을 dp에 저장하고, 이 중에서 가장 큰 값이 가장 오래걸리는 시간이 될것이다.이런 자료구조가 되게 만들어준다.이 때, 출발지에 이어진 모든 노드들까지 가는 최소비

오늘 라이브코딩을 했는데, 알고리즘 구현을 요구하는 문제가 아닌 좀 창의적인 문제 해결을 원하는 문제였다. 개인적으로 참신한 발상이 맘에 들어 포스팅한다. Problem Min stack 문제는 단순히 Stack클래스를 구현하면 된다. 다만, 새로운 메서드가 추가되

모의면접에서 라이브 코테에서 뜬끔없이 하노이탑을 구현해보라는 요구를 받았다.재귀연습에 아주 기초적인 문제인데 생각해보니 한번도 구현해보지 않았던.. 이 점이 실수였다.항상 기초에 충실하자!문제는 워낙 유명하니, 여기 프로그래머스 문제에서 확인할 수 있다.전혀 감이 오지