꾸준함

문제 링크입니다: https://koitp.org/problem/SDS_TEST_CLOCK/read/ 같은 학교 학우인 sansan709(degurii.tistory.com)님의 도움으로 풀 수 있었던 문제였습니다.XOR 연산을 이용하여 간단하게 풀 수 있는 문제였는데 아직 비트 연산에 익숙치 않은 저에게는 구현이 상당히 까다로웠던 문제였습니다. 알고리즘은 아래와 같습니다.1. 0 ~ 9까지 세그먼트들을 이차원 배열에 미리 저장합니다.2. 7개의 세그먼트들로 구성된 숫자 4개를 입력받고 해당 숫자들로 시간을 표현할 수 있으면 우선 해당 시간을 구합니다.3. 세그먼트들은 최대 2번 고칠 수 있습니다.i) 따라서, XOR 연산을 통해 하나의 세그먼트를 고친 뒤 시간을 표현할 수 있으면 해당 시간을 구하는데 ..

문제 링크입니다: https://koitp.org/problem/SDS_TEST_CALCULATOR/read/ 힙을 이용해야지만 시간 내에 AC를 받을 수 있는 정렬 알고리즘 문제였습니다. 알고리즘은 아래와 같습니다.1. 최소 힙을 구성하는 우선순위 큐를 선언해주고 숫자들을 우선순위 큐에 넣어줍니다.2. 최소 힙에서 두 개의 숫자 즉, 최소 숫자와 두 번째로 작은 숫자를 꺼내서 더해줍니다.3. 2번의 연산 결과를 합에 더해주고, 2번의 연산 결과를 우선순위 큐에 넣어줍니다.4. 2~3번을 우선순위 큐 크기가 1이 될 때까지 반복해줍니다. #include #include #include #include #include using namespace std; int N; int main(void) { ios_..

문제 링크입니다: https://koitp.org/problem/SDS_TEST_BIGINT/read/ 그리디(greedy) 알고리즘 문제였습니다. 알고리즘은 아래와 같습니다.1. 첫 번째 숫자는 고정이지만 두 번째 숫자부터는 원하는대로 배치가 가능하기 때문에 오름차순 정렬을 해줍니다.2. 작은 숫자부터 뺄셈을 해주면 가장 큰 수가 나오기 때문에 오름차순 정렬한 숫자들을 M만큼 뺄셈을 진행해주고 나머지는 더해주면 됩니다. #include #include #include using namespace std; int N, P, M; int main(void) { ios_base::sync_with_stdio(0); cin.tie(0); int test_case; cin >> test_case; for (in..

문제 링크입니다: https://koitp.org/problem/SDS_TEST_TREASURE/read/ 전형적인 BFS(Breadth First Search) 알고리즘 문제였습니다.시작점과 도착점이 정해져 있고 단방향 그래프이기 때문에 BFS 알고리즘을 돌리고 도착점에 도달했을 때 제한시간 내 도착하면 경과시간을 반환하고 제한시간을 초과했다면 -1을 반환해주면 되는 문제였습니다. #include #include #include #include #include using namespace std; const int MAX = 1000 + 1; int N, M, K; vector graph[MAX]; //전형적인 BFS int BFS(int nodeNum, int cnt) { queue q; bool v..

문제 링크입니다: https://koitp.org/problem/SDS_TEST_PAGE/read/ 등차 수열을 생각해보면 쉬운 문제였습니다. 알고리즘은 아래와 같습니다.1. J = 0인 경우, 모든 페이지를 확인해야하지만 시작 페이지 이상인 페이지들만 셉니다.2. J > 0인 경우, 시작 페이지 이상이고 N 이하인 페이지들만 셉니다.i) 입력 받은 페이지가 등차 수열에 포함되는 숫자인지 확인합니다.ii) (입력 받은 페이지 - 시작 페이지)가 등차(J+1)로 나누어 떨어진다면 i)가 성립합니다. #include using namespace std; const int MAX = 1000; int N, S, J, K; int main(void) { ios_base::sync_with_stdio(0); ci..

문제 링크입니다: https://koitp.org/problem/SDS_TEST_SURVIVOR/read/ 간단한 브루트 포스(Brute Force) 문제였습니다. 알고리즘은 아래와 같습니다.1. 반복문을 통해 모든 인덱스를 통해 8 방향 중 범위 초과가 아닌 인덱스만 확인합니다.2. 1번에서 확인한 인덱스들이 불모지가 없고 초원, 산, 물이 모두 있다면 도시를 세울 수 있습니다. *문제는 마치 8 방향을 모두 확인할 수 있는 땅만 확인하라는 식으로 적혀 있지만 실제로는 그냥 범위 초과가 아닌 인덱스를 확인하는 것을 요구하기 때문에 모든 땅을 확인해야합니다. #include using namespace std; const int MAX = 10; typedef struct { int y, x; }Dir;..

문제 링크입니다: https://koitp.org/problem/SDS_TEST_CONSULTING/read/ A 난이도였음에도 불구하고 정답률이 2%일 정도로 구현하기 난해했던 문제였습니다.저도 펭로그(http://penglog.tistory.com/2)님 덕분에 풀 수 있었습니다. 알고리즘은 다음과 같습니다.1. 전화 상담을 진행할 때 최소 고객 수와 최대 고객 수를 파악합니다.i)최소 고객 수는 모든 고객을 순차적으로 원하는 상담시간만큼 상담해줄 경우입니다.ii)최대 고객 수는 모든 고객을 K분 즉, 최소 상담시간만큼 상담해줄 경우입니다.2. 최소 고객 수 ~ 최대 고객 수만큼 반복문을 돌립니다.3. 2번을 진행하는데 우선 현재 고객 수만큼 10점을 곱해주고 최소 상담 시간인 K분만큼은 상담해줬을테..

문제 링크입니다: https://koitp.org/problem/SDS_TEST_SPACE/read/ 별도의 알고리즘을 요구하지 않는 쉬운 문제였습니다. 총 9가지의 경우를 고려해줘야합니다.1. S에서 E로 바로 가는 경우2. S의 x 좌표가 0을 지나 M-1로 가는 경우3. S의 x 좌표가 M-1을 지나 0으로 가는 경우4. S의 y 좌표가 0을 지나 N-1로 가는 경우5. S의 y 좌표가 N-1을 지나 0으로 가는 경우6. 2번 + 4번7. 2번 + 5번8. 3번 + 4번9. 3번 + 5번 #include #include using namespace std; int main(void) { ios_base::sync_with_stdio(0); cin.tie(0); //cin 속도 향상 int test_..

문제 링크입니다: 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로 옮깁니다.(현재 상태..