본문 바로가기

분류 전체보기

 (341)
[백준 / BOJ] 11054 가장 긴 바이토닉 부분 수열 문제 출처 : www.acmicpc.net/problem/11054 11054번: 가장 긴 바이토닉 부분 수열 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000) www.acmicpc.net 수열S가 주어진다. 이때, 수열S의 어떤 수 A를 기준으로 A이전의 수가 증가하는 부분 수열 일때, A 이후가 감소하는 부분 수열 이라면, 그 수열을 바이토닉 수열 이라고 한다. 이때, 수열 S에서 가능한 모든 바이토닉 수열중 가장 긴 수열의 길이를 구하는 문제다. 풀이 N이 1000이므로 완전탐색으로 풀경우 시간초과가 난다. 다이나믹 프로그래밍으로 풀어야 하는 문제였다. 문제 이해가 좀 어려운 문제였다, 문제에서 ..
[백준 / BOJ] 2638 치즈 문제 출처 : www.acmicpc.net/problem/2638 2638번: 치즈 첫째 줄에는 모눈종이의 크기를 나타내는 두 개의 정수 N, M (5≤N, M≤100)이 주어진다. 그 다음 N개의 줄에는 모눈종이 위의 격자에 치즈가 있는 부분은 1로 표시되고, 치즈가 없는 부분은 0으로 표 www.acmicpc.net N*M크기의 모눈종이에 치즈가 있다. 모눈종이의 가장자리부터 공기가 들어오는데, 공기에 2면 접촉해있는 치즈는 1초후 녹기시작한다. 가장자리에는 치즈가없을때, 모든 치즈가 녹아 없어지는데 걸리는 정확한 시간을 구하는 문제다. 풀이 BFS,DFS를 이용한 시뮬레이션 문제다. N,M이 최대 100,100이라서 총 칸수가 10000칸 까지 갈수있다. 한번 치즈를 녹일때마다 모든 칸을 다 봐준다..
[백준 / BOJ] 2096 내려가기 문제 출처 : www.acmicpc.net/problem/2096 2096번: 내려가기 첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중의 하나가 된다. www.acmicpc.net 내려가기 게임을 하고있다. 이 게임은 첫번째 줄에서 마지막 줄까지 내려가는 게임인데, 내려갈때 일정한 규칙에 따라 내려가야한다. 바로 아래 칸으로 내려가거나 바로 아래칸에 연결된 칸으로만 내려갈수있다. 예를들어, 왼쪽에서 내려갈수있는경우는, 왼쪽아래와 가운데 아래이다. 마지막 줄까지 내려갔을때, 최댓값과 최솟값을 구하는 문제다. 풀이 N이 100000이라서 완전탐색으로 풀경우 시간초과가 난다. 그리디로 풀려고해..
[백준 / BOJ] 13506 카멜레온 부분 문자열 문제 출처 : www.acmicpc.net/problem/13506 13506번: 카멜레온 부분 문자열 문자열 S의 부분 문자열 T 중에서, 접두사(Prefix)도 될 수 있고, 접미사(Prefix)도 될 수 있고, 두 경우가 아닌 위치에도 등장하는 T를 카멜레온 부분 문자열이라고 한다. 문자열 S가 주어졌을 때, 카 www.acmicpc.net 카멜레온 부분 문자열이란, 문자열 S의 접미사이자 접두사인 부분문자열 T가 문자열S에서 한번 더 나오는 문자열을 말한다. 예를들어, fixprefixsuffix에서 fix는 카멜레온 부분문자열인데, fix가 접두사, 접미사, 그리고 중간에 한번 더 나오기때문이다. 마찬가지로 abcabcabc또한 카멜레온 부분문자열이다. 문자열 S가 주어졌을때, 가장 긴 카멜레온..
[백준 / BOJ] 14502 연구소 문제 출처 : www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net N*M그리드가 주어지고, 그리드의 상태가 주어진다. 0 : 빈칸 1 : 벽 2 : 바이러스 바이러스는 매초 상하좌우 빈칸으로 확산될수있다. 바이러스가 모두 확산된후 남아있는 빈칸의 수를 안전영역이라 한다. N*M그리드에 벽 3개를 적절히 설치했을때, 안전영역의 최대 크기를 구하는 문제다. 풀이 N과 M의 범위가 크지않아, 완전탐색으로 풀리는문제다. 시간복잡도는 1. N*M그리드 에서 3개의 빈칸을 선택하는 경..
[백준 / BOJ] 18119 단어 암기 - Trie 문제 출처 : www.acmicpc.net/problem/18119 18119번: 단어 암기 준석이는 영어 단어를 외우려고 한다. 사전에는 N가지 단어가 적혀 있다. 모든 단어는 소문자이다. 단어 안에 있는 모든 알파벳을 알 때, 그 단어를 완전히 안다고 한다. 다음과 같은 쿼리들이 주 www.acmicpc.net 준석이가 영어단어를 외울려고한다. 사전에 N가지 단어가적혀있으며, 모든 단어는 소문자로만 이루어져있다. 준석이는 처음에 모든 알파벳을알고있지만, 쿼리가 주어질때마다 알파벳을 까먹을수도 까먹은 단어를 기억할수도있다. 단어장에 적혀있는 N개의 단어와 M번의 쿼리 가 주어졌을때, 각 쿼리마다 준석이가 기억하는 단어의 개수를 출력하는 문제다. 풀이 최악의 경우, N = 10000 이때 각 단어의 길이..
[백준 / BOJ] 1701 Cubeditor 문제 출처 : www.acmicpc.net/problem/1701 1701번: Cubeditor Cubelover는 프로그래밍 언어 Whitespace의 코딩을 도와주는 언어인 Cubelang을 만들었다. Cubelang을 이용해 코딩을 하다보니, 점점 이 언어에 맞는 새로운 에디터가 필요하게 되었다. 오랜 시간 고생한 www.acmicpc.net Cubelover는 텍스트 에디터 Cubeditor를 만들었다. 이 에디터가 다른 에디터와 다른점은, 찾을려하는 문자열이 2번이상 존재해야지 찾는것이다. 예를들어, ababac에서 aba를 찾을려하면 ababac 이렇게 찾을수있다. c를 찾을려하면 c는 한번밖에 나오지 못하므로 찾지못한다. 풀이 완전탐색으로 풀려할경우, 약 5000^3 반복할수있어서 시간초과가..
[백준 / BOJ] 14938 서강그라운드 문제 출처 : www.acmicpc.net/problem/14938 14938번: 서강그라운드 예은이는 요즘 가장 인기가 있는 게임 서강그라운드를 즐기고 있다. 서강그라운드는 여러 지역중 하나의 지역에 낙하산을 타고 낙하하여, 그 지역에 떨어져 있는 아이템들을 이용해 서바이벌을 www.acmicpc.net 예은이가 서강그라운드게임을한다. 서강그라운드는 여러지역중 하나의 지역에 낙하하여, 아이템을 먹고 서바이벌을 하는 게임이다. 예은이는 어떤 지역에 낙하해야 가장 많은 아이템을 얻을수있는지 궁금하다. 지역의 개수 n 각 지역을 연결하는 길 m 지역사이의 거리 l 예은이의 수색범위 m 이 주어졌을때, 얻을 수 있는 아이템의 최대 개수를 출력하면 된다. 풀이 플로이드와샬 혹은 다익스트라로 풀수있는데, 플로이드..

티스토리툴바