사이트 링크 : https://www.acmicpc.net/problem/1072 문제는 아래와 같습니다. 문제 N명의 병사가 무작위로 나열되어 있다. 각 병사는 특정한 값의 전투력을 보유하고 있으며, 병사를 배치할 때는 전투력이 높은 병사가 앞쪽에 오도록 내림차순으로 배치를 하고자 한다. 다시 말해 앞쪽에 있는 병사의 전투력이 항상 뒤쪽에 있는 병사보다 높아야 한다. 또한 배치 과정에서는 특정한 위치에 있는 병사를 열외시키는 방법을 이용한다. 그러면서도 남아있는 병사의 수가 최대가 되도록 하고 싶다. 예를 들어, N=7일 때 나열된 병사들의 전투력이 다음과 같다고 가정하자. 이 때 3번 병사와 6번 병사를 열외시키면, 다음과 같이 남아있는 병사의 수가 내림차순의 형태가 되며 5명이 된다. 이는 남아있는..

사이트 링크 : https://www.acmicpc.net/problem/1300 문제는 아래와 같습니다. 문제 세준이는 크기가 N×N인 배열 A를 만들었다. 배열에 들어있는 수 A[i][j] = i×j 이다. 이 수를 일차원 배열 B에 넣으면 B의 크기는 N×N이 된다. B를 오름차순 정렬했을 때, B[k]를 구해보자. 배열 A와 B의 인덱스는 1부터 시작한다. 입력 첫째 줄에 배열의 크기 N이 주어진다. N은 105보다 작거나 같은 자연수이다. 둘째 줄에 k가 주어진다. k는 min(109, N2)보다 작거나 같은 자연수이다. 출력 B[k]를 출력한다. 문제 해결 포인트 문제의 아이디어가 떠오르지 않아 정말 시간을 많이 사용한 문제였습니다. ㅋㅋ 해당 문제에서 가장 중요한 포인트는 count_belo..

Trie 알고리즘이란 문자열을 검색을 할때 트리 형식으로 각 단어를 하위 노드에 저장하여 시간 복잡도가 (Mlog(n)) 인 알고리즘 사용하는 이유는 문자열의 탐색을 하고자할 때 시간복잡도를 보면 알 수 있습니다. 단순하게 하나씩 비교하면서 탐색을 하는것보다 훨씬 효율적입니다. 단, 빠르게 탐색이 가능하다는 장점이 있지만 각 노드에서 자식들에 대한 포인터들을 배열로 모두 저장하고 있다는 점에서 저장 공간의 크기가 크다는 단점도 있습니다. 검색어 자동완성, 사전에서 찾기 그리고 문자열 검사 같은 부분에서 사용할 수 있다고 위키에 보면 나와있습니다. 이 알고리즘을 이용한 문제는 대표적으로 프로그래머스의 가사 검색 문제입니다. class Node: def __init__(self, key, data=None)..

이분 탐색 문제를 풀어보다가 최장증가수열 알고리즘으로 풀수있는 알고리즘이 있어 이론을 정리를 하려고 합니다. 최장증가부분수열(LIS,Longest increasing subsequence) 이란 주어진 원소 n개인 배열에서 오름차순으로 정렬된 가장 긴 부분수열을 찾는 알고리즘입니다. 즉 각 원소가 이전 원소보다 크다는 조건을 만족하고 그 길이가 최대안 부분수열을 최장 증가부분수열입니다. 예를 들어 아래와 같은 수열이 있다고 가정을 해봅시다 [3, 5, 7, 9, 2, 1, 4, 8] 여기서 증가하는 부분수열을 만든다면 했을때 졍렬이 아닌 요소를 제외하는 방법으로 한다면 아래와 같이 여러가지가 나올수 있습니다. [3,5,6,7] [1,4,8] [2,4,8] ... 등이 있지만 제일 긴 수열은 3,5,6,8..

사이트 링크 : https://www.acmicpc.net/problem/1365 문제는 아래와 같습니다. 문제 공화국에 있는 유스타운 시에서는 길을 사이에 두고 전봇대가 아래와 같이 두 줄로 늘어서 있다. 그리고 길 왼편과 길 오른편의 전봇대는 하나의 전선으로 연결되어 있다. 어떤 전봇대도 두 개 이상의 다른 전봇대와 연결되어 있지는 않다. 문제는 이 두 전봇대 사이에 있는 전깃줄이 매우 꼬여 있다는 점이다. 꼬여있는 전깃줄은 화재를 유발할 가능성이 있기 때문에 유스타운 시의 시장 임한수는 전격적으로 이 문제를 해결하기로 했다. 임한수는 꼬여 있는 전깃줄 중 몇 개를 적절히 잘라 내어 이 문제를 해결하기로 했다. 하지만 이미 설치해 놓은 전선이 아깝기 때문에 잘라내는 전선을 최소로 하여 꼬여 있는 전선..

사이트 링크 : https://www.acmicpc.net/problem/1072 문제는 아래와 같습니다. 문제 김형택은 지금 몰래 Spider Solitaire(스파이더 카드놀이)를 하고 있다. 형택이는 이 게임을 이길 때도 있었지만, 질 때도 있었다. 누군가의 시선이 느껴진 형택이는 게임을 중단하고 코딩을 하기 시작했다. 의심을 피했다고 생각한 형택이는 다시 게임을 켰다. 그 때 형택이는 잠시 코딩을 하는 사이에 자신의 게임 실력이 눈에 띄게 향상된 것을 알았다. 이제 형택이는 앞으로의 모든 게임에서 지지 않는다. 하지만, 형택이는 게임 기록을 삭제 할 수 없기 때문에, 자신의 못하던 예전 기록이 현재 자신의 엄청난 실력을 증명하지 못한다고 생각했다. 게임 기록은 다음과 같이 생겼다. 게임 횟수 : ..