본문 바로가기
반응형

PS 문제 풀이/Jungol101

[Jungol] 정올 3115 긴 자릿수 나눗셈 출처: http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=2397&sca=5090 Approach - 나눗셈 연산은 다른 ±, × 연산처럼 각 자리에서 바로 값을 정하기 쉽지 않습니다. - 나눗셈 연산은 뺄셈 연산을 이용해서 구합니다. 즉, 각 자리에서 뺄셈이 가능하면 몫을 1 증가 시키고 해당 수치로 빼다가 불가능해지만 다음 자리로 이동합니다. #include const int LM = 210; int strlen(const char* s, int len = 0){ while (s[len]) len++; return len; } int strcmp(const char* s, const char* t){ while (*s && *s == *t) s+.. 2021. 3. 13.
[Jungol] 정올 2462 키 순서 출처: jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=1723&sca=40 Approach 문제 접근법 및 인접행렬로 구현된 코드는 [BOJ] 2458 키 순서 참고 [BOJ] 백준 2458 키 순서 출처: https://www.acmicpc.net/problem/2458 Input 6 6 1 5 3 4 5 4 4 2 4 6 5 2 Output 1 그래프 관계를 표현 → a가 b보다 작다면 a에서 b로 화살표 표현 Q. 자신의 키 순서를 알 수 있는 방법은 무엇이.. zoosso.tistory.com 연결리스트 이용한 풀이 #define _CRT_SECURE_NO_WARNINGS #include const int LM = 510; struct Node { int d.. 2021. 3. 13.
[Jungol] 정올 3142 ID 검사 출처: [Jungol] 정올 3142 ID 검사 Approach 아래 각 구현시, 사용자가 로그인 여부 / 탈퇴 등에 상태를 Hash로 관리하면 된다. 1. 가입 여부 2. 로그인 여부 3. 회원가입처리: 가입 후 자동 로그인 되지 않음 4. 탈퇴 처리 5. 로그인 처리 6. 로그아웃 처리 ▶ [해시] Hash란? [해시] Hash란? Hash란? 원소가 저장되는 위치가 원소 값에 의해 결정되는 자료구조 - 평균 상수 시간에 삽입, 검색, 삭제가 가능하다. - 매우 빠른 응답을 요구하는 상황에 유용 (Hash는 최소(최대) 원소를 찾는 것 zoosso.tistory.com STL Version #define _CRT_SECURE_NO_WARNINGS #include #include #include usi.. 2021. 3. 13.
[Jungol] 정올 2543 타일 채우기 출처: http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=1804&sca=40 Approach Binary Search (이분 탐색) Binary Search (이분 탐색) Binary Search (이분 탐색) 정렬된 자료에서 목표값을 찾고자 할 때, 사용되는 탐색기법 O(logN) 리스트 중간의 값(mid)을 선택하여 찾고자 하는 값과 비교하는 방식 분할 정복 알고리즘(Divide and Conquer Al zoosso.tistory.com 2 × 2 타일에서 하나의 타일에 홀이 있다면 타일을 채우는 방법은 항상 존재. 마찬가지로, 4 × 4 타일에서 하나의 타일에 홀이 있다면 타일을 채우는 방법은 항상 존재 2k × 2k 타일 에서 하나의 타일.. 2021. 3. 6.
[Jungol] 정올 3517 Tutorial : 이진탐색(Binary Search-이진검색) 출처: http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=2857&sca=30 Approach - 배열의 원소가 정렬되어서 주어지므로 별도로 정렬할 필요가 없습니다. Binary Search (이분 탐색) Binary Search (이분 탐색) Binary Search (이분 탐색) 정렬된 자료에서 목표값을 찾고자 할 때, 사용되는 탐색기법 O(logN) 리스트 중간의 값(mid)을 선택하여 찾고자 하는 값과 비교하는 방식 분할 정복 알고리즘(Divide and Conquer Al zoosso.tistory.com #include #define LM 500005 int N, Q, arr[LM]; void input() { scanf("%d", &N).. 2021. 3. 6.
[Jungol] 정올 1847 월드컵 출처: http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=1114&sca=4030 Approach [BOJ] 6987 월드컵 문제 참고 [BOJ] 백준 6987 월드컵 출처: https://www.acmicpc.net/problem/6987 Input 5 0 0 3 0 2 2 0 3 0 0 5 4 0 1 1 0 4 4 1 0 3 0 2 4 1 0 1 1 3 0 0 5 1 1 3 5 0 0 4 0 1 2 2 1 2 0 3 1 0 4 0 0 5 5 0 0 3 1 1 2 1 2 2 0 3 0 0 5 1 0 4 .. zoosso.tistory.com 승리 횟수: 5 + 3 + 2 + 2 + 0 + 1 = 13 패배 횟수: 0 + 1 + 2 + 3 + 5 +.. 2021. 3. 4.
[Jungol] 정올 1169 주사위 던지기1 출처: http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=449&sca=20 Approach 주사위를 3번 던져서 나올 수 있는 모든 경우의 수 for(int i=1; i 2021. 3. 4.
[Jungol] 정올 1082 화염에서탈출(SLIKAR) 출처: http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=362&sca=50 Approach 동시다발적으로 확장되는 불을 피해서 용사는 집(D)에 도착하여야 합니다. ① 각각의 불이 퍼지는 시간을 timeMap[][]에 저장합니다. ← BFS [Test Case 1] [Test Case 2] - timeMap[][] = 0인 곳은 바위이거나 불이 시작했던 위치 - timeMap[][] = 0이 아닌 숫자는 불이 번지는 시점 ex) timeMap[5][1] = 10초에 해당 지점에 불 존재. ② 용사가 이동할 때 바위가 있는 곳이거나 그 시점에 불이 번지는 곳을 피하며 이동합니다. ← BFS ▶ 즉, 불에 대한 BFS를 먼저 처리한 후, 용사에 대한 .. 2021. 3. 4.
[Jungol] 정올 2606 토마토(초) 출처: Jungol 2606 토마토(초) Approach - 익은 토마토는 1개 이상일 수 있다. - 비어있는 칸 너머에 있는 안 익은 토마토는 익힐 수 없다. - Queue를 이용한 BFS → O(N x M x H) 📌 BFS (Breadth-First Search, 너비 우선 탐색) BFS (Breadth-First Search, 너비 우선 탐색) BFS 그래프 전체를 탐색하되, 인접한 노드들을 차례대로 방문합니다. Queue 이용 * DFS로 풀리는 문제는 일반적으로 BFS로도 풀 수 있습니다. Process ※ 깊이 우선 탐색과는 달리 너비 우선 탐색에서 zoosso.tistory.com #define _CRT_SECURE_NO_WARNINGS #include const int LM = 102; .. 2021. 3. 4.
[Jungol] 정올 1240 제곱근 출처: http://jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=523&sca=30 Approach ① low + high = 1 + 263- 1 = 263으로 long long 범위를 벗어나 Overflow 발생 → unsigned long long 사용 ② mid * mid = 262 * 262 = 2124 이기 때문에 unsigned long long으로도 처리할 수 없습니다. 이런 경우에는 mid 2021. 3. 4.
반응형

티스토리툴바