-

https://www.acmicpc.net/problem/1431 1431번: 시리얼 번호 첫째 줄에 기타의 개수 N이 주어진다. N은 1,000보다 작거나 같다. 둘째 줄부터 N개의 줄에 시리얼 번호가 하나씩 주어진다. 시리얼 번호의 길이는 최대 50이고, 알파벳 대문자 또는 숫자로만 이루어져 있다. 시리얼 번호는 중복되지 않는다. www.acmicpc.net #include #include #include #include using namespace std; struct info { int sum; string str; }; vector v; bool F(info a, info b) { if (a.str.length() != b.str.length()) { return a.str.length() < ..

https://www.acmicpc.net/problem/10814 10814번: 나이순 정렬 온라인 저지에 가입한 사람들의 나이와 이름이 가입한 순서대로 주어진다. 이때, 회원들을 나이가 증가하는 순으로, 나이가 같으면 먼저 가입한 사람이 앞에 오는 순서로 정렬하는 프로그램을 작성하시오. www.acmicpc.net 1. Stable Sort 라고 해서 괜히 무턱대고 병합 정렬 사용했다가는 낭패. 너무 복잡해진다. 2. Stable Sort 가 아닌 Sort 를 사용해서 똑같은 결과를 낼 수 있다. 3. 문제를 잘 읽어야함. 나이순 + 나이가 같으면 가입순이다. 이름 사전순 비교하지 않는다. 첫번째 코드 #define _CRT_SECURE_NO_WARNINGS #include #include #incl..

https://www.acmicpc.net/problem/10825 10825번: 국영수 첫째 줄에 도현이네 반의 학생의 수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 한 줄에 하나씩 각 학생의 이름, 국어, 영어, 수학 점수가 공백으로 구분해 주어진다. 점수는 1보다 크거나 같고, 100보다 작거나 같은 자연수이다. 이름은 알파벳 대소문자로 이루어진 문자열이고, 길이는 10자리를 넘지 않는다. www.acmicpc.net 만약 입력이 "ABC 10 20 30" 으로 들어 온다면? scanf("%s %s %s %s", a, b, c, d) or cin >> a>> b >> c >> d 로 처리 가능! //cout name >> k >> e >> m; v.push_back({ name,a..

https://www.acmicpc.net/problem/11004 11004번: K번째 수 수 N개 A1, A2, ..., AN이 주어진다. A를 오름차순 정렬했을 때, 앞에서부터 K번째 있는 수를 구하는 프로그램을 작성하시오. www.acmicpc.net C++에 sort를 사용하면 된다. 입력이 5,000,000이니 O(nlogn)이면 가능하다고 판단됨. 다만, cout / cin 대신 scanf와 printf 를 사용해야함. 입출력 속도가 차이가 많이 나기에 이것만 바꿔도 시간초과냐 통과냐가 갈림. 해당 문제는 Quick Sort 대신 Quick Selection Sort를 사용하면 O(n)에 해결할 수 있다고함 #include #include #include #include using names..

https://www.acmicpc.net/problem/2573 2573번: 빙산 첫 줄에는 이차원 배열의 행의 개수와 열의 개수를 나타내는 두 정수 N과 M이 한 개의 빈칸을 사이에 두고 주어진다. N과 M은 3 이상 300 이하이다. 그 다음 N개의 줄에는 각 줄마다 배열의 각 행을 나타내는 M개의 정수가 한 개의 빈 칸을 사이에 두고 주어진다. 각 칸에 들어가는 값은 0 이상 10 이하이다. 배열에서 빙산이 차지하는 칸의 개수, 즉, 1 이상의 정수가 들어가는 칸의 개수는 10,000 개 이하이다. 배열의 첫 번째 행과 열, 마지 www.acmicpc.net 핵심 로직은 map 에서 1이상을 가지는 값의 갯수를 저장해두고 사용한다. DFS 순회를 할 때마다 4방향을 조사하여 0의 갯수만큼 차감해주..

처음에 그냥 DFS로만 풀었다가 시간초과가 났다. N이 100정도 되기 때문에 DFS로는 시간 초과가 해결이 안된다. 따라서 DP를 적용하여 풀어야만 한다. DP[x][y] 를 -1로 초기화 해두고, 방문하는 좌표에 0을 넣어 준다.(그래야지 방문했는지 안했는지 알 수 있다.) DP[x][y]는 (x,y)를 지나서 (n,n) 까지 도달 할 수 있는 경로를 저장해준다고 생각하면 된다. 그렇기 때문에 다른 경로를 통해 (x,y)를 다시 방문하였을 때는 더 탐색하지 않고 해당 값만 return 해주면 된다! 그렇게 되면 DP[0][0]에는 (0,0) ~ (n,n) 까지의 경로가 저장되게 된다. 코드: #include using namespace std;typedef long long lld;int N;int ..

단순 무식한 방법이 먹힌듯 하다. map을 초기화 할 때 1이 입력되는 좌표들은 모두 Q에 push ! 큐를 팝하면서 연결되어있는 부분들을 탐색 ! 그 과정에서 집의 수를 세어준다 ! 코드: #include #include #include #include using namespace std; int N;int D[26][26];int visited[26][26]; int px[4] = { 1, 0, -1, 0 }; // down right up leftint py[4] = { 0, 1, 0, -1 };struct pos{int x;int y;};int cnt;int total;queue Q; char tmp[26];void dfs(int x, int y){ if (visited[x][y] == 1) re..

메모리 초과 난 코드. 애초에 모든 점들을 방문하는건 무리! dfs에서 스택을 엄청나게 잡아먹기 때문에 2500 2500 5000 이런 식으로 입력하면 메모리가 날라간다. #include #include //#includeusing namespace std; int map[5001][5001];int visited[5001][5001];int R[5001]; int px[4] = { 1, 0, -1, 0 }; // down right up leftint py[4] = { 0, 1, 0, -1 }; bool flag = false;struct pos{int x;int y;};pos arr[5001];queue Q;int cnt;int index = 0;int N;void F(int xt, int yt, i..