알고리즘/백준 (89) 썸네일형 리스트형 백준 1516 게임 개발 https://www.acmicpc.net/problem/1516 1516번: 게임 개발 첫째 줄에 건물의 종류 수 N(1 ≤ N ≤ 500)이 주어진다. 다음 N개의 줄에는 각 건물을 짓는데 걸리는 시간과 그 건물을 짓기 위해 먼저 지어져야 하는 건물들의 번호가 주어진다. 건물의 번호는 1부 www.acmicpc.net 위상정렬 문제다. 차이가 있다면 '시간'이라는 변수가 추가된 것! 보통은 'C건물이 완성되려면 A건물과 B건물이 완성되어야 합니다' 라는 문제조건에 따라 inedge의 개수만 세면 되는데 이 문제는 '시간'이 기준이어서 A건물과 B건물이 완성되는 시간 모두를 고려하는 게 아니라 둘 중 더 늦게 완성되는 건물의 완성 시간을 기준으로 잡아야 한다. 즉 Queue가 아니라 priority Q.. 백준 9935 문자열 폭발 https://www.acmicpc.net/problem/9935 9935번: 문자열 폭발 문제 상근이는 문자열에 폭발 문자열을 심어 놓았다. 폭발 문자열이 폭발하면 그 문자는 문자열에서 사라지며, 남은 문자열은 합쳐지게 된다. 폭발은 다음과 같은 과정으로 진행된다. 문자열이 www.acmicpc.net Stack을 활용하는 문제다. 정확히 말하면 STL이나 여타 라이브러리가 아니라 Stack의 LIFO을 이용한다. 백만이나 되는 Input과 2초 밖에 안되는 시간제한을 고려했을 때 별다른 선택지가 없었다. 비교 연산을 1억번 할 때 1초 정도가 들기 때문에 2초면 비교 연산만 고려해도 2억번 이내로 해결해야한다. 하지만 Input이 100만 이기 때문에 N^2는 최악의 경우 100 0000 * 100 .. 백준 9019 DSLR https://www.acmicpc.net/problem/9019 9019번: DSLR 문제 네 개의 명령어 D, S, L, R 을 이용하는 간단한 계산기가 있다. 이 계산기에는 레지스터가 하나 있는데, 이 레지스터에는 0 이상 10,000 미만의 십진수를 저장할 수 있다. 각 명령어는 이 레지스� www.acmicpc.net 간단한 구현 문제인데 시간초과가 빡세다... 완전 탐색으로 풀면된다. 처음엔 map 자료형과 bfs를 혼합해서 풀었는데 시간초과가 떳다. map 자료형이 시간이 꽤 드는 듯... 역시 임의 접근만큼 빠른게 없다. 방문 체크를 할 bool array를 하나 만들어서 작업을 했다. /* DSLR */ #include #include #include #include using names.. 백준 5214 환승 https://www.acmicpc.net/problem/5214 5214번: 환승 문제 아주 먼 미래에 사람들이 가장 많이 사용하는 대중교통은 하이퍼튜브이다. 하이퍼튜브 하나는 역 K개를 서로 연결한다. 1번역에서 N번역으로 가는데 방문하는 최소 역의 수는 몇 개일까? 입 www.acmicpc.net BFS를 쓰면 되는 문제이지만 메모리 초과가 문제가 된다 . Edge를 연결하는 과정에서 브루트포스를 적용하면 무려 10 ^ 9가 된다. 일일히 두 개를 연결하지 않고 Hub처럼 동작할 dummy 노드를 하나 만들면 공간복잡도를 크게 줄일 수 있다. 앞으로도 유용하게 쓸 수 있는 스킬인 것 같다. /* 환승 */ #include #include #include #define MAX 100000 + 1 us.. 백준 1700 멀티탭 스케줄링 https://www.acmicpc.net/problem/1700 1700번: 멀티탭 스케줄링 기숙사에서 살고 있는 준규는 한 개의 멀티탭을 이용하고 있다. 준규는 키보드, 헤어드라이기, 핸드폰 충전기, 디지털 카메라 충전기 등 여러 개의 전기용품을 사용하면서 어쩔 수 없이 각종 전 www.acmicpc.net 그리디 알고리즘을 쓴다. 사실 왜 골드2인지 모르겠다. /* 멀티탭 스케줄링 */ #include #include #include using namespace std; int n_of_hole, n_of_use, total_used; vector use_schedule; map used; //vector used; void input(); void solve(); int main(void) { i.. 백준 5052 전화번호 목록 https://www.acmicpc.net/problem/5052 5052번: 전화번호 목록 문제 전화번호 목록이 주어진다. 이때, 이 목록이 일관성이 있는지 없는지를 구하는 프로그램을 작성하시오. 전화번호 목록이 일관성을 유지하려면, 한 번호가 다른 번호의 접두어인 경우가 없� www.acmicpc.net 트라이 문제다. 트라이 문제를 몇 개 더 풀면서 이런 유형에 익숙해지는 것도 좋을 듯 하다! https://www.acmicpc.net/problem/tag/%ED%8A%B8%EB%9D%BC%EC%9D%B4 트라이 - 1 페이지 www.acmicpc.net 그런 의미에서 트라이 관련문제가 모여있는 백준 사이트도 링크했다. /* 전화번호 목록 */ #include #include #include #in.. 백준 9934 완전 이진 트리 https://www.acmicpc.net/problem/9934 9934번: 완전 이진 트리 문제 상근이는 슬로베니아의 도시 Donji Andrijevci를 여행하고 있다. 이 도시의 도로는 깊이가 K인 완전 이진 트리를 이루고 있다. 깊이가 K인 완전 이진 트리는 총 2K-1개의 노드로 이루어져 있다. (�� www.acmicpc.net 트리 형태로 구현하면 된다. 그리고 높이별로 인쇄하면 됨 queue를 이용했다. (Inorder 순회 같기도?) /* 완전 이진 트리*/ #include #include #include #include #define MAX 1024 + 1 using namespace std; void input(); void solve(); int K, n_in_height; int.. 백준 3665 최종 순위 https://www.acmicpc.net/problem/3665 3665번: 최종 순위 문제 올해 ACM-ICPC 대전 인터넷 예선에는 총 n개의 팀이 참가했다. 팀은 1번부터 n번까지 번호가 매겨져 있다. 놀랍게도 올해 참가하는 팀은 작년에 참가했던 팀과 동일하다. 올해는 인터넷 예선 �� www.acmicpc.net 문제를 보자마자 위상 정렬 느낌이 난다. 특이한 점이 있다면, 두 팀의 상대순위를 바꾸는 작업을 할 때 다른 팀과의 상대 순위는 유지해야 한다는 점이다. 즉, 2->3->4 였는데 2와 4는 바꾼다고 해서 4->3->2를 하면 안된다!! 다른 곳은 단순히 Input을 받는 곳이고 solve() 함수에서 해결한다. #include #include #include #include #incl.. 백준 16234 인구 이동 https://www.acmicpc.net/problem/16234 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모�� www.acmicpc.net 단순한 시뮬레이션 문제다. #include #include #include #include #define pp pair #define MAXN 50 + 1 using namespace std; bool open_the_gate[MAXN][MAXN][4]; int map[MAXN][MAXN]; int N, L, R; int dr[4] = { -1, 0, 1, 0 }; int dc[.. 백준 1799 비숍 https://www.acmicpc.net/problem/1799 1799번: 비숍 첫째 줄에 체스판의 크기가 주어진다. 체스판의 크기는 10이하의 자연수이다. 둘째 줄부터 아래의 예와 같이 체스판의 각 칸에 비숍을 놓을 수 있는지 없는지에 대한 정보가 체스판 한 줄 단위로 www.acmicpc.net 탐색계의 절대강자가 나타났다... 시간 제한이 무려 10초라서, '아~ 시간제한 신경 안써도 되겠네'라고 생각하기 쉽다. 게다가 Input의 최대치가 10이라니?! N! 을 해도 10초는 통과할 수 있다! 하지만... 그냥 완전탐색했다가는 나처럼 좌절을 겪고 모든 코드를 삭제하는 수모를 감내해야만 한다. O(2^(N*N))이었던가... 그렇다. 이 문제를 두 가지로 생각할 수 있다 1. 이미 있는 비숍을 .. 이전 1 ··· 5 6 7 8 9 다음
