마탁이의 개발 블로그

www.acmicpc.net/problem/10757 10757번: 큰 수 A+B 두 정수 A와 B를 입력받은 다음, A+B를 출력하는 프로그램을 작성하시오. www.acmicpc.net 로직은 간단하게 생각했으나 std::atoi()의 특성을 제대로 이해하지 않고 사용해 시간이 걸렸던 문제 atoi는 char형 포인터를 문자열로 받는데 이때 1 byte의 char만 입력한다면 뒤에 null이 들어가지 않아 값이 다를 경우가 발생할 수 있다. 더보기 #include #include #include // define #define MAX_LEN 10002 int main() { // init std::ios::sync_with_stdio(false); // input char A[MAX_LEN] = { '..

www.acmicpc.net/problem/13458 13458번: 시험 감독 첫째 줄에 시험장의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 각 시험장에 있는 응시자의 수 Ai (1 ≤ Ai ≤ 1,000,000)가 주어진다. 셋째 줄에는 B와 C가 주어진다. (1 ≤ B, C ≤ 1,000,000) www.acmicpc.net 브론즈 2레벨 문제 (삼성역량 테스트 문제에서는 가장 쉬운 난이도...) 총감독관이 없어도 되는지에 대한 의문이 남긴한다. 최대 입력이 1,000,000 으로 주어지기 때문에 long long으로 값을 출력하였다. 코드 더보기 #include #include // size #define INPUT_MAX_SIZE 1000000 // debug #defin..

www.acmicpc.net/problem/11004 11004번: K번째 수 수 N개 A1, A2, ..., AN이 주어진다. A를 오름차순 정렬했을 때, 앞에서부터 K번째 있는 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 단순한 정렬 문제 같지만 채점 시간을 보니 데이터량이 엄청나다. (물론 입력범위도 -10^9 ~ 10^9) 따라서 최소 힙정렬을 이용하기로 생각하고 코드를 구현하였다 채점현황에 보니 algorith 라이브러리에 nth_element(), sort()를 쓰는 것보다 직접 구현해보는 게 도움이 될 것 같다. 코드 더보기 #include #include #include #include // debug #define debug_m 0 // define #define MI..

www.acmicpc.net/problem/1977 1977번: 완전제곱수 M과 N이 주어질 때 M이상 N이하의 자연수 중 완전제곱수인 것을 모두 골라 그 합을 구하고 그 중 최솟값을 찾는 프로그램을 작성하시오. 예를 들어 M=60, N=100인 경우 60이상 100이하의 자연수 중 완 www.acmicpc.net 간단한 수학 문제이다. 백준 MyPage에서 '실패'가 되어있길래 풀었다. math.h 를 사용하면 해결을 쉽게 할 수 있다. 코드 더보기 #include #include #include // size #define INPUT_MAX10000 // macro #define MIN(a,b) (a < b ? a : b) int main() { // 1977 // init std::ios::sync..

www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 동적 프로그램이을 통해 주어진 입력을 1로 만드는 연산의 횟수를 최소화 하는 문제 점화식을 이해할 수 없어 구글링을 통해 풀었음. Top-down 방식과 Bottom-up 방식이 있는데, 먼저 Top-down 으로 해결하였음 Bottom-up 방식을 통해서 상대적으로 메모리를 아낄 수 있는 것을 보인다. (Bottom-up 구현 필요) Top-Down 더보기 #include #include #include // debug #define debug_m 1 // size #define INPUT_MAX10000000 // mac..

www.acmicpc.net/problem/9370 9370번: 미확인 도착지 (취익)B100 요원, 요란한 옷차림을 한 서커스 예술가 한 쌍이 한 도시의 거리들을 이동하고 있다. 너의 임무는 그들이 어디로 가고 있는지 알아내는 것이다. 우리가 알아낸 것은 그들이 s지점에서 www.acmicpc.net 최단 거리, 특정한 목적지를 거치는 조건이 있는 ICPC 문제. 1280ms가 나왔는데, 채점 현황을 보니 매우 빠른 코드들이 있어 알고리즘의 차이점 확인 필요. 나같은 경우 Dijkstra 계산을 7번 하고 있는데 이때문에 속도가 매우 느린 듯. 더보기 1280ms #include #include #include #include #include // max size #define TEST_CASE_MAX..

www.acmicpc.net/problem/1504 1504번: 특정한 최단 경로 첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존 www.acmicpc.net 해당 문제는 최단 경로 문제에서 특정한 정점을 무조건 지나야 한다는 조건을 추가한 문제이다. 물론, 특정한 정점을 지나갈 때에도 최단 거리의 경로를 지날 수 있도록 계산해야 한다. 시작점 -> 특정한 점_1 -> 특정한 점_2 -> 도착점의 최단 경로 계산을 나누어야 한다. 시작점 -> 특정한 점_1 특정한 점_1 -> 특정한 점_2 특정한 점_2 -> 도착점 과 시..

www.acmicpc.net/problem/1753 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1≤V≤20,000, 1≤E≤300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1≤K≤V)가 주어진다. www.acmicpc.net 다익스트라 알고리즘을 사용하여 해결해야하는 문제이다. 다익스트라 알고리즘은 정점 to 정점에 대한 값을 가진 배열을 구성해 풀어도 되지만 우선순위 큐(= 힙 정렬)을 이용하면 더욱 효율적으로 해결된다. std::priority_queue 를 사용하였지만 실제적으론 힙 정렬을 구현할 수 있으면 좋다. 문제를 풀 때, while(!priQue.empty()) 부분에서 Break의 조건을 ..

www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net 미로를 탐험하면서 벽을 부쉈는지에 대한 상태에 대해 알고 있어야 문제를 풀 수 있었다. 이는 visited[MAX_SIZE+1][MAX_SIZE+1][2] 의 형태로 3차원의 인덱스가 0일경우 부순적 없음, 1일경우 부순적 있음으로 생각하여 BFS 코드를 구현하면 된다. 헤더 파일 중 #include 를 써서 INT_MAX를 사용하고 BFS의 반환 값을 min 값으로 변경하며 사용했다...

www.acmicpc.net/problem/1697 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net BFS를 이용하는 간단한 문제 if() 조건문 안의 메모리 초과 오류를 처음에 생각하지 않고 구현하였다가 디버깅 돌리면서 다시 깨닫게되었음 더보기 #include #include // def #define MAX_SIZE 100000 #define PAIR std::pair #define DEBUG_MODE 0 // global bool visisted[MAX_SIZE + 1]; //..