Algorithm 썸네일형 리스트형 [ 백트래킹 ] N과 M Backtracking 이란?백트래킹은 모든 가능한 경우를 탐색하되 조건을 만족하지 않는 경로를 미리 차단(가지치기)하는 알고리즘이다. 쉽게 말해가능한 선택지를 따라가며 시도한다.조건에 어긋나면 되돌아온다. -> 백트래킹조건을 만족하면 결과를 기록한다.DFS(깊이 우선 탐색)을 기반으로 구현한다. 우선 문제를 분석해보자.[백준 15649]https://www.acmicpc.net/problem/15649"1부터 N까지 자연수 중에서 중복 없이 M개를 고른 모든 수열을 출력하라"N개의 수 중에서 M개를 뽑되 순서가 중요하고, 중복은 허용되지 않는다. 해당 문제는 겉으로 보기엔 단순한 모든 경우 탐색 문제처럼 보이지만 실제로는 Combinatorial Explosion 다루는 예제처럼 보인다. 모든 경우를 .. 더보기 [ 백준 / Java ] 2805 나무자르기 첫번 째 접근 방법(브루트 포스) public class B_2805 { public static void main(String[] args) { long startTime = System.currentTimeMillis(); Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int m = sc.nextInt(); List list = new ArrayList() { { for (int i = 0; i < n; i++) { add(sc.nextInt()); } } }; int max = list.stream().mapToInt(Integer::intValue).max().orElse(0); while(true) { int tree = 0; max--.. 더보기 [Java / Javascript] HashSet, HashMap HashSet 🤔 set 인터페이스를 구현하는 Java 컬렉션 프레임워크의 일부로 중복된 요소 없이 값을 저장하는 데이터 구조다. 그리고 비선형 구조이기 때문에 순서의 개념과 인덱스가 존재하지 않는다. 때문에 값을 추가/삭제 하는 경우 Set 내부에 해당 값을 검색하여 해당 기능을 수행해야 한다. 이로 인해 처리속도가 List에 비해 느리다는 것이 단점이다. HashSet은 내부적으로 HashMap을 사용하여 요소를 저장한다. 특징 요소의 순서를 보장하지 않는다. 하나의 null 값을 포함할 수 있다. 주로 데이터의 중복을 허용하지 않는 상황에서 사용한다. import java.util.HashSet; public class HashSetExample { public static void main(Str.. 더보기 [ 프로그래머스 / DFS, BFS ] 단어 변환(level 3) Level 3 단어 변환 🤔 begin 에서 target 으로 단어 변환하기 HashMap을 이용하여 그래프를 구성하자. begin 단어와 words 배열에 있는 각 단어를 그래프의 노드로 추가하고 서로 연결될 수 있는 단어들(한 글자만 다른 단어들)을 각 노드의 인접 리스트로 추가하자. 🤔 BFS 알고리즘 사용 BFS를 사용하여 begin 단어로부터 시작이 target 단어에 도달하는 데 필요한 최소 수를 구하자. Queue를 사용하여 탐색할 단어들을 관리하여 각 단계에 방문한 단어와 그 단어까지 도달하는 데 필요한 단계를 저장하자. 🤔 단어 비교 함수(compareWord) 두 단어가 한 글자만 다른지 여부를 판단하는 함수를 만들자. 두 단어의 길이가 같고 서로 다른 문자의 수가 정확히 하나인 경우에.. 더보기 [ 프로그래머스 / Java ] 1차 캐시 👨💻 우선 이 문제를 풀기전에 페이지 교체 알고리즘에 대해 알아보자! ➡️ 운영체제는 주기억장치보다 더 큰 용량의 프로그램을 실행하기 위해 프로그램의 일부만 주기억장치에 적재하여 사용한다. 이를 가상 메모리 기법이라고 한다. 페이징 기법으로 메모리를 관리하는 운영체제에서 필요한 페이지가 주기억장치에 적재되지 않았을 때(페이지부재) 어떤 페이지 프레임을 선택하여 교체할 것인지 결정하는 방법을 페이지 교체 알고리즘이라 한다. ☑️ 프레임 : 물리 메모리를 일정한 크기로 나눈 블록 ☑️ 페이지 : 가상 메모리를 일정한 크기로 나눈 블록 💡 페이지 교체 알고리즘의 종류 OPT(Optimal Page Replacement) : 앞으로 가장 오랫동안 사용되지 않을 페이지 교체 FIFO(First In First .. 더보기 [ Java / 프로그래머스 ]귤 고르기 👨💻 아무생각없이 문제를 읽고 리스트에 담아서.. 크기별로 개수를 맵에 담은 다음에.. 그 개수를 다시 리스트에 담아서.. 정렬하고.. 역으로 돌린 다음에 순차적으로 더했을 때 k보다 같거나 크면 끝내 보자!!라는 생각을 하고 바로 코드를 짜보았다. 너무 길어지고 효율성도 너무 똥일 것같았지만 일단 해보았다. 레벨 2부터는 효율성도 따지길래 틀렸을 거라고 생각했는데 성공은 했다 ㅋㅋ 😅 살벌하다.. 메모리와 시간이 너무 비효율적이다. 나는 항상 독특하게 생각해서 코테 푸는게 재밌다. 하지만 개발자로써는 효율성을 중요하게 따져야하기 때문에 앞으로는 효율성을 따지면서 풀어봐야겠다. int k = 6; int[] orange = {1, 3, 2, 5, 4, 5, 2, 3}; List list = new Ar.. 더보기 [프로그래머스/Java] 짝지어 제거하기 ➡️ Level 1 까지는 그냥 생각대로 풀어도 모든 테스트 케이스에 통과된 것같은데 Level 2부터는 효율성과 시간복잡도까지 고려해야 하는 것같다. //머리 굴려서 열심히 풀었는데 시간 초과 남 ㅡㅡ public class Main { public static void main(String[] args) { String s = "baabaa"; List list = new ArrayList(Arrays.asList(s.split(""))); int result = 0; int firstLength = list.size(); while(true) { int lastLength = 0; for(int i=0; i 1 “cdcd” [c] [c, d] [c, d, c] [c, d, c, d] --> 0 👨.. 더보기 스택(Stack) 데이터를 일시적으로 쌓아 놓는 자료구조로, 데이터의 입력과 출력 순서는 후입선출(LIFO: Last In First Out)이다. 나중에 넣은 데이터를 가장 먼저 꺼낸다. push : 데이터를 넣음, pop : 데이터를 꺼냄 void x() {} void y() {} void z() { x(); y(); } void main() { z(); } //만약 위의 코드가 있다면 스택을 사용하여 //아래 처럼 흐른다. 자바 프로그램에서 메서드를 호출하고 실행할 때 프로그램 내부에서 스택을 사용한다. main push z push x push x pop y push y pop z pop x y z z z z z main main main main main main main 스텍 만들기 public class In.. 더보기 이전 1 2 3 다음
