꾸준함

문제 링크입니다: https://www.acmicpc.net/problem/1946 그리디(greedy) 알고리즘 문제였습니다. A라는 사람의 서류심사 성적과 면접시험 성적이 B란 사람보다 둘 다 열세라면 채용을 하지 않는다는 것이 문제의 조건이였습니다.따라서, 알고리즘은 아래와 같습니다.1. 신입사원들의 서류심사 성적을 기준으로 오름차순 정렬을 합니다.2. 정렬한 뒤 첫 번째 사원은 서류심사 성적이 일등이므로 무조건 채용을 합니다.3. 첫 번째 사원의 면접시험 성적을 기록하고 두 번째 사원부터 N 번째 사원까지 반복문을 돌리면서 기록한 면접시험 성적보다 우세한 사람을 찾아 채용합니다.4. 3번에서 채용한 사람의 면접시험 성적을 기록하고 3번을 반복합니다. #include #include using na..

문제 링크입니다: https://www.acmicpc.net/problem/15927 비교적 쉬운 문제였지만 어렵게 생각했기 때문에 많이 틀린 문제였습니다.결국 같은 학교 학우인 ssangba55님(blog.naver.com/pasdfq)과 sansan709(degurii.tistory.com)님의 도움 덕분에 풀 수 있었습니다.개인적으로 이 문제는 그리디(Greedy) 알고리즘으로 분류되어야한다고 생각합니다. 알고리즘은 아래와 같습니다.1. 문자열의 양 끝부터 순차적으로 회문 조건을 만족하는지 판별합니다.i) 회문 조건을 만족하지 않는다면 문자열이 팰린드롬(palindrome) 즉, 회문이 아니기 때문에 답은 문자열의 전체 길이입니다.ii) 문자열이 회문이라면 앞에 있는 문자나 뒤에 있는 문자를 제외시..

문제 링크입니다: https://www.acmicpc.net/problem/1914 하노이 탑은 재귀적으로 접근한다면 꽤 쉽게 풀 수 있는 문제입니다. 알고리즘은 아래와 같습니다.(우선, N=3일 때를 설명하겠습니다)1. a, b, c 기둥이 있고 처음에 원판들은 모두 a에 있습니다.2. 첫 번째 원판을 c로 옮깁니다.(현재 상태: (2, 3), 0, (1))3. 두 번째 원판을 b로 옮깁니다.(현재 상태: (3), (2), (1))4. 첫 번째 원판을 b로 옮깁니다.(현재 상태: (3), (1, 2), 0)5. 세 번째 원판을 c로 옮깁니다.(현재 상태: 0, (1, 2), (3))6. 첫 번째 원판을 a로 옮깁니다.(현재 상태: (1), (2), (3))7. 두 번째 원판을 c로 옮깁니다.(현재 상태..

문제 링크입니다: 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..