본문 바로가기

이론/알고리즘&자료구조&Java

[알고리즘] 순열 - java(백준 10972/10973/10974/1722) 순열"1~N 까지 겹치는 숫자가 없이 나열되어있는 것"크기가 N인 수열은 총 N! 개 N의 범위에 따라 자료형(int, long)으로 적절히 선언해주어야 한다. 사전 식 나열 -> "오름 차순 정렬" 다음순열(next_premutation in C++ STL) - O(n)A[i-1] 가장 마지막부터 시작하는 가장 긴 감소수열을 찾음 O(n)결과적으로 A[0]A[1]...A[i-1]로 시작하는 가장 마지막 순열이 됨 j>=i 이면서 A[j]>A[i-1]를 만족하는 가장 큰 j 를 찾음 i번째 부터 내림 차순 정렬된 상태이기 때문에, i 번째부터 끝까지 중 에서 i-1보다 크면서 가장 작은 수가 선택A[i-1]과 A[j] swap A[0]..A[i-1] 의 다음순열로 바뀌게 됨A[i]부터 순열을 뒤집음 O(.. 이론/알고리즘&자료구조&Java 2018. 8. 21.
[백준알고리즘] 11723: 집합 -Java 솔직히 학교 수업에서 비트마스크 대충이나마 가르쳐주시긴 했지만인생에 쓸모 없을줄알고 제대로 공부한 적이 없었다ㅠ____ㅠ 후회해도 늦었징 ㅇ오늘 비트마스크에 대해 공부했다 ---------------------------------------------------------------------------1) 비트마스크'모든 경우를 살펴보아야 하는 경우' -> 솔직히 아직 이해안됨' 상태를 배열에 넣어야 하는 경우 ' -> 이것도 비트연산을 사용해서 부분집합 표현 A^B -> 다르면 1, 같으면 0 not 연산 -> 자료형에 따라 결과가 달라질 수 있음 shift 연산 : 1 10(2)ex) 3 > 를 사용할 수 있다.(N%2==1 ) ==(N&1): 맨 마지막 수가 1인지 아닌지만 판별 길이가 N인 이.. 이론/알고리즘&자료구조&Java 2018. 8. 16.
[Java] String.format 에 대해 알아보자(백준 알고리즘 2439) 알고리즘 문제를 풀다보면 자릿수를 맞춰야 하는 문제가 하나씩 보이는데, 예를들면, 0010을 출력해야 하는데 int형으로 출력하면 00이 생략된다던가 모든 스트링을 오른쪽 정렬해야한다던가. 이런 경우가 있다. Java에서 String.format함수를 통해 쉽게 이 문제를 해결할 수 있다. 자주 쓰이는 두가지 경우만 알아보겠다. 1. String의 자릿수를 맞추는 경우 String.format("%자릿수s", str) 를 이용한다. 자릿수에 맞추어서 str이 변환된다. 만약, str의 길이가 자릿수보다 길 경우 str이 그대로 출력된다. String format=String.format("%"+T+"s", str);#만약 자릿수를 맞추고 왼쪽 정렬을 하고 싶다면 String format=String.fo.. 이론/알고리즘&자료구조&Java 2018. 8. 16.
[Algorithm] Dynamic Programming vs Memoization Dynamic Programming VS Memoization공통점- 배열을 저장공간으로 사용한다. - 미리 계산한 값을 재사용 함으로써 반복 계산을 방지한다.Dynamic Programming하나의 문제를 작은 하부 문제로 나누어 해결하는 방법.작은 문제부터 해결하며 현재 계산하고 있는 문제는 "이전에 계산된 문제의 답"을 이용하여 풀 수 있어야 한다.작은 문제부터 해결해 나간다고 하여 "Bottom-UP"방식이라고 한다.재귀호출을 사용하지 않기 때문에 오버헤드가 작다.Memoization큰 문제를 해결하기 위해 작은 문제를 호출하여 해결하는 방법.단 문제를 해결하여 나온 답은 캐싱하여 재사용함으로써 반복 계산을 방지한다.최종 문제인 가장 큰 문제부터 호출한다고 하여 "Top-Down"방식이라고 한다... 이론/알고리즘&자료구조&Java 2018. 8. 1.
[자료구조/Java Collection] Set Set순서 유지x, 데이터 중복 허용xHashSet가장 빠른 random access 속도내부적으로 Hashing을 이용해서 구현한 컬렉션"데이터의 존재 유무가 중요할 때"hashing: 원래의 데이터를 상징하는 더 짧은 길이의 값으로 변환하는 것. 이 값으로 검색을 수행하면 훨씬 더 빠른 속도를 낼 수 있음LinkedHashSet추가된 순서, 최근에 접근한 순서대로 접근 가능Set 중 성능이 가장 느림TreeSet정렬된 순서 유지, 정렬 방법 지정 가능 red-black tree(이진 탐색 트리) 타입으로 값 저장, 성능이 느림데이터 추가, 삭제는 시간이 걸리지만 검색과 정렬의 성능은 뛰어남TreeSet treeset=new TreeSet(); treeset.add("apple"); treeset.ad.. 이론/알고리즘&자료구조&Java 2018. 7. 30.
Array/Linked list/ Stack/ Queue/ Tree/ Graph/ Sorting/ Dynamic Programming 깃헙 자료를 긁어와서 목차 링크가 안먹습니다. https://github.com/SeoJaeyeon/study/tree/master/study/DataStructure%26Algorithm 참고목차자료구조ArrayLinked ListStack-백준 알고리즘 9012-괄호매칭Queue-백준 알고리즘 7662-이중우선순위큐TreeGraph-DFS-BFS백준 알고리즘 2178-미로백준 알고리즘 4963SortingBubble sortInsertion sortSelection sortMerge sortQuick sort알고리즘Dynamic Programming-백준 알고리즘 9095-백준 알고리즘 1463ArrayArray 란?​"연속적인 메모리 영역을 가지는 선형 리스트"특징 집합index만 알고 있다면 ra.. 이론/알고리즘&자료구조&Java 2018. 7. 19.

티스토리툴바