본문 바로가기
반응형

전체 글1307

[BOJ] 백준 21611 마법사 상어와 블리자드 삼성 SW 코딩 테스트 준비(A형) 삼성 SW 기출 모음 출처: https://www.acmicpc.net/problem/21611 Approach 2021년 상반기 2번 문제로 구현 + 시뮬레이션 유형입니다. 개인적으로는 오전/오후 문제 4개 중에서 상대적으로 난이도가 높은 문제였던것 같습니다. 정해진 T/O나 응시자 평균을 비교해봐야 겠지만 1, 2번 문제를 모두 푸는것이 쉽지 않을 것 같습니다. 👀 문제를 복원/각색하면서 이해하기 어려운건지, 아니면 해석능력이 부족한건지... 다른 문제와 달리 내용 이해하기 위해서 2~3번 그림을 비교해가며 읽어야 했습니다. 😂 ① d 방향으로 거리가 s 이하인 모든 칸의 구슬 파괴 파괴된 칸은 빈 칸이 된다. (블리자드 마법) ② 구슬이 파괴된 후에는 빈 칸이 생.. 2021. 5. 24.
[BOJ] 백준 21609 상어 중학교 삼성 SW 코딩 테스트 준비(A형) 삼성 SW 기출 모음 출처: https://www.acmicpc.net/problem/21609 Approach 2021 상반기 2번 문제로 BFS 유형 문제이다. ▶ BFS (Breadth-First Search, 너비 우선 탐색) BFS (Breadth-First Search, 너비 우선 탐색) BFS 그래프 전체를 탐색하되, 인접한 노드들을 차례대로 방문합니다. Queue 이용 * DFS로 풀리는 문제는 일반적으로 BFS로도 풀 수 있습니다. Process ※ 깊이 우선 탐색과는 달리 너비 우선 탐색에서 zoosso.tistory.com 문제에서 요구하는 아래 사항을 구현하면 된다. ① 크기가 가장 큰 블록 그룹을 찾는다. 그러한 블록 그룹이 여러개이면 포함된 무.. 2021. 5. 23.
[VS] Visual Studio에서 input.txt로 입력받도록 설정하기 Visual Studio에서 input.txt로 입력받도록 설정하기 알고리즘 문제를 풀다보면 Input Data를 입력받고 특정 Logic을 수행하고 출력한다. ▶ freopen( )을 이용한 파일 입출력 freopen( )을 이용한 파일 입출력 알고리즘 문제를 풀다보면 주어진 Input Data를 입력받아 Logic을 수행한 후 정해진 Output Data를 출력한다. scanf()나 cin 으로 표준 입출력 하는 경우에는 계속해서 Copy & Paste해야 하는 번거로움이 있다. zoosso.tistory.com 코드에 아래 문구로도 "input.txt" 파일에서 입력을 받을 수 있지만 freopen("input.txt", "r", stdin); 코드 제출할 때는 해당 부분을 주석처리해야 하는 번거로.. 2021. 5. 23.
[SWEA] 10763 조 신나 출처: SWEA Approach 문제 설명은 풀이에 비해 복잡한데, 🤦‍♂️ i 번째 인덱스의 배열 값을 입력받을 때, 입력값이 i와 동일하지 않으면 ans 변수가 올라간다. 소수점 6번째 자리까지 출력하기 위해 float 타입으로 캐스팅하였다. #include int N, val, ans, TC; int main(void) { // freopen("input.txt", "r", stdin); scanf("%d", &TC); for (int tc = 1; tc 2021. 5. 23.
[SWEA] 1849 영준이의 무게측정 출처: SWEA Approach Disjoint-Set & Union-Find Disjoint-Set & Union-Find Disjoint-Set, 상호 배타적 집합 서로 중복되지 않는 부분 집합들을 의미 (교집합 존재 X) Union-Find Disjoint-Set을 표현할 때 사용하는 알고리즘. ex) 여러 노드가 존재할 때, 두 개의 노드를 선택해서 두 zoosso.tistory.com #include const int MAX_N = 1e6 + 2; char cmd; int N, M, TC, a, b, w; int parent[MAX_N], rank[MAX_N], W[MAX_N]; int Find(int n) { if (parent[n] == n) return n; W[n] += W[parent[.. 2021. 5. 23.
[SWEA] 1843 영준이의 숫자 고르기 출처: SWEA Approach bit 연산을 이용해서 자료를 재배치하는 문제이다. - 배열 index N은 가장 큰수(마지막수)가 N인 경우의 수이다. - 전체가 다 들어오고 나서 셈하는 것이 아닌 들어 올때마다 갱신된다. ▶ 비트마스크 (Bitmask) 비트마스크 (Bitmask) 비트마스크 정수의 이진수 표현(Bit)을 자료 구조로 쓰는 기법 현대의 모든 CPU는 이진수를 이용해도 모든 자fy 표현 내부적으로 이진수를 사용하는 컴퓨터들은 이진법 관련 연산들을 아주 빨리 zoosso.tistory.com #include #define LL long long const int MOD = 1000000007; const int MAX_N = 1e5; int N, S, TC, srr[MAX_N + 1]; .. 2021. 5. 23.
[BOJ] 백준 21608 상어 초등학교 삼성 SW 코딩 테스트 준비(A형) 삼성 SW 기출 모음 출처: https://www.acmicpc.net/problem/21608 Approach BFS + 완전탐색을 구현하는 문제이다. ▶ BFS (Breadth-First Search, 너비 우선 탐색) BFS (Breadth-First Search, 너비 우선 탐색) BFS 그래프 전체를 탐색하되, 인접한 노드들을 차례대로 방문합니다. Queue 이용 * DFS로 풀리는 문제는 일반적으로 BFS로도 풀 수 있습니다. Process ※ 깊이 우선 탐색과는 달리 너비 우선 탐색에서 zoosso.tistory.com ① N * N 명의 친구들을 입력받은 순서대로 배치한다. ② 문제에서 주어진 우선순위에 따라 map[][]에 배치한다. → isBetter.. 2021. 5. 23.
[BOJ] 백준 10759 팰린드롬 경로 3 출처: https://www.acmicpc.net/problem/10759 Approach DP[][] = 문자열이 팰린드롬인 경우의 수 ▶ 동적계획법(Dynamic Programming, DP) 동적계획법(Dynamic Programming, DP) 동적 계획법(Dynamic Programming)은 큰 의미에서 분할 정복과 같은 접근 방식을 의미한다. 처음 주어진 문제를 더 작은 문제들로 나눈 뒤 각 조각의 답을 계산하고, 이 답들로부터 원래 문제에 대한 zoosso.tistory.com #include #define LL long long const int MAX_N = 500 + 2; const int MOD = 1000000007; inline LL add(LL A, LL B) { return .. 2021. 5. 22.
[SWEA] 4534 트리 흑백 색칠 출처: SWEA Approach 메모제이션을 이용해서 풀 수 있는 문제이다. DP[Color][Node] = Node에서 Color를 가질 때, 가질 수 있는 최대 색칠 방법 수 - DP[흰색][node] = DP[검은색][next] + DP[흰색][next] - DP[검은색][node] = DP[흰색][next] 변수 계산에서 int 범위를 벗어나기 때문에 long long 타입이 필요하고 MOD로 나머지 연산(%) 처리해야 한다. ▶ 동적계획법(Dynamic Programming, DP) 동적계획법(Dynamic Programming, DP) 동적 계획법(Dynamic Programming)은 큰 의미에서 분할 정복과 같은 접근 방식을 의미한다. 처음 주어진 문제를 더 작은 문제들로 나눈 뒤 각 조각.. 2021. 5. 22.
동적계획법(Dynamic Programming, DP) 동적 계획법(Dynamic Programming)은 큰 의미에서 분할 정복과 같은 접근 방식을 의미한다. 처음 주어진 문제를 더 작은 문제들로 나눈 뒤 각 조각의 답을 계산하고, 이 답들로부터 원래 문제에 대한 답을 계산해 내기 때문이다. 동적 계획법과 분할 정복의 차이가 발생하는 부분은 문제를 나누는 방식이다. 동적 계획법(DP)은 다른 알고리즘과 함께 이용해서 문제를 풀어야 하는 경우가 있다. 특정 Case를 여러번 계산하는 대신 한 번만 계산하고 계산 결과를 재활용하여 속도를 높이다. 그러기 위해 각 문제의 답을 메모리에 저장해 둘 필요가 있다. → DP[ ][ ] ▶ 연속된 부분 합(연속합) - 1 (완전 탐색) ▶ 연속된 부분 합(연속합) - 2 (Prefix Sum) ▶ 연속된 부분 합(연속합.. 2021. 5. 22.
반응형

티스토리툴바