코딩 대장

문제 풀이

 에라토스테네스의 체를 활용하여 소수를 구했습니다.

(https://ko.wikipedia.org/wiki/%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98_%EC%B2%B4)

코드

제출 결과

문제 출처

https://www.acmicpc.net/problem/1978

문제 해설

 자료형을 연습하기 좋은 문제라고 생각이 들어 가져오게 되었습니다. 유의해야 할 점은 총 두 가지로 반올림과 최빈값 구하기입니다.

 반올림 같은 경우, 양수와 음수일 때를 고려하여 양수일 때는 0.5를 더해준 값을 int형으로 변환시켜 저장해 주었고 음수일 때는 0.5를 빼준 값을 int형으로 변환시켜 저장하였습니다. 최빈값의 경우, 우선 가장 빈도수가 높을 때 빈도가 몇인지 구하여 같은 빈도가 있는지 확인해 주었습니다.

코드

제출 결과

문제 출처

https://www.acmicpc.net/problem/2108

문제 풀이

 게임의 규칙을 찾아야 풀이가 가능한 문제입니다. 게임의 규칙은 다음과 같습니다.

1. 같은 곳을 두 번 뒤집으면 결과가 같으므로 이러한 경우는 고려하지 않아도 됩니다.

2. N은 짝수이므로,

2-1) (x, y)의 돌 (=노란색 별) 을 뒤집으면 자기 자신과 가로줄, 세로줄의 돌 색이 바뀌게 되므로 노란색 별 기준 주변의 검은색 돌 갯수는 홀수개가 됩니다.

2-2) 초록색 별 기준 바뀌는 돌의 색은 자기 자신과 자기 자신이 속한 한 줄이 되므로 검은 돌의 갯수는 짝수개가 됩니다.

2-3) 자기 자신의 색이 바뀌지 않는 빨간색 별 기준 바뀌는 돌의 색은 가로 줄 한 개, 세로 줄 한 개이므로 검은 돌의 갯수는 홀수개가 됩니다.

(+ 흰 색 돌을 기준으로 보는 경우 뒤집은 돌의 주변 흰색 돌만 짝수개가 됩니다.)

3. 즉, 가로줄의 검은 돌 갯수와 세로 줄의 검은 돌 갯수를 합한 것이 홀수라면, 뒤집은 돌이 됩니다. (중복 제외)

(+ cin, cout으로 받으면 시간 초과납니다ㅠㅠ)

코드

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52

#include <iostream>   using namespace std;   int main() {       ios_base::sync_with_stdio(false);     cin.tie(NULL);     cout.tie(NULL);          int t;     cin >> t;       for (int tc = 1; tc <= t; tc++)     {         int ans = 0;         char board[1000][1000];         int h[1000] = { 0, };         int v[1000] = { 0, };           int n;         cin >> n;           for (int i = 0; i < n; i++)         {             for (int j = 0; j < n; j++)             {                 cin >> board[i][j];                 if (board[i][j] == 'B')                 {                     h[i]++;                     v[j]++;                 }             }         }           for (int i = 0; i < n; i++)         {             for (int j = 0; j < n; j++)             {                 int x = h[i] + v[j];                 if (board[i][j] == 'B')                     x -= 1;                   if (x % 2 != 0)                     ans++;             }         }         cout << '#' << tc << ' ' << ans << '\n';     }     return 0; } http://colorscripter.com/info#e" target="_blank" style="color:#e5e5e5; text-decoration:none">Colored by Color Scripter

 

 

제출 결과

 

문제 출처

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWefzFeq5P8DFAUh&categoryId=AWefzFeq5P8DFAUh&categoryType=CODE

문제 풀이

 bfs 알고리즘을 활용하여 방문하지 않은 길을 따라 도착점이 나올 때까지 탐색하였습니다.

코드

제출 결과

문제 출처

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV14vXUqAGMCFAYD&categoryId=AV14vXUqAGMCFAYD&categoryType=CODE&&&

문제 풀이

 다양한 방법으로 풀이가 가능한 문제로 저는 포인터를 역 방향으로 참조하여 문제를 풀었습니다.

코드

제출 결과

문제 출처

https://www.acmicpc.net/problem/1427

문제 해설

 단순한 정렬 문제입니다. 버블 소트를 활용하여 풀이하였습니다.

코드

문제 출처

https://www.acmicpc.net/problem/2750

풀이 과정

 arr에 map을 입력 받고, 시작점인 (0, 0)부터 탐색을 시작합니다. 해당 칸까지 이동하였을 때, 걸린 최소 비용을 dist 배열에 저장해 줍니다. dist 배열은 매우 큰 수로 초기값을 정해 줍니다. 

 간단한 예를 들어, dist에 파란색 경로의 최소 비용이 저장되어 있을 때, 주황색 경로의 최소 비용이 더 작은 경우 dist에 저장된 값을 주황색 경로의 값으로 갱신하여 줍니다. 따라서 탐색이 종료되면, dist[n-1][n-1]에는 (n-1, n-1)까지 가는 최소 비용이 저장되어 있게 됩니다.

코드

제출 결과

문제 출처

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV15QRX6APsCFAYD&categoryId=AV15QRX6APsCFAYD&categoryType=CODE&&&

문제 풀이

 이 문제는 단순히 구현을 했을 때는 시간 초과가 나게 됩니다. 따라서 x를 고정시켜 주고, 이 x에 따라 나올 수 있는 y를 찾아가면서 문제를 풀어야 합니다.

 예를 들어, 10 12 3 9의 경우 3이 x의 자리에 올 때 y의 자리에 올 수 있는 값은 3, 1, 11, 9, ... 이며 이 때 각각 10년의 텀을 두고 발생하게 됩니다. 따라서 답은 3년에 3*10을 더한 33년이 됩니다. 주의할 점은 % 연산의 경우 0부터 시작하기 때문에 이를 고려하여 코드를 구성해야 합니다.

 만약 가장 처음에 y 자리에 왔던 값이 다시 나타나게 된다면, 이는 한 주기를 모두 지났다는 뜻이 되므로 종말 년도를 넘어섰다는 뜻이 됩니다. 따라서 -1을 출력합니다.

 또는 최소 공배수와 최대 공약수를 활용하여 종말 년도를 먼저 계산하고, 이를 넘어서는 경우를 찾아주는 것도 가능합니다.

코드

제출 결과

문제 출처

https://www.acmicpc.net/problem/6064