본문 바로가기

알고리즘

 (100)
백준 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. 이미 있는 비숍을 ..
백준 11049 행렬 곱셈 순서 https://www.acmicpc.net/problem/11049 11049번: 행렬 곱셈 순서 첫째 줄에 입력으로 주어진 행렬을 곱하는데 필요한 곱셈 연산의 최솟값을 출력한다. 정답은 231-1 보다 작거나 같은 자연수이다. 또한, 최악의 순서로 연산해도 연산 횟수가 231-1보다 작거나 같� www.acmicpc.net 1차 시도는 브루트 포스였다. 매 번 가능한 모든 곱셈 결과 중 가장 작은 것을 합쳤다. 그럴싸하지만 이게 전체의 최적값을 보장하는 지 증명하지 못했고 --> 틀렸습니다 를 받았다. ㅠㅠ 2차 시도도 비슷했다. 원소 중에 가장 큰 값을 골라서 그 주변의 행렬을 곱했다. 이것역시 전체의 최적 값을 보장하지 않는다. --> 틀렸습니다 를 받았다. 결국 답은 Recursive + Memo..
백준 16235 나무 재테크 https://www.acmicpc.net/problem/16235 16235번: 나무 재테크 부동산 투자로 억대의 돈을 번 상도는 최근 N×N 크기의 땅을 구매했다. 상도는 손쉬운 땅 관리를 위해 땅을 1×1 크기의 칸으로 나누어 놓았다. 각각의 칸은 (r, c)로 나타내며, r은 가장 위에서부터 www.acmicpc.net 단순 구현이다. 삼성은 이런 문제가 많더라 /* 나무 재테크 */ #include #include #include #define BOARD 10 + 1 using namespace std; void input(); void solve(); int N, M, K; int dr[8] = { -1, -1, -1, 0, 1, 1, 1, 0 }; int dc[8] = { -1,0,1,1,1..
백준 10026 적록색약 https://www.acmicpc.net/problem/10026 10026번: 적록색약 문제 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G( www.acmicpc.net 간단한 DFS 혹은 BFS 문제다. 두 개의 배열을 이용하면 금방 풀 수 있다. 아마 이 문제의 핵심은 Input 함수일듯...? /* 적록색약 */ #include #include #include using namespace std; void input(); void solve(); int N, WEAKNESS, NO_WEAKNESS; int dr[4] = { -1,0,1,0 }; int..
백준 1103 게임 https://www.acmicpc.net/problem/1103 1103번: 게임 줄에 보드의 세로 크기 N과 가로 크기 M이 주어진다. 이 값은 모두 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 보드의 상태가 주어진다. 쓰여 있는 숫자는 1부터 9까지의 자연수 또는 www.acmicpc.net 1. 그래프를 이용해서 최장거리 + Cycle 체크로 푸는 사람도 있고 2. DFS + 다이나믹 프로그래밍을 이용해서 풀수도 있다 2번이 더 간단하므로 2번으로 풀었다. 기회가 된다면 1번으로 풀어보는 것도 좋겠다. (되는지는 확실치 않음) 이 문제에서 주어지는 input은 그래프로 치자면 양방향 간선이라서 그냥 방문한 곳을 또 방문하면 무한 루프가 생겼다고 볼 수 있다. 그래서 재방문시 -1을 ..

티스토리툴바