본문 바로가기

Programming/알고리즘

(11)
[코테준비] 입문자를 위한 알고리즘 해결전략 - 2 프로그래머스 > 해시 > 전화번호 목록 큰 그림 시간 복잡도 O(n^2) 테스트 1,5,6,7,11 실패 & 효율성 성공 => ["123", "01230"]에서 java.lang.StringIndexOutOfBoundsException: begin 0, end 5, length 3 에러가 뜬다. 왠지 소트를 할 때 기준을 문자열 자릿수가 아닌, 숫자 값으로 정수 비교를 한 것 같다...? 소팅 결과가 분명 01230, 123 이렇게 되었기 때문에 저 에러가 뜬 것이 분명하다. 벽을 넘자 그래서 sort를 문자열 길이 기준으로 할 수 있을까 생각을 해서 구글링을 해보았는데 compare로 사용자 정의 메서드를 이용해서 만들어야 해서 복잡해질뿐더러, 내가 원하는 기능을 추가하는 것이 제한시간 안에 구현하는 ..
[코테준비] 입문자를 위한 알고리즘 해결전략 - 1 프로그래머스 > 해시 > 완주하지 못한 선수 큰 그림 앞으로 문제풀이를 할 때 다음의 절차를 따르려고 한다 (TDD 방식과 비슷) 1. 문제를 풀기전에 종이에 문제해결을 위한 스케치를 한다. 1-1. 큰그림을 그린다 1-2. 벽을 세운다. 1-3. 의문을 세운다. 2. 코딩을 시작한다. 2-1. 큰그림을 구현한다. 테스트 케이스를 돌려서 큰그림 테스트를 통과, 벽에 대한 테스트 케이스가 실패함을 확인한다. 처음에는 무조건 테스트에 실패한다. 2-2. 벽을 넘는다. 2-3. 의문을 해결한다. 3. 제출한다. 큰그림 : 문제를 푸는 큰 틀이자 뼈대. 고양이를 그릴 때 전체적인 고양이 골격을 그리는 것을 의미. 스케치를 해 나갈 때, 고양이의 머리 -> 몸통 -> 다리 순으로 그려나가는 것이 아닌, 고양이 뼈..
[자료구조]스택,큐로 이해하는 DFS,BFS DFS & BFS 란? 깊이우선 탐색, 너비 우선 탐색의 약자이다. 이진트리를 완전탐색하는 두가지 방법론이다. 스택으로 이해하는 DFS 이제까지는 재귀호출로 DFS 를 이해해왔고, BFS 가 큐로 이루어진것을 이해했다. DFS 를 스택으로 구현해보기도 했지만, 정확히 그 동작원리를 알지 못했었다. 때마침 오늘 학교강의를 들으며 이 부분에 대해 교수님이 설명해 주셔서 글로 남긴다. 스택은 LIFO(Last in First out), 큐는 FIFO(First in First out) 으로 동작한다. DFS by stack 왼쪽이 스택의 bottom, 오른쪽이 스택의 top 이다. BFS by queue 왼쪽이 큐의 front이다. 코드로의 구현 기존에 DFS 를 재귀적으로 이해했었고 그렇게 코딩해왔었다. 이..