본문 바로가기
반응형

분류 전체보기1305

[BOJ] 백준 2668 숫자 고르기 출처: https://www.acmicpc.net/problem/2668 Input 7 3 1 1 5 5 4 6 Output 3 1 3 5 윗줄에서 N ~ 0개의 정수를 뽑아서 둘째 줄과 조합되는 경우를 완전 탐색하는 경우는 TLE 발생 DFS 탐색으로 그래프 탐색하듯이 cycle이 형성되는 구간을 찾는 문제입니다. 첫째 줄: [1 2 3 4 5 6 7] 둘째 줄: [2 3 4 2 6 1 7] ① for문으로 각 정점을 출발점으로 DFS 탐색합니다. 이때, 이미 조사가 끝난 구간(visited[])는 그냥 넘어갑니다. ② DFS 탐색에서 cycle 구간을 파악하기 위해서는 chk[] 배열에 표시합니다. 한번의 DFS탐색이 끝났을 때, 표시한 chk[] 값을 다시 해제합니다. ③ chk[]로 DFS 탐색 .. 2021. 2. 17.
[BOJ] 백준 2578 빙고 출처: https://www.acmicpc.net/problem/2578 Input 11 12 2 24 10 16 1 13 3 25 6 20 5 21 17 19 4 8 14 9 22 15 7 23 18 5 10 7 16 2 4 22 8 17 13 3 18 1 6 25 12 19 23 14 21 11 24 9 20 15 Output 15 사회자가 부르는 숫자를 target[] 배열에 저장합니다. 해당 숫자를 한개씩 빙고판에 mark() 표시하며 visited[][] 표시합니다. 방문 표시가 끝나면 표시(mark)된 곳에서 가로줄, 세로줄을 확인합니다. 마크된 곳과 별개로 대각선 두 곳도 각각 5곳이 칠해지지 않았다면 계속 확인합니다. ▶ 가로줄, 세로줄 (+ 대각선 2개)를 확인했을 때, "bingo"가 .. 2021. 2. 17.
[BOJ] 백준 2502 떡 먹는 호랑이 출처: https://www.acmicpc.net/problem/2502 Input 6 41 Output 2 7 만족하는 A, B 조합이 1개 이상일 수 있는 Special judge 유형 문제입니다. 첫번째 날 떡의 개수 = A, 두번째 날 떡의 개수 = B 라고 했을 때, ▶ A → B → A + B → A + 2B → 2A + 3B → 3A + 5B → 5A + 8B → 8A + 13B [B의 관점]: 2번째 항부터 계수의 변화가 1 → 1 → 2 → 3 → 5 → 8 → 13 → ... 로서, 피보나치 수열을 형성합니다. B의 계수가 fibo(n)일 때, A의 계수는 fibo(n-1)에 해당합니다. 문제에서 주어지는 D를 고려하면 B의 계수는 fibo(D-1)이며, A의 계수는 fibo(D-2) .. 2021. 2. 17.
[BOJ] 백준 2621 카드 게임 출처: https://www.acmicpc.net/problem/2621 Input B 3 B 7 R 1 B 2 Y 7 Output 207 주어진 규칙을 모두 구현한 후 각 조건에서 구해지는 점수 중 최대값을 구해주면 됩니다. 카드의 조합을 Poker에 비유하다면 분기조건을 보기 좋게 설계할 수 있습니다 #include inline int max(int A, int B) { if (A > B) return A; return B; } inline int min(int A, int B) { if (A < B) return A; return B; } int color[4], digit[10]; // R B Y G + 1 ~ 9 int maxNum, pair1, pair2, triple, quad; int ma.. 2021. 2. 17.
[BOJ] 백준 10801 카드게임 출처: https://www.acmicpc.net/problem/10801 Input 6 7 5 1 4 10 2 3 8 9 1 10 2 9 4 8 3 7 5 6 Output A 게임 라운드는 총 10번이므로 A[10], B[10] 배열로 숫자를 입력받은 하나씩 비교하면 A와 B가 이긴횟수를 기록합니다. 최종 결과에 따라 A, B, D(비김) 출력 #include int A[10], B[10], aWin, bWin; int main() { // freopen("input.txt", "r", stdin); for (int i = 0; i < 10; ++i) { scanf("%d", A + i); } for (int i = 0; i < 10; ++i) { scanf("%d", B + i); } for (int.. 2021. 2. 17.
[BOJ] 백준 10798 세로읽기 출처: https://www.acmicpc.net/problem/10798 Input ABCDE abcde 01234 FGHIJ fghij Output Aa0FfBb1GgCc2HhDd3IiEe4Jj 문자열을 입력받고 각 문자열의 크기를 info[] 저장합니다. 한 문자열의 최대 길이는 15이므로 각 문자열의 첫번째부터 15번째 위치를 세로로 읽습니다. 이때, 배열 인덱스 접근 시 overflow 방지를 위해서 문자열의 길이보다 큰 위치에 인덱스 접근에 유의합니다. * 문자열의 시작인덱스는 0부터이므로 주의 #include int len(const char *str) { int ret = 0; for (;;) { if (str[ret] == '\0') break; ret++; } return ret; } .. 2021. 2. 17.
[BOJ] 백준 2526 싸이클 출처: https://www.acmicpc.net/problem/2526 Input 67 31 Output 3 연산과정에서 동일한 숫자가 나오는 시점에서 그 이후로는 사이클에 포함되어 있습니다. 『67』 → 『25』 → 『1』 → 『5』 → 『25』가 두 번 나타났으므로 이후로는 사이클이 진행됩니다. 이때, 중복되지 않은 숫자의 개수 = (연산과정에서) 중복된 숫자가 두번째 나타난 순서 - 처음 나타난 순서입니다. 『25』가 중복해서 나타는 순서는 5번째와 2번째 이므로 ▶5 - 2 = 3개 #include const int MAX_N = 1000; int visited[MAX_N]; int num, N, P, ans; int main() { // freopen("input.txt", "r", stdin.. 2021. 2. 17.
[BOJ] 백준 2567 색종이 - 2 출처: https://www.acmicpc.net/problem/2567 Input 4 3 7 5 2 15 7 13 14 Output 96 먼저 색종이가 덮어지는 영역을 『1』 로 표시합니다. ▶둘레를 구하기 위해서 표시한 『1』의 상하좌우를 확인합니다. ①의 경우 오른쪽이 비어져 있으므로 둘레에 해당됩니다. → +1 ②의 경우 상하좌우가 채워져 있으므로 둘레에 해당되지 않습니다. → +0 ③의 경우 아래쪽, 오른쪽이 비어져 있으므로 둘레에 해당됩니다. → +2 #define _CRT_SECURE_NO_WARNINGS #include int N, answer, board[101][101], nextX, nextY; int dx[] = { 0, 0, -1, 1 }; int dy[] = { -1, 1, 0,.. 2021. 2. 17.
[BOJ] 백준 7575 바이러스 출처: https://www.acmicpc.net/problem/7575 Input 3 4 13 10 8 23 93 21 42 52 22 13 1 2 3 4 11 1 3 8 9 21 42 52 22 13 41 42 10 9 21 42 52 13 22 52 42 12 21 Output YES [문제 분석] - 감염된 프로그램의 개수 N (2 ≤ N ≤ 100) - 바이러스 코드 추정을 위한 최소 길이 K (4 ≤ K ≤ 1,000) - 각 프로그램에 대한 정보 i 번째 프로그램의 길이를 나타내는 정수 Mi (10 ≤ Mi ≤ 1,000) Mi 개의 프로그램 코드를 나타내는 양의 정수 정수의 범위는 1 이상 10,000 이하 ▶ [해시] Hash란? [해시] Hash란? Hash란? 원소가 저장되는 위치가 .. 2021. 2. 17.
[BOJ] 백준 10840 구간성분 출처: https://www.acmicpc.net/problem/10840 Input afcdrdesdefwszr gedsrddemzr Output 7 문자열로 구성된 두 서열에서 같은 성분을 가진 구간 중에서 가장 긴 구간을 찾아 그 구간의 길이를 출력하는 문제 ▶ [해시] Hash란? [해시] Hash란? Hash란? 원소가 저장되는 위치가 원소 값에 의해 결정되는 자료구조 - 평균 상수 시간에 삽입, 검색, 삭제가 가능하다. - 매우 빠른 응답을 요구하는 상황에 유용 (Hash는 최소(최대) 원소를 찾는 것 zoosso.tistory.com 구성 성분이 같은 최대 길이를 구하는 것이므로 큰 값부터 작은 값까지 줄여가며 구성성분을 확인 하는 경우에는 TLE 발생 ※ 구성 성분이 같은지 확인하는 방법은.. 2021. 2. 17.
반응형

티스토리툴바