꾸준함

문제 링크입니다: https://www.acmicpc.net/problem/1120 완전 브루트 포스(Brute Force) 알고리즘으로 접근했다가 틀리고 그리디(Greedy) 알고리즘으로 해결한 문제입니다. 알고리즘은 아래와 같습니다.처음으로 주어진 문자열: s1, 두 번째로 주어진 문자열: s21. 결국 s1의 양 끝에 붙이는 알파벳은 s2와 동일하게 붙이면 됩니다.2. s1은 s2보다 무조건 작거나 같기 때문에 s2의 0 번째 인덱스부터 s1의 시작 지점으로 삼아 같지 않은 인덱스의 수를 셉니다.3. 2에서 구한 결과 중 가장 작은 값을 출력합니다. #include #include #include using namespace std; const int INF = 987654321; string s1..

문제 링크입니다: https://www.acmicpc.net/problem/1377 버블 소트는 한번 진행될 때마다 각 숫자 좌측으로 한칸씩 이동이 가능하다는 원리를 이용해 푸는 문제였습니다.알고리즘은 아래와 같습니다.1. pair형 벡터에 숫자와 인덱스를 저장합니다.2. 숫자를 기준으로 오름차순 정렬을 진행합니다.3. 해당 숫자에 저장되어있는 인덱스와 정렬 기준 인덱스를 뺀 값이 (좌측으로 이동한 횟수 - 1)입니다.4. 3에서 구한 값 중 (최대 + 1)을 출력합니다. #include #include #include using namespace std; int N; int main(void) { ios_base::sync_with_stdio(0); cin.tie(0); //cin 실행속도 향상 cin..

문제 링크입니다: https://www.acmicpc.net/problem/2873 총 3가지 경우의 수를 고려하여 풀어야했던 그리디(Greedy) 알고리즘 문제였습니다. 가로와 세로의 길이가 모두 짝수일 때 풀이는 백준님 슬라이드(https://www.slideshare.net/Baekjoon/baekjoon-online-judge-2873)를 참고하여 풀었습니다. 알고리즘은 아래와 같습니다. 1. 세로가 홀수일 경우 i) 모든 칸을 방문할 수 있습니다. ii) 홀수번 째 행에서는 오른쪽으로 갔다가 내려오고 짝수번 째 행에서는 왼쪽으로 갔다가 내려갑니다. 2. 가로가 홀수일 경우 i) 모든 칸을 방문할 수 있습니다. ii) 홀수번 째 열에서는 아래로 내려갔다가 오른쪽으로 가고 짝수번 째 열에서는 위로 ..

문제 링크입니다: https://www.acmicpc.net/problem/1080 그리디(Greedy) 알고리즘을 적용하여 좌측 상단의 인덱스부터 비교해가며 주어진 행렬에서 결과 행렬로 바뀔 수 있는지 판별하는 문제였습니다. 알고리즘은 아래와 같습니다.1. N과 M이 모두 3 이상일 때만 XOR 연산을 할 수 있기 때문에 N이나 M 중 하나라도 3 미만이라면 서로 같은지만 판별한다.2. N과 M이 모두 3 이상이라면 좌측 상단 부터 해당 인덱스에 있는 값들을 비교하고 만약 서로가 다르다면 XOR 연산을 진행합니다.i) 비교해갈 때 y축은 N-3까지 x축은 M-3까지 for문을 돌립니다.ii) 만약 XOR 연산을 진행하고 난 뒤 결과 행렬과 동일하다면 반복문을 빠져나와 XOR 연산 횟수를 출력합니다.ii..

문제 링크입니다: https://www.acmicpc.net/problem/10610 30의 배수이기 위해서는 다음의 조건을 충족해야합니다.1. 끝의 자리수가 0이여야 합니다.2. 각 자리의 수의 합이 3의 배수여야 합니다. 따라서 위 두 조건을 충족하지 못한다면 -1을 출력해주고 조건을 충족한다면 내림차순으로 숫자를 정렬해주고 출력하면 됩니다! #include #include #include using namespace std; //내림차순 정렬 bool cmp(char a, char b) { if (a > b) return true; return false; } int main(void) { string N; cin >> N; long long sum = 0; bool zero = false; for..

문제 링크입니다: https://www.acmicpc.net/problem/2875 간단한 그리디(Greedy) 알고리즘 문제였습니다. 알고리즘은 아래와 같습니다.1. 대회에 보낼 인원이 없을 경우i) 여자 인원 / 2ii) 남자 인원2. 대회에 보낼 인원이 있을 경우(여자 인원 + 남자 인원 - 대회에 보낼 인원) / 3 위 세 가지 경우 중 최소가 답입니다. #include #include using namespace std; int main(void) { int N, M, K; cin >> N >> M >> K; //K가 없을 경우 두 가지 //K가 있을 경우 cout

문제 링크입니다: https://www.acmicpc.net/problem/14889 브루트 포스(Brute Force) 알고리즘을 DFS(Depth First Search) 알고리즘처럼 적용하여 푸는 문제였습니다. 알고리즘은 아래와 같습니다.1. 각 팀당 N / 2 명의 선수들이 있어야 하므로 start 팀의 팀원이 조건을 충족 못할 경우 팀원을 추가해주고 link 팀의 팀원이 조건을 충족 못할 경우 팀원을 추가해줍니다.2. 1번에서 이상적이게 start팀과 link팀에 N / 2 명의 선수들이 추가되었다면 조건을 충족하였으므로 각 팀의 점수를 합산해서 차를 구한 뒤 현재 최소 점수차와 비교하여 업데이트합니다. #include #include #include using namespace std; con..

문제 링크입니다: https://www.acmicpc.net/problem/1405 DFS(Depth First Search) 알고리즘을 이용하여 모든 경우를 탐색하면 되는 문제였습니다.동서남북으로 갈 확률이 자연수로 주어지기 때문에 0.01을 곱해 확률로 만들어 주는 것과 출력할 때 소수점 10의 자리까지 출력해주는 것만 조심하면 어렵지 않게 풀 수 있는 문제인 것 같습니다. 알고리즘은 아래와 같습니다.1. 한 방향으로 최대 14번 움직일 수 있기 때문에 (15, 15)에서 시작하고 판은 적어도 29*29여야 합니다.2. 한번 움직일 때마다 4방향 다 움직이면서 브루트 포스(Brute Force) 알고리즘을 적용하여 답을 탐색합니다. (다른 방향으로 탐색하기 전에 전 방향에서 밟았던 칸을 다시 밟지 않..

문제 링크입니다: https://www.acmicpc.net/problem/1744 간단한 그리디 문제이지만 벡터를 이용하여 구현하기는 힘든 문제였습니다.벡터에 모든 숫자를 넣고 조건문을 통해 그리디하게 접근하려다가 계속 틀려서 최근에 자주 애용하는 우선순위 큐를 이용하여 풀었습니다. 알고리즘은 아래와 같습니다.1. 1과 곱하면은 손해이기 때문에 1은 무조건 더합니다. 따라서, 1의 개수를 더해줍니다.2. 양수는 내림차순으로 저장하고 음수는 오름차순으로 저장해야 두 수를 곱했을 때 최대가 됩니다.3. 무조건 두 수를 곱한다고 가정하기 때문에 우선순위 큐의 크기가 홀수일 경우 오류가 발생합니다.i) 따라서, 양수가 저장되어있는 우선순위 큐 크기가 홀수이면 1을 넣어줘 짝이 없는 양수를 그대로 더해주게 합니..

문제 링크입니다: https://www.acmicpc.net/problem/11559 BFS(Breadth First Search) 알고리즘을 응용하여 푸는 시뮬레이션 문제였습니다. 알고리즘은 아래와 같습니다.1. 필드를 밑에서부터 위로 하나하나 확인하면서 BFS 알고리즘을 적용하여 4개 이상의 같은 색깔 블록이 상하좌우로 연결되었는지 확인합니다i) 4개 이상의 같은 색깔이 연속되어 붙어있으면 터뜨려야하므로 벡터에 넣습니다.ii) 동시에 터뜨릴 수 있다면 하나의 연쇄라고 생각하기 때문에 모든 색깔의 블럭에 대해 고려해줘야합니다.2. 블록을 터뜨렸다면 블록들의 위치가 바뀌기 때문에 while문을 통해 다시 1번을 진행하고 만약 또 터뜨릴 수 있다면 연쇄를 추가해줍니다.3. 터뜨릴 수 있는 모든 블럭을 터뜨..