모기와의 스파링 기록장

이진 탐색이란?이진 탐색 알고리즘은 정렬된 배열, 리스트에서 원하는 값을 빠르게 찾아낼 수 있는 알고리즘이다. 이진 탐색이 얼마나 빠른지는 다른 대표적인 알고리즘인 선형 탐색 알고리즘과 비교해볼 수 있다. 선형 탐색의 경우, 앞에서부터 차례대로 탐색하므로 O(n)의 시간복잡도를 갖지만 이진 탐색은 무려 O(log n)의 시간복잡도를 갖는다. 하지만 배열이 정렬된 상태에서 이진 탐색이 올바르게 작동함을 유의해야 한다.    이진 탐색 알고리즘 설명이진 탐색 알고리즘의 핵심은 탐색 범위를 반으로 좁히는 것에 있다. 탐색 범위의 중앙에 있는 값을 보고, 우리가 찾는 값이 어느 범위에 있을지 찾아내는 것이다. 따라서 중복 없이 오름차순 정렬된 배열에서 이진 탐색은 아래와 같은 순서로 진행된다.배열 내에서 값 k..

탐색 알고리즘경우의 수(그래프의 노드)를 탐색하는 탐색 알고리즘, 그 중에서도 모든 경우의 수를 탐색하는 완전 탐색 알고리즘에는 크게 두 종류가 있는데, BFS(Breadth First Search - 너비 우선 탐색), DFS(Depth First Search - 깊이 우선 탐색)가 이에 속한다. BFS는 큐를 이용해 현재 노드와 가까운 순서대로 노드를 탐색해 나가는 방법이고, DFS는 스택을 이용해 현재 노드와 연결된 다음 노드를 차례로 탐색해 나가는 방법이다. 참고로 함수 호출에 스택을 이용하기에 주로 재귀 함수를 이용해 DFS를 구현한다고 한다. 그래프 탐색 알고리즘에 대한 자세한 정보는 아래 링크를 참고하면 될 것 같다.https://jin1ib.tistory.com/entry/BFS-DFS-1..

문제 링크https://www.acmicpc.net/problem/9663    풀이 과정체스판의 0번째 행부터 차례대로 퀸을 위치시키는 방식으로 해결했다. 아래 코드에서 loc이 퀸의 위치를 저장시키는 배열이며 인덱스가 행을, 대응하는 원소값이 열을 의미하는 것을 전제로 한다. 행을 매개변수로 받는 sol 메소드 내에서 현재 행에 대한 모든 열을 검사해 유효한 점에서 다음 행의 sol 메소드를 재귀 호출한다. 이때 행값을 매개변수로 받는 check 메소드가 sol 내에서 호출되어 현재 행 이전에 위치한 모든 퀸의 동선(열, 대각선 방향)과 겹치지 않는지 확인한다. 재귀를 통해 최종적으로 sol(n)이 호출되면 지금까지 퀸 n개의 배치가 유효하다는 뜻이므로 count를 1 증가시킨다. sol 메소드가 이..

문제 링크https://www.acmicpc.net/problem/2447    풀이 과정별 모양으로 채운 2차원 배열에서 시작해 현재 사각형의 9등분에서 가운데 부분을 빈칸으로 바꾸는 식으로 문제를 해결했다. eraseStar의 매개변수 중 row, col은 도형의 시작점이고, temp라는 변수를 이용해 9등분을 구현했다. for문을 이용해 eraseStar를 9번 재귀 호출했다. 중간에 빈칸으로 채워지는 부분까지 호출되는데, 어차피 빈칸이므로 정답에 지장은 없다.    코드import java.util.*;import java.io.*;class Main { static void eraseStar(char[][] arr, int row, int col, int size) { int ..

문제 링크https://www.acmicpc.net/problem/24511    풀이 과정queuestack이 어떤 방식으로 작동하는지 보고, 최대한 간단한 방식으로 queuestack을 구현해야 한다. 임의의 원소를 queuestack에 삽입한 경우 길이 n인 queuestack의 i번째 원소가 어떤 값을 리턴하는지를 생각해보자. i번째 원소가 큐일 경우 자신이 이전에 갖고 있던 값을 리턴하고, 스택일 경우 삽입한 원소를 그대로 리턴한다.(임의의 데이터 x0을 삽입했을 때 1번 자료구조가 큐인 경우 x1을 리턴하고, 스택인 경우 x0을 리턴) 즉 스택에 저장된 원소는 절대로 queuestack의 리턴값이 될 수 없고, 큐에 저장된 원소는 다음 자료구조로 넘어가는 방식이라고 볼 수 있다. 위와 같은 이..

문제 링크https://www.acmicpc.net/problem/12789    풀이 과정# 문제에서의 예시1번을 통과시키기 위해 1번 앞에 있는 5번, 4번을 모두 왼쪽 공간으로 이동시킨다.그리고 2번을 통과시키기 위해 앞의 3번을 왼쪽 공간으로 이동시킨다.줄에 있는 사람이 다 없어졌다면, 왼쪽 공간의 3~5번이 왼쪽 공간으로 들어온 순서의 반대로 통과한다. 원래 서있던 줄에서는 순서대로 빠져나갈 수 있고, 왼쪽 공간에서는 들어온 순서의 반대로 빠져나가는 것을 이용해 문제를 해결해야 한다. 1번을 먼저 통과시키기 위해, 입력으로 들어온 순서 정보를 큐에 저장한 뒤 순차적으로 조사하면 문제 상황을 구현할 수 있다. 큐의 앞부분을 확인하고 제거하는 식으로 큐를 순차적으로 조사할 수 있다.(이때 제거의 의..