본문 바로가기

전체보기

 (168)
백준 11657 /* 타임머신 */ #include #include #include #define INF 2100000000 #define ll long long int #define pp pair using namespace std; void input(); void solve(); struct line { int src, dst, wgt; line(int a, int b, int c) { src = a; dst = b; wgt = c; } }; int N, M; ll dist[501]; vector edge; int main(void) { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); input(); solve(); return 0; } void ..
백준 1865 웜홀 https://www.acmicpc.net/problem/1865 1865번: 웜홀 첫 번째 줄에는 테스트케이스의 개수 TC(1 ≤ TC ≤ 5)가 주어진다. 그리고 두 번째 줄부터 TC개의 테스트케이스가 차례로 주어지는데 각 테스트케이스의 첫 번째 줄에는 지점의 수 N(1 ≤ N ≤ 500), � www.acmicpc.net 벨만 포드 알고리즘을 이용하는 문제다. 이 문제를 풀면서 배운점은 문제의식을 명확히 하라는 점이다. 벨만 포드는 다익스트라 알고리즘보다 시간복잡도(O(V*E) vs O(ElogE))가 크기 때문에 잘 사용하지 않는다. 하지만 다익스트라 알고리즘보다 정확해서 음의 가중치가 섞인 경로에서 최적 경로를 찾아낼 수 있고 음의 사이클의 유무도 파악할 수 있다. 결국은 Shortes Path..
백준 14725 개미굴 https://www.acmicpc.net/problem/14725 14725번: 개미굴 첫 번째 줄은 로봇 개미가 각 층을 따라 내려오면서 알게 된 먹이의 정보 개수 N개가 주어진다. (1 ≤ N ≤ 1000) 두 번째 줄부터 N+1 번째 줄까지, 각 줄의 시작은 로봇 개미 한마리가 보내준 먹이 � www.acmicpc.net 트라이 문제다. 기존의 struct에서 alphabet 개수만큼 배열을 할당한 대신 map으로 바꾼것 말고는 동일하다 . /* 개미굴 */ #include #include #include #include using namespace std; void input(); void solve(); int N; struct trieNode { bool is_terminal; map tri..
백준 10165 버스 노선 https://www.acmicpc.net/status?user_id=museum114&problem_id=10165&from_mine=1 채점 현황 www.acmicpc.net 이런 문제는 경우의 수를 잘 쪼개는 게 중요한 것 같다. 이 문제를 어렵게 만드는 요인은 바로 '원형'이라는 점이다. 우리가 보기에는 원형이든 선형이든 상관없지만 컴퓨터에게 이 문제는 꽤 중요하다. 인덱스가 달라지기 때문이다. 그래서 0(중심점)을 넘어서는 버스 노선은 특별한 연산을 거친 후 vector에 넣었다. 자세한 건 코드로 확인하시라~ /* 버스 노선 */ #include #include #include #include #define ll long long int #define pp pair using namespace..
백준 1256 사전 https://www.acmicpc.net/problem/1256 1256번: 사전 첫째 줄에 N, M, K가 순서대로 주어진다. N과 M은 100보다 작거나 같은 자연수이고, K는 1,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 다이나믹 프로그래밍을 사용하는 문제다. k-th lexicographical string 문제는 문자열 DP 문제에 자주나오는데 이 참에 정리를 해야겠다. /* 사전 */ #include #include #define ll long long int using namespace std; void input(); void solve(); int N, M, K; /* 사실 j에 해당하는 오른쪽 배열은 201로 할 필요가 없지만 연산 코드를 줄이기위해..
백준 17140 이차원 배열과 연산 https://www.acmicpc.net/problem/17140 17140번: 이차원 배열과 연산 첫째 줄에 r, c, k가 주어진다. (1 ≤ r, c, k ≤ 100) 둘째 줄부터 3개의 줄에 배열 A에 들어있는 수가 주어진다. 배열 A에 들어있는 수는 100보다 작거나 같은 자연수이다. www.acmicpc.net 구현..구현 문제다... 아 힘들어... /* 이차원 배열과 연산 */ #include #include #include #include #define pp pair using namespace std; void input(); void solve(); inline bool comp(pp& a, pp& b) { if (a.second == b.second) { return a.first..
백준 5719 거의 최단 경로 https://www.acmicpc.net/problem/5719 5719번: 거의 최단 경로 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 장소의 수 N (2 ≤ N ≤ 500)과 도로의 수 M (1 ≤ M ≤ 104)가 주어진다. 장소는 0부터 N-1번까지 번호가 매겨져 있�� www.acmicpc.net 다익스트라 한 번 돌리고 최적경로 지우고 다익스트라 한 번 돌리면 풀 수 있는 문제다. 아이디어가 직관적으로 떠오르는데, 구현이 까다로운 문제 edge는 점과 Weight를 동시에 저장한다. trace에 최적 경로를 저장한다. dist는 S로부터 모든 점까지의 최단 거리를 계산한다. /* 거의 최단 경로 */ #include #include #include #de..
백준 5557 1학년 https://www.acmicpc.net/problem/5557 5557번: 1학년 상근이가 1학년 때, 덧셈, 뺄셈을 매우 좋아했다. 상근이는 숫자가 줄 지어있는 것을 보기만 하면, 마지막 두 숫자 사이에 '='을 넣고, 나머지 숫자 사이에는 '+' 또는 '-'를 넣어 등식을 만들며 놀�� www.acmicpc.net 다이나믹 프로그래밍. 중요한 건 시작할 때 (0,0)으로 시작하면 안된다는 점이다. 이럴 경우 4 0 0 0 0 같은 반례에 걸린다. 무조건 첫 값을 지정해줘야한다. /* 1학년 */ #include #include #include #include #define ll long long int using namespace std; void input(); void solve(); int ..
백준 1162 도로포장 https://www.acmicpc.net/problem/1162 1162번: 도로포장 문제 준영이는 매일 서울에서 포천까지 출퇴근을 한다. 하지만 잠이 많은 준영이는 늦잠을 자 포천에 늦게 도착하기 일쑤다. 돈이 많은 준영이는 고민 끝에 K개의 도로를 포장하여 서울에서 포�� www.acmicpc.net 양수 weight의 간선으로 이루어진 그래프에서 한 점으로부터 다른 점까지의 최단거리를 구하는 알고리즘은 다익스트라알고리즘이다. 이 문제는 여기서 한 술 더 뜬다. 내가 원하는 간선의 weight를 0으로 만들 수 있다! 이것만 잘 생각하면 일반적인 다익스트라 문제와 똑같다. N개 중에 K개를 고르는 문제는 어떻게 풀어야할까? N개 중에 K개를 고르는 모든 경우의 수를 구할 수도 있다. 즉 next_p..
백준 1701 Cubeditor https://www.acmicpc.net/problem/1701 1701번: Cubeditor 문제 Cubelover는 프로그래밍 언어 Whitespace의 코딩을 도와주는 언어인 Cubelang을 만들었다. Cubelang을 이용해 코딩을 하다보니, 점점 이 언어에 맞는 새로운 에디터가 필요하게 되었다. 오랜 시간 고�� www.acmicpc.net KMP 알고리즘...? 을 활용하는 문제다. 시작점을 하나씩 옮겨가면서 failed 배열을 채운다 이 failed 배열은 보통 'pi' 로 표현하는 그 배열이다. 이 배열에서 가장 큰 값이, 가장 긴 문자열의 길이라는 걸 활용하면 문제를 풀 수 있다. /* Cubeditor */ #include #include #include #include using ..

티스토리툴바