백준 14503번 : 로봇청소기 처음에 문제만 읽고, 그동안 많이 풀었던 좌표를 이용한 BFS문제로 방향을 잡았는데 풀리지 않았다.이 문제의 유형은 시뮬레이션 문제이다. 시뮬레이션이란?시뮬레이션의 핵심은 문제의 규칙을 그대로 따라가야 한다는 것에 있다. 위 문제는 로봇이 모든 곳을 탐색하는게 아니라, 정해진 규칙대로만 움직이는 특징이 있다. 왼쪽 확인 없으면 또 왼쪽 4번 다 확인 뒤로 이동 로봇청소기는 이 규칙을 가진다. // 북 동 남 서int[] dy = {-1, 0, 1, 0};int[] dx = {0, 1, 0, -1}; 먼저 방향을 숫자로 표현하기 위해 좌표를 잡는다. y = 행 (위 아래), x=열(좌우) 예를 들면 북쪽으로 이동할경우 행이 줄어든다. (1,1) → (0,1)따라서d..

DFS / BFS 알고리즘의 특징은 이전 글에서 정리한 적 있다.코테 준비를 하면서, 어떤 유형에서 어떤 알고리즘을 써야할지 헷갈리는 부분이 많아 정리해보려고 한다. DFS일반적으로 재귀함수를 이용하여 구현한다. 정점 v를 방문한다.정점 v에서 인접한 정점 중에 방문하지 않은 정점 w가 있다면 w를 v로 하여 1부터 재귀함수를 반복한다.인접한 정점을 모두 방문했다면 스택에서 정점을 꺼내 위를 반복한다. import java.util.LinkedList;public class DFS_Graph { private int V; private LinkedList adj[]; DFS_Graph(int v){ V = v; adj = new LinkedList[v]; ..

깊이 우선 탐색이란루트 노드 (혹은 다른 임의의 노드)에서 시작해서 다음 분기(branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법이다.넓게 탐색하기 전에, 깊게 탐색하는것이다.더 이상 갈곳이 없는 정점에 도착했다면 마지막에 따라왔던 간선을 따라 뒤로 돌아간다. 깊이 우선 탐색이 너비 우선 탐색보다 좀 더 간단하다. 검색 속도는 너비 우선 탐색보다 느리다. DFS의 가장 큰 특징 ➡️ 재귀적인 특징으로 구현을 한다.그래서 각 원소를 포함시킬지 말지 여부를 다 시도해야 하는 완전 탐색의 경우 재귀호출이나 DFS로 짜는것이 쉽다. 다음은 그래프 형식의 DFS 이다.노드 간 연결을 리스트로 관리한다.import java.util.LinkedList;public class DFS_study {..

Deque란? 양쪽 끝에서 삭제와 삽입이 전부 가능하다. 스택과 큐를 덱의 특수한 예시라고 생각할 수 있다. 원소의 추가가 O(1)원소의 제거가 O(1)제일 앞/뒤의 원소 확인이 O(1)제일 앞/뒤가 아닌 나머지 원소들의 확인/변경이 원칙적으로 불가능 배열과 연결리스트 둘다 구현할 수 있지만, 배열을 이용하는 방식이 훨씬 더 편리하다.head ➡️ 가장 앞에 있는 원소의 인덱스tail ➡️ 가장 뒤에 있는 원소의 인덱스 +1 큐와 다르게 양쪽으로 삭제와 삽입이 모두 가능하기 때문에, 초기값을 max로 둔다! Deque의 자주 쓰이는 메서드offerLast(E e)뒤에 원소 추가큐 삽입pollFirst()앞에서 원소 꺼내고 제거큐 삭제peekFirst()앞 원소 확인 (삭제 X)큐 조회offerFirst(..

MapMap은 키 - 값의 쌍을 저장하는 자료구조 이다. 키는 맵 내에서 유일해야 한다.키는 중복될 수 없지만, 값은 중복될 수 있다.순서를 유지하지 않는다. HashMap이란?데이터를 저장할 때 Key와 Value가 짝을 이루어 저장된다.데이터를 저장할때는 키 값으로 해시 함수를 실행한 결과를 통해 저장 위치를 결정한다.따라서 HashMap은 특정 데이터의 저장위치를 해시 함수를 통해 바로 알 수 있기 때문에 데이터의 추가, 삭제, 검색이 빠르다. 삽입, 삭제, 검색 작업은 해시 자료 구조를 사용하므로 일반적으로 상수시간 O(1)의 복잡도를 가진다. HashMap 자주 쓰이는 메서드 정리put(K key, V value)키와 값을 맵에 저장. 기존 키가 있으면 값 덮어쓰기기존 값 또는 nullge..

동적 프로그래밍 (DP) 란?복잡한 문제를 더 작은 하위 문제로 나누어 해결하는 알고리즘 설계 기법이다.큰 문제를 작은 여러 개의 문제로 쪼개서 푸는데, 겹치는 부분이 있으면 한번 풀었던 답을 잘 저장해뒀다가 나중에 다시 계산하지 않고 재활용한다. 결정을 내리기 전에 작은 문제들을 먼저 해결하고, 그 결과를 바탕으로 최적의 선택을 하기 때문에상향식 접근 방식 (bottom-up) 접근 방식이라고도 불린다. DP 기법을 적용시키기 위해 1. 중복되는 부분 문제동일한 작은 문제들이 반복하여 나타나는 경우에 사용이 가능하다.2. 최적 부분 구조 부분 문제의 최적 결과 값을 사용해 전체 문제의 최적 결과를 낼 수 있는 경우 사용이 가능하다. Memoization memoization은 동적 프로그래밍 기법 ..

그리디 알고리즘(Greedy Algorithm)이란? 현재 상황에서 가장 최적이라고 생각되는 것을 선택해 나가는 방식으로 진행하여 해답에 도달하는 알고리즘이다.문제를 풀 때, 두가지 조건이 성립해야 그리디 알고리즘을 적용시킬 수 있다. 1. Greedy Choice Property이 선택이 항상 전체 문제의 최적해를 반드시 도출할 수 있어야 한다.그리디 알고리즘을 사용해서 푸는 문제가 나왔을 때, 이 조건이 만족되는가?를 생각해 충족되면 그리디 알고리즘을 사용하는 것이다. 2. Optimal Substructure 문제에 대한 최종 해결 방법이 부분 문제에 대해서도 최적해로 구성될 수 있는 경우를 말한다.즉, 전체 문제를 작은 부분 문제로 나누어 각각의 부분 문제에서 최적의 해를 구한 후 이를 조합하여 ..

DFS (Depth- First Search) 깊이 우선 탐색 루트 노드에서 시작해서 다음 분기로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방식을 말한다.주로 재귀함수 또는 Stack 으로 구현할 수 있다. 일반적으로 재귀함수를 통해 구현한다.탐색할 때 한 방향으로 갈 수 있을 때까지 계속 가다가 더 이상 갈 수 없게 되면 다시 가장 가까운 갈림길로 돌아와서 이곳으로부터 다른 방향으로 다시 탐색을 진행한다. BFS보다 좀 더 간단하며, 모든 노드를 방문하고자 하는 경우에 이 방법을 선택한다. 어떤 노드를 방문했었는지 여부를 반드시 검사해야한다. ➡️ 목표 노드가 깊은 단계에 있을 경우 해를 빨리 구할 수 있다. BFS(Breadth-First-Search) 너비 우선 탐색 시작 노드에서 인..