본문 바로가기

전체보기

 (168)
백준 10868 최솟값 https://www.acmicpc.net/problem/10868 10868번: 최솟값 N(1 ≤ N ≤ 100,000)개의 정수들이 있을 때, a번째 정수부터 b번째 정수까지 중에서 제일 작은 정수를 찾는 것은 어려운 일이 아니다. 하지만 이와 같은 a, b의 쌍이 M(1 ≤ M ≤ 100,000)개 주어졌을 때는 www.acmicpc.net 세그먼트 트리를 활용하는 문제다. 문제를 읽다보면 대놓고 세그먼트 트리를 활용하라는 것 같다... /* 최솟값 */ #include #include #include #include using namespace std; void solve(); int seg_init(int s, int e, int node); int seg_find(int s, int e, in..
백준 2104 부분배열 고르기 https://www.acmicpc.net/problem/2104 2104번: 부분배열 고르기 문제 크기가 N(1≤N≤100,000)인 1차원 배열 A[1], …, A[N]이 있다. 어떤 i, j(1≤i≤j≤N)에 대한 점수는, (A[i]+…+A[j])×Min{A[i], …, A[j]}가 된다. 즉, i부터 j까지의 합에다가 i부터 j까지의 최솟값을 곱한 �� www.acmicpc.net 세그먼트 트리를 활용한 문제다. 그냥 재귀를 활용할 수도 있지만 만약 가장 작은 수가 배열의 양 끝일 경우 O(N^2)가 되기 때문에 시간초과에 걸린다. 그리고 자료형도 신경써야한다. pair를 활용한 세그먼트 트리로 해결했다 /* 부분 배열 고르기 */ #include #include #include #include ..
CODE: 하드웨어와 소프트웨어에 숨어있는 언어, 찰스 펫졸드 재밌게 읽었다. 아주 원시적인 수준의 신호부터 --> 이진법 --> 트랜지스터 --> 메모리 --> OS 등을 거쳐서 마지막엔 데이터 전송에 대해서도 간단히 다룬다. 이 광활한 영역을 관통한다는 점이 참 흥미로운데 그 만큼 책이 두껍다. 토비의 스프링처럼 교과서에 비하면 두껍지않지만 교양서로 읽기 얇은 편은 아니다. 더군다나 교양서와 교과서 사이에 위치한 듯한 내용도 심심치않게 등장하기 때문에 마냥 속편하게 보기 쉬운 책은 아니다. 하지만 이 책을 다 읽으면 하드웨어에 대한 간략한 감이 생긴다. 그만큼 찬사를 받고 있기도 하다. 특히 컴퓨터공학 비전공자는 이런 로우레벨 지식을 접하기가 쉽지않다. 교과서는 너무 어려워서 독학이 힘들고 교양서는 너무 쉬워서 별 도움이 되지않는 경우가 많기 때문이다. 그 중간..
백준 2014 소수의 곱 https://www.acmicpc.net/problem/2014 2014번: 소수의 곱 첫째 줄에 K(1 ≤ K ≤ 100), N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 K개의 소수가 오름차순으로 주어진다. 같은 소수가 여러 번 주어지는 경우는 없으며, 주어지는 소수는 모두 541보다 작거나 �� www.acmicpc.net 우선순위 큐를 이용하는 문제다. 코드는 간단하다 아이디어도 간단하다. 자료형 실수만 하지 않으면 금방 풀 수 있을 것 같다. /* 소수의 곱 */ #include #include #include #include #include #define INTMAX 2147483647 using namespace std; int n_of_decimal, target; int d..
백준 10159 저울 https://www.acmicpc.net/problem/10159 10159번: 저울 첫 줄에는 물건의 개수 N 이 주어지고, 둘째 줄에는 미리 측정된 물건 쌍의 개수 M이 주어진다. 단, 5 ≤ N ≤ 100 이고, 0 ≤ M ≤ 2,000이다. 다음 M개의 줄에 미리 측정된 비교 결과가 한 줄에 하나씩 www.acmicpc.net 백준의 '여행 가자'라는 문제랑 흡사하다. 이 문제도 두 가지 버전으로 풀 수 있다. 첫 번째가 BFS, 두 번째가 플로이드 와샬 이다. 우선 BFS부터 살펴보자. 이 그래프는 단방향 그래프이고 양방향이 절대 될 수 없을 뿐더러 사이클도 생길 수 없기 때문에 트리구조다. 그래서 한 정점에서 BFS를 돌릴 때 접근되는 모든 점은 시작 정점보다 가볍다. 이 때 주의할 건 'A..
백준 1976 여행가자 https://www.acmicpc.net/problem/1976 1976번: 여행 가자 동혁이는 친구들과 함께 여행을 가려고 한다. 한국에는 도시가 N개 있고 임의의 두 도시 사이에 길이 있을 수도, 없을 수도 있다. 동혁이의 여행 일정이 주어졌을 때, 이 여행 경로가 가능한 것인 www.acmicpc.net 여행가고싶다... 이 문제는 두 가지 방법으로 풀 수 있다. 첫번째는 BFS, 두번쨰는 Union-Find이다 두 코드 다 수록했다. BFS로 푸는 건 각 정점간의 연결관계를 확인하는 방법이다. 예를 들어서 A - B, B - C가 연결되어 있을 때 A를 시작점으로 BFS를 돌리면 당연히 C까지 연결된다. A를 시작으로 하는 BFS를 돌리면서 도착하는 정점마다 A와 연결되어있다고 표시해두면 문제를..
백준 15684 사다리 조작 https://www.acmicpc.net/problem/15684 15684번: 사다리 조작 사다리 게임은 N개의 세로선과 M개의 가로선으로 이루어져 있다. 인접한 세로선 사이에는 가로선을 놓을 수 있는데, 각각의 세로선마다 가로선을 놓을 수 있는 위치의 개수는 H이고, 모든 세로선 www.acmicpc.net 구현을 하면 되는데... 그 구현이... 너무 빡세다.... 가능한 모든 케이스를 대입하면 된다. 즉, 일일이 사다리를 넣어보고 주어진 조건을 만족하는 지 체크한다(이걸 무한반복...) /* 사다리 조작 */ #include #include #include using namespace std; void input(); void solve(); int N, M, H; bool ghost_leg[3..
백준 1981 배열에서 이동 https://www.acmicpc.net/problem/1981 1981번: 배열에서 이동 문제 n×n짜리의 배열이 하나 있다. 이 배열의 (1, 1)에서 (n, n)까지 이동하려고 한다. 이동할 때는 상, 하, 좌, 우의 네 인접한 칸으로만 이동할 수 있다. 이와 같이 이동하다 보면, 배열에서 몇 개의 www.acmicpc.net 이분탐색과 BFS(혹은 DFS)를 활용한 문제. 이분탐색은 '가능한 최대'라거나 '가능한 최소' 등의 키워드에 맞춰 사용하면 될 것 같다. /* 배열에서 이동 */ #include #include #include #include using namespace std; int n, small, large; int map[100 + 1][100 + 1]; bool is_visit..
백준 2629 양팔 저울 https://www.acmicpc.net/problem/2629 2629번: 양팔저울 첫째 줄에는 추의 개수가 자연수로 주어진다. 추의 개수는 30 이하이다. 둘째 줄에는 추의 무게들이 자연수로 가벼운 것부터 차례로 주어진다. 같은 무게의 추가 여러 개 있을 수도 있다. 추의 무 www.acmicpc.net 백 트랙킹과 DP를 활용하는 문제다. 적은 N과 상대적으로 널럴한 시간 제한을 보자마자 백트랙킹 감이 오긴했으나... 아직 recursion 알고리즘을 짜는 게 미흡한 것 같다. 이렇게 ''완전탐색''을 하면 반드시 풀 수 있는 문제를 백트랙킹과 DP로 구현할때는 각 케이스에서 발생 가능한 모든 사례를 Recursion으로 처리하는 연습을 해야겠다. ㅠㅠ /* 양팔 저울 */ #include #in..
백준 1613 역사 https://www.acmicpc.net/problem/1613 1613번: 역사 첫째 줄에 첫 줄에 사건의 개수 n(400 이하의 자연수)과 알고 있는 사건의 전후 관계의 개수 k(50,000 이하의 자연수)가 주어진다. 다음 k줄에는 전후 관계를 알고 있는 두 사건의 번호가 주어진다. �� www.acmicpc.net 플로이드 워셜 알고리즘을 활용하는 문제다. N이 400밖에 안되므로 O(N^3)을 해도 6400만이라서 시간초과에 걸리지 않는다. /* 역사 */ #include #define MAX_N 400 + 1 #define MAX_EDGE 50000 + 1 using namespace std; int n, k, s; int order[MAX_N][MAX_N]; int main(void) { ..

티스토리툴바