본문 바로가기

알고리즘

 (179)
[HackerRank] Is This a Binary Search Tree? (Java, 이진탐색트리 판단, 확인) www.hackerrank.com/challenges/is-binary-search-tree/problem Is This a Binary Search Tree? | HackerRank Given the root of a binary tree, you have to tell if it's a binary search tree. www.hackerrank.com ## 접근방법 정말 좋은 문제다, 지금까지 이진탐색트리의 시간복잡도, 삽입, 탐색에 관해서만 생각했었다. 만들어진 이진트리를 판단하는 문제는 접해보지 않았다. 어떻게 이진트리임을 판단할 것인가? 처음에는 단순 자식으로만 값의 비교를 통해서 확인하려고 했다. 이것은 아주 위험하고 어리석은 생각이다. 이진트리는 왼쪽 이진트리의 노드들은 모두 현재 값보다..
[HackerRank] Organizing Containers of Balls(Java) www.hackerrank.com/challenges/organizing-containers-of-balls/problem Organizing Containers of Balls | HackerRank Determine if David can perform some sequence of swap operations such that each container holds one distinct type of ball. www.hackerrank.com ## 접근방법 이 문제는, 예제를 그리다가 아이디어가 쉽게 떠올랐다. 아이디어가 말로 표현하기 편해서 글을 쓰게 되었다. 이 문제의 목적은, 컨테이너에 한 가지의 공으로 가득채워야 한다. 어떻게 풀것인가? 과정을 생각하려 하지말고, 결과에 초점을 맞춰보자. ..
[HackerRank] Queen's Attack II(Java) ## 접근방법 쉬워보였지만, 의외로 시간이 걸렸던 문제이다. 두 가지 접근 방법을 소개하려고 한다. 첫번째로는 직관적으로 문제를 풀어보자. 퀸에서 출발하여, 벽을 만나는 순간의 여러 방향의 끝지점의 좌표를 미리 구해주자. 이제는 방해물 좌표를 가지고, 여러 방향의 끝지점 좌표들을 막을 수 있는지 확인해야 한다. 즉, 퀸, 장애물, 끝지점 좌표가 한 직선위에 있어야 한다. 수직선은 열이 모두 같아야 하고, 수평선은 행이 모두 같아야 한다. 대각선 일 때는, 기울기가 동일해야 한다. 위의 조건만으로는 부족하므로, 점의 대소 관계를 통해서 가운데 있음을 확인하면 된다. 첫번째 접근 방식은 구현이 지저분하다는 생각이 들었다. 구글링을 통해서 두번째 접근 방법을 알았다. 두번째 접근은 좀 더 직관적이다. 수직선,..
[BOJ 2812] 크게 만들기(Stack, Java) www.acmicpc.net/problem/2812 2812번: 크게 만들기 N자리 숫자가 주어졌을 때, 여기서 숫자 K개를 지워서 얻을 수 있는 가장 큰 수를 구하는 프로그램을 작성하시오. www.acmicpc.net ## 접근방법 이 문제는 스택을 이용해서 풀어야 한다. N이 500,000이므로 우선순위큐를 이용한 N * logN 시간복잡도가 걸린다면, 시간초과가 발생할 것이다. 따라서, 선형 탐색이 필요하다. K개를 지워서 가장 큰 수를 만드려면, 앞자리수가 커야 좋다. 값을 비교하고, 가장 큰 수를 만들수 있는 후보들을 저장하는 자료구조가 필요하다. 스택을 사용하면 입력된 순서대로 값의 비교가 가능하므로 자료구조로 스택을 사용할 것이다. 값을 비교할 때는, 스택의 peek 값과 현재 가르키는 값을..
[BOJ 1103] 게임(Java, DFS, DP, Cycle) www.acmicpc.net/problem/1103 1103번: 게임 줄에 보드의 세로 크기 N과 가로 크기 M이 주어진다. 이 값은 모두 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 보드의 상태가 주어진다. 쓰여 있는 숫자는 1부터 9까지의 자연수 또는 www.acmicpc.net ## 접근 이 문제는 정답률에 비해서 어렵지 않은 문제이다. 보드의 크기만큼의 DP를 선언해주고, DP의 값을 갱신하면서 가장 큰 이동 횟수를 구해주면 된다. DP[nr][nc] = DP[r][c] + 1 nr, nc는 r, c에서 이동할 수 있는 신규 점을 의미한다. +1은 이동 횟수가 더해짐을 의미한다. 어떤 nr, nc를 접근할 때, 기존에 가진 값을 갱신하지 못하면 이동할 필요가 없다. 이 문제에서는 위..
[BOJ 11003] 최솟값 찾기(Deque) www.acmicpc.net/problem/11003 11003번: 최솟값 찾기 N개의 수 A1, A2, ..., AN과 L이 주어진다. Di = Ai-L+1 ~ Ai 중의 최솟값이라고 할 때, D에 저장된 수를 출력하는 프로그램을 작성하시오. 이때, i ≤ 0 인 Ai는 무시하고 D를 구해야 한다. www.acmicpc.net ## 접근 특정 구간이라는 단어를 보면 세그먼트 트리를 습관적으로 이용하려고 했다. N * logN의 시간복잡도를 가지므로 나쁘지 않은 선택이지만 이 문제에서 시간 초과가 발생한다. 이 문제는 세그먼트 트리와 다르게 고정된 길이의 구간의 값들의 최솟값을 요구하고 있다. 세그먼트 트리보다 더 빠르게 최소값을 찾을 수 있지 않을까? 최소값을 바로 얻을 수 있는 자료구조가 필요하다. ..
[BOJ 2357] 최솟값과 최댓값(Segment Tree, 세그먼트 트리, 자바) www.acmicpc.net/problem/2357 2357번: 최솟값과 최댓값 N(1 ≤ N ≤ 100,000)개의 정수들이 있을 때, a번째 정수부터 b번째 정수까지 중에서 제일 작은 정수, 또는 제일 큰 정수를 찾는 것은 어려운 일이 아니다. 하지만 이와 같은 a, b의 쌍이 M(1 ≤ M ≤ 100 www.acmicpc.net ## 시간복잡도 문제에서, 특정 구간의 최솟값과 최댓값을 구해야 한다. 일반적으로 생각했을때, M개의 a와 b마다 정렬을 하고 최소값과 최대값을 구한다면 O(M * N * logN)의 시간복잡도가 발생한다. M과 N은 최대 10만이므로 무조건 시간초과가 발생한다. ## 세그먼트 트리 이 문제는 세그먼트 트리 개념을 모르면 풀 수 없다. 알고리즘에서 특정 구간들에 대한 계산된..
[BOJ 1701] Cubeditor (백준, JAVA, KMP) www.acmicpc.net/problem/1701 1701번: Cubeditor Cubelover는 프로그래밍 언어 Whitespace의 코딩을 도와주는 언어인 Cubelang을 만들었다. Cubelang을 이용해 코딩을 하다보니, 점점 이 언어에 맞는 새로운 에디터가 필요하게 되었다. 오랜 시간 고생한 www.acmicpc.net ## KMP 알고리즘 찾아야 하는 단어의 길이를 S, 전체 문서의 길이를 T라고 해보자. 모든 문서에서 단어를 비교하게 된다면 최악의 시간 복잡도는 O(T * S)가 된다. O(T * S)보다 시간을 줄일 수 있는 방법을 KMP 알고리즘이라고 한다. KMP 알고리즘의 핵심은, 검사된 문자의 정보를 이용하는 것이다. 찾아야 하는 단어의 문자의 substring(0, n)마다 ..

티스토리툴바