경험주의자의 블로그

문제 보기 문제 분석 [요약] 문자열 하나가 주어진다. 주어진 문자열 사이 사이에 존재하는 숫자를 찾아 모두 더하여 출력한다. [푸는 과정] 오랜만에 한 시간 넘게 잡고 있던 알고리즘 문제다. 왜냐하면... 지금부터 썰을 풀어볼 것이다. //문제를 대충 읽었어요.. 처음에는 그냥 모든 숫자를 일의자리 숫자 취급하여 더해버렸다(문제를 제대로 읽자..ㅎ). 당연히 오답. 자세히 살펴보니 붙어있는 숫자는 하나의 숫자 취급을 해 주어야 한다. 예를 들어 'a555d222f6d5s1'이라는 문자열에 숨어있는 숫자는 '555', '222', 6', '5', '1' 이 되고 555+222+6+5+1 = 789가 정답이 된다. //로직이 틀렸어요.. 이제 문제를 제대로 파악했으니 코드를 짜 본다. 또 오답이다. 이건 ..

문제 보기 문제 분석 [요약] 주어진 케이스 별로 1)첫 번째 줄 : 녹음기에 담긴 모든 울음소리, 2)두 번째 줄~'What does the fox say'이전 까지의 줄 : 각 동물의 울음소리 이다. 1번 문장을 2번에서 언급한 동물의 울음소리를 제외하여 출력한다. [푸는 과정] 각 동물의 울음소리를 " goes "로 잘라내서 HashTable에 담고 차례대로 'replace()'를 써서 해당 울음소리를 모두 ''로 바꾼 뒤 출력하는 방법이 바로 떠올랐다. 그런데 여기서 문제 발생. 예제의 'seal'은 'ow'소리를 내며 울고 모든 동물 울음소리를 담은 문장에 'pow'가 포함되어 있다. 그래서 만약 'replace("ow", "");'를 쓴다면 'pow'라는 단어가 'p'로 변해버린다. 그래서 다..

문제 보기 문제 분석 [요약] 다양한 높이의 통나무를 원형으로 세웠을 때 높이 차이가 가장 적도록 배치하기. [푸는 과정] 우선 숫자의 최소 혹은 최대를 구하는 문제기 때문에 '정렬'이 필요 하겠다. 정렬이 쉽도록 배열을 선택할 것이다. 각 숫자의 차이가 가장 적도록 배치하려면 우선 가장 큰수를 중간에 배치 하고 남은 숫자들을 양 옆으로 내림차순 배치를 하면 되겠다. input용 배열 하나(=numbers), 통나무 정렬용 배열(=logs) 하나로 총 두 개의 배열을 사용 할 것이다. 이제 나란히 놓인 두 숫자의 차 중 가장 큰 차를 구해야 한다. 혹시 모를 시간초과 방지를 위해 통나무를 정렬하면서 Math.max()함수를 이용해 두 수의 최대 차를 구할 것이다. 코드 보기 import java.io.*..

문제 보기 문제 분석 [요약] 주차장을 이용한 차량별 요금을 계산 하여 차량 번호 오름차순으로 출력하기. 테스트 케이스별로 기본 시간/요금, 단위 시간/요금이 다름. [푸는 과정] 차량번호를 기준으로 이용시간 체크를 해야겠다. 총 이용시간을 계산 하려면 여러번의 차량번호 검색이 필요하기 때문에 시간초과 방지를 위해 Map을 써야겠다. 주차장 이용 중인 차량 용 Map(=carParkRecords), 각 차량 별 총 이용 시간용 Map(=useTimeRecords) 이렇게 두 가지 맵을 사용할 것이다. 해당 문제에서 각 차량 별 출입 시간을 오름차순으로 제공한다. 그렇기에 carParkRecords에 해당 차량이 있으면, 해당 입력이 해당 차량의 출차 시간을 나타내므로 시간 차이를 계산하여 useTimeR..

(나만의)구분 특징 문제가 반복적인 작은문제로 이루어짐 점화식 도출 필요 피보나치 함수 알고리즘 작성순서 점화식 도출(반복적 부분을 식으로 표현) Top-down VS Bottom-up 선택 비 반복 부분 존재 시 따로 추가 구현(즉, 비 반복적 부분 + 점화식의 형태) 참고 Bottom-Up / Top-Down 비교 Bottom-Up : 필요한 재료 전부를 미리 준비 후 바구니에 넣고 꺼내어 쓰는 방식 ☞ (바구니=)배열/리스트 등 Top-Down : 필요한 재료를 그때그때 준비해나가는 방식 ☞ 재귀함수 사용 피보나치 수열을 통해 이해하기 '동적 프로그래밍'이라는 이름이 그리 직관적은 아니라 생각한다. 따라서 해당 알고리즘을 이제 막 접하기 시작했다면 단번에 이해하기 힘들수 있다(사실은 내가 그러했다)..

public class BinarySearch { static int[] arr = {1, 3, 5, 7, 8, 10, 35, 99, 100}; public static void main(String[] args) { System.out.print("이진탐색 결과: "); binarySearch_recursion(5, 0, arr.length-1); //binarySearch_ } private static int binarySearch_recursion(int answer, int smallNum, int bigNum) { int middleNum; if(smallNum

(나만의)구분 특징 루트로부터 가까운 것 부터 검색 찾고자 하는 노드까지의 경로가 여러개일지라도 최단경로임을 보장 가능 알고리즘 작성순서 인접행렬 VS 인접리스트 선택(그래프 정보 저장용) 주어진 그래프 정보 입력 Queue를 사용한 BFS 알고리즘 구현 코드예시 인접리스트 사용시(Queue) import java.util.Collections; import java.util.Iterator; import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; public class BFS_LinkedList { public static void main(String[] args) { Scanner sc = new Scanner(S..

(나만의)구분 특징 찾고자 하는 노드를 찾게되면 탐색이 종료 됨 → 해당 경로가 최단경로라는 보장 불가 알고리즘 작성순서 인접행렬 VS 인접리스트 선택(그래프 정보 저장용) 주어진 그래프 정보 입력 재귀함수 VS 스택 선택(DFS 알고리즘의 구현) 코드예시 인접리스트 사용시(재귀함수) import java.util.Collections; import java.util.Iterator; import java.util.LinkedList; import java.util.Scanner; public class DFS_LinkedList { public static void main(String[] args) { Scanner sc = new Scanner(System.in); //-----그래프의 노드,간선 ..

알고리즘의 성능은 대체 어떻게 측정할 수 있을까? '시간복잡도'라는 것이 있다. 우선 의미를 알아보자. 시간복잡도란 특정 알고리즘이 작업을 완료하는데 걸리는 시간을 정량화하는 것이다. -위키백과 참조- 시간을 정량화 한다? 이해가 갈듯말듯 하다. 쉽게 말하자면 시간복잡도는 어떠한 알고리즘이 완료되기까지 필요한 스텝을 의미한다. 즉, 분/초를 세는 것이 아닌 몇번의 단계가 필요한지를 측정하는 것이다. 그리고 그 단계들을 분류하기 쉽게 지표화 한 것이 'BigO Notation'이다. 1) O(1) -Input사이즈에 관계없이 알고리즘이 완료되기까지 걸리는 스텝이 하나(=항상 일정) -최적의 알고리즘(=가장 선호되는 알고리즘) -구현하기 쉽지 않음 public void sayHello(){ System.ou..