더 부지런해지기 위한 블로그

개발 공부하며 기록하는 블로그 입니다.

자바알고리즘

출처 : 프로그래머스 코딩테스트 연습, https://school.programmers.co.kr/learn/courses/30/lessons/12951# - JadenCase란 모든 단어의 첫 문자가 대문자이고, 그 외의 알파벳은 소문자인 문자열 - 단, 첫 문자가 알파벳이 아닐 때에는 이어지는 알파벳은 소문자로 (첫 번째 입출력 예 참고) - 문자열 s를 JadenCase로 바꾼 문자열을 리턴하기 처음에 공백을 기준으로 split 해서 배열에 담고 첫글자만 대문자, 나머지만 소문자로 바꾸면 끝날 것 같았는데 공백이 연속해서 나올 수 있다는 부분을 고려해주지 않아서 " " -> " " 이렇게 나와야 하는데 " " -> "" 이렇게 나왔다. 나의 풀이 문자 단위가 아니라 한글자씩 쪼개서 - 완전 첫 글자..

2023. 4. 23.

자바알고리즘

출처 : 프로그래머스 코딩테스트 연습, https://school.programmers.co.kr/learn/courses/30/lessons/161990 머쓱이의 바탕화면을 정리해주자~ - 최소한의 이동거리를 갖는 한 번의 드래그로 모든 파일을 선택해서 한 번에 지우려고 함 - 시작점 S(x, y) 끝점 E(x, y) => 이으면 네모네모 - 빈칸은 ".", 파일이 있는 칸은 "#" - 결과는 시작점과 끝점 [x, y, x, y] 나의 풀이 - #을 만나면 체크한다. (시작점에는 가장 작은 좌표, 끝점에는 가장 큰 좌표가 오겠구나 했음) - 여기서 중요한 점은 시작할때 시작점 x, y에 wallpaper에서 제일 큰 값을 셋팅해주는 것임 (그렇지 않으면 계속 0이 나올 것임) (정사각형이 아니므로 시작..

2023. 4. 7.

자바알고리즘

출처: 프로그래머스 코딩 테스트 연습, https://school.programmers.co.kr/learn/courses/30/lessons/172928 직사각형 격자 모양의 공원에서 로봇 강아지 산책시키기 - park는 공원이고, routes의 방향과 거리(몇칸 이동) - result는 최종 이동 후 위치를 반환 - 공원을 벗어나거나, 장애물을 만나면 해당 명령을 무시하고 다음 명령을 수행 나의 풀이 이차원배열과 좌표를 사용하여 풀어보았습니다. 1. 이차원배열에 값 셋팅 & 시작지점 찾기 2. 방향키 자료 셋팅 (이차원배열, Map 사용) 3. 찾은 시작지점을 가지고 시작, - routes에서 방향표 읽어서 n번 반복(예를 들어 "E"를 읽어 2번 반복) -> 도중에 범위를 벗어나거나, 장애물 만나면..

2023. 4. 3.

자바알고리즘

- Java에서 스택과 큐를 표현하는 좋은 방법은 Deque 인터페이스 사용하는 것 - 스택은 후입선출법, 큐는 선입선출법 따름 더보기 Deque(덱)이란? 양방향 큐(double-ended queue)라고도 부르며 모든 삽입 삭제가 리스트의 양 끝, 둘중 하나에서 일어나는 이중 연결리스트 이는 스택으로 사용할수도 있고 큐로 사용할 수도 있다. 스택 라이브러리 이해하기 메서드 설명 특징 push() 원소 집어넣기 - 용량에 한계는 없지만 구현에 따라 예외 던질 수 있다. - null 삽입 가능하지만 매우 조심해야 한다. peek() 원소 삭제하지 않고 스택의 위에 있는 원소 반환하기 - 빈 스택은 null 반환 - null이 유효한 원소일 수도 있으므로 isEmpty() 사용 pop() 스택에서 원소 삭..

2022. 12. 24.

자바알고리즘

- 리스트는 순서가 있는 값들의 모음(collection) - 노드는 하나의 객체와 다음 노드에 대한 참조로 이루어짐 - 이중 연결리스트는 이전 노드에 대한 참조도 가지고 있다. - 삽입 및 삭제는 지역적 발생하므로 시간복잡도 O(1) - 검색은 모든리스트 순회해야 하므로 O(n) class List { public T data; // 나 public ListNode next; // 다음 } 7.1 두 개의 정렬된 리스트 합치기 단순 연결리스트 L과 F에 숫자가 오름차순 저장되어 있다. L과 F를 합쳐 하나의 단순 연결리스트 반환하기 (단, 오름차순 유지) 힌트 : 정렬된 배열은 인덱스 두개로 합칠 수 있다. 리스트는 반복자가 끝에 도달했을 때 처리에 주의할 것 - 두 개의 리스트를 앞에서부터 확인하면서..

2022. 12. 13.

자바알고리즘

5.12 오프라인 데이터 샘플 구하기 서로 다른 원소로 이루어진 배열과 부분 집합의 크기 주어졌을 때, 주어진 크기의 부분집합 결과를 반환하라 (모든 부분 집합이 생성될 확률은 같아야 한다.) 힌트 : 크기가 k인 임의의 부분 집합이 존재할 때 크기가 k+1인 임의의 부분 집합을 어떻게 구할 수 있을까? - 배열 A의 길이는 n, 부분 집합의 크기는 k라고 하면 가장 단순한 방법은 입력 배열 순회하며 각 원소를 k/n의 확률로 선택하기 - 크기가 k인 모든 부분 집합 나열 후 임의로 하나의 부분집합 선택하기(시간 및 공간복잡도 매우 큼) - 크기가 k-1인 부분 집합 만든 후 임의의 나머지 원소 추가하기 5.13 온라인 데이터 샘플 구하기 패킷 스니퍼 : 네트워크 세션에 균일한 샘플의 패킷을 제공 어떤 ..

2022. 12. 10.

자바알고리즘

문자열 라이브러리 이해하기 - Java 문자열 String은 암묵적으로 불변이므로, StringBuilder를 활용하여 가변적으로 다루도록한다. - 가변 문자열을 앞에서 부터 갱신해 나가는 방법은 느리므로 가능한 뒤에서부터 쓰는 것이 좋다. + String 핵심 메서드 더보기 charAt() compareTo() contains() endWith() indexOf() indexOff() lastIndexOf length() replace() split() startsWith() substring() 시작인덱스는 포함하지만 마지막인덱스 포함하지 않음 주의 toCharArray() toLowerCase() trim() + StringBuilder 핵심메서드 더보기 append() charAt() delete..

2022. 12. 10.

자바알고리즘

배열 특징 : 연속한 메모리 공간에 할당 5.1 네덜란드 국기 문제 (그룹들의 묶음) 배열 A와 인덱스 i 가 주어졌을 때 A[i](피벗)보다 작은 원소, 피벗과 같은 원소, 피벗보다 큰 원소 순으로 재배열하라 - 공간을 사용하는 방법 : 세가지 리스트 만든 후 차례로 A에 넣어주면 됨 (공간복잡도 O(n) / 시간 복잡도 O(n)) - 시간을 사용하는 방법 : 1) 배열 순회하며 피벗보다 작은 원소 그룹 스왑 후 피벗보다 큰 원소 그룹 스왑 5.2 임의의 정수값 증가시키기 십진수 D를 나타낸 배열 A가 있고, D+1의 결과를 다시 배열 A에 갱신하라 예) {1,2,9} => {1,3,0} //힌트 : 실제 예제 입력 사용해보자 유한 정밀도 산술로 이루어진 프로그램 언어로도 동작해야 한다(?) - 무식하..

2022. 11. 26.

자바알고리즘

참고로, 이 책은 자바 알고리즘 도서가 파이썬에 비해 많지가 않아서 추천 도서 중에 고른 책인데 내용은 매우 유용하지만 다소 난이도가 있어 입문용으로는 추전하지 않는다. (책의 서문에서도 학부수준의 자료구조나 알고리즘이 익숙한 사람을 대상독자로 한다.) 나도 한번 읽으면 절반은 이해 못하지만, 여러번 읽다 보면 이해되지 않을까 싶어서 간단요약을 하려고 한다. 기본 자료형, 비트를 잘 사용하면 프로그램의 성능 향상 시킬 수 있다. 4.1 패리티 계산하기 패리티 : 보통 정보 전달 과정에서 오류 생겼는지 검사하기 위한 값(전체 비트의 개수를 2로 나눈 나머지 값과 같다.) 1이 홀수개면 1, 짝수개면 0이 된다. 64비트로 이루어진 숫자 굉장히 많을때 -> 룩업테이블 활용 - 무식하게 모든 비트 갯수 세기 ..

2022. 11. 18.

자바알고리즘

넓이 우선 탐색은 한줄씩 읽으며 내려간다. 레벨 순 탐색한다고 하는데 루트노드를 0레벨, 다음줄 1레벨(루트기준 노드 한번), 그 다음줄 2레벨(루트기준 노드 두번) ,,, 큐로 구현 1 들어갔다가 1 나오고 연결된 2 , 3 들어가고 2 나오고 연결된 4, 5가 뒤로 들어가고 3 나오고 연결된 6,7이 뒤로 들어가고 ,,, import java.util.LinkedList; import java.util.Queue; class Node7{ //이진트리(넓이우선) int data; Node7 lt,rt; public Node7(int val) { data=val; lt=rt=null; } } public class Tree7 { Node7 root; public void BFS(Node7 root) { ..

2021. 9. 5.