본문 바로가기
반응형

PS 문제 풀이/Jungol101

[Jungol] 정올 2601 종이접기 출처: http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=1862&sca=50 Approach 주어지는 접는 횟수 n에 대해서 출력되는 모양 규칙을 파악해야 한다. (n = 1) ∨ (n = 2) ∧∨∨ (n = 3) ∧∧∨∨∧∨∨ (n = 4) ∧∧∨∧∧∨∨∨∧∧∨∨∧∨∨ 현재 문자열의 길이 = len 일 때, n이 증가할 때 다음 문자열의 길이는 {2 × len + 1} 이다. 이때, 기존 문자열에서 중간 '∨'이 삽입되고 중간을 기준으로 뒤쪽에 있는 글자가 뒤집혀서 앞쪽에 배치되는 형태 입니다. * 설명을 위해서 문자 변경 v ^vv ^^vv^vv ^^v^^vvv^^vv^vv n이 증가할 때, 기존 문자열 구성과 길이를 이용해서 앞에 붙여지는 .. 2021. 7. 21.
[Jungol] 정올 2586 자동분무기(중) 출처: http://www.hancom.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=1847&sca=5090 Approach Input 30 30 30 31 30 29 30 31 30 30 30 31 30 29 30 31 30 29 29 30 29 29 29 30 29 30 30 31 30 29 30 31 30 30 30 31 30 29 30 31 30 32 32 32 32 31 32 32 32 30 30 31 30 29 30 31 30 30 30 31 30 29 30 31 30 Output . . . . . . . . . . . . . . . . . . . . - . . . . . . . . . . . . . . . . . . . . . + . . . + . ... 2021. 5. 16.
[Jungol] 정올 2223 블랙홀 출처: http://jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=1484&sca=9040 Approach 벨만-포드 (Bellman-Ford) 알고리즘을 이용할 수 있다. 벨만-포드 (Bellman-Ford) 개념 가중 유향 그래프에서 최단 경로를 구하는 알고리즘입니다. 벨만 포드 알고리즘은 동작원리는 다익스트라(Dijkstra)와 유사합니다. 차이점은 벨만 포드는 음수 가중치가 존재하는 경우에도 zoosso.tistory.com #include const int LM = 505; int N, M, B, dist[LM]; struct Data { int s, e, t; }A[LM * 12]; int acnt; void input() { scanf("%d %d %d.. 2021. 4. 3.
[Jungol] 정올 1863 종교 출처: http://jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=1136&sca=4050 Approach Disjoint-Set & Union-Find Disjoint-Set & Union-Find Disjoint-Set, 상호 배타적 집합 서로 중복되지 않는 부분 집합들을 의미 (교집합 존재 X) Union-Find Disjoint-Set을 표현할 때 사용하는 알고리즘. ex) 여러 노드가 존재할 때, 두 개의 노드를 선택해서 두 zoosso.tistory.com #include const int LM = 50005; int N, M, group[LM], ans; int find(int n) { if (group[n] == n) return n; group[n].. 2021. 4. 2.
[Jungol] 정올 1516 단어세기 출처: http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=788&sca=20 Approach 해당 문제에서는 문장의 앞, 뒤에 필요 없는 공백 문자를 포함하지 않는 데이터가 Input으로 주어지며 단어와 단어 사이에도 하나의 공백만이 있다. 하지만 '임의의 문장'은 맨 앞, 맨 뒤에 공백이 한 개 이상 포함될 수 있습니다. ▶ " leading space multiple space tailing space " #include #include #include #include using namespace std; int main() { string s, w; while (getline(cin, s) && s!= "END") { map dic; for (.. 2021. 3. 18.
[Jungol] 정올 1264 마법색종이 출처: http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=547&sca=99 Approach - 사각형을 시작점(sx, sy), 끝점(ex, ey), 색(color)로 정의 - 현재 사각형 내부에 또 다른 사각형이 없는 사각형을 '단말 사각형' 그렇지 않은 경우 '일반 사각형'으로 정의 - 새로운 점이 단말 노드 사각형에 포함되는 경우 단말 사각형은 두 개의 단말 사각형을 만들면서 사각형의 색이 바뀐다. 그리고 자신은 일반 사각형이 된다. → 이진 트리 생성 및 탐색 ※ 편향 이진 트리가 형성되는 경우 최악의 시간 복잡도를 가질 수 있다. 높이는 N이므로, 시간복잡도 O(N × N) 또한 완성된 트리에서 단말 노드 중 사각형 면적의 최대값 최소값을 .. 2021. 3. 18.
[Jungol] 정올 4320 이진탐색 트리 (binary search tree) 2 출처: jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=3670&sca=99&page=29 Approach now 노드 삭제 ① child 노드가 존재하지 않는다면 단순히 삭제 ② child 노드가 1개인 경우 → now 자리를 child가 대신한다. ③ child가 lch, rch 두 개인 경우 Left/Right Sub Tree 중 에서 now와 가까운 숫자(target node)를 찾아야 합니다. 즉, Left Sub Tree에서 가장 큰 숫자 혹은 Right Sub Tree에서 가장 작은 숫자가 해당됩니다. ※ 여기서 대체되는 target 노드를 후임자(successor)라고 합니다. ※ 이진탐색트리 정의를 생각하면 child가 2개인 노드는 반드시 그 서브 .. 2021. 3. 18.
[Jungol] 정올 1880 암호풀기(Message Decowding) 출처: http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=1153&sca=9040 Approach 복호화 키는 공백을 포함하지 않으나 암호문은 공백을 포함하고 있다. → 에 포함된 fgets(문자열 이름, 문자열 길이, 입력 스트림) 하지만 fgets()는 개행문자('\r', '\n')도 입력한다는 점에 유의해야 한다. 윈도우의 개행문자('\r\n')와 리눅스의 개행문자('\n')가 다르기에 가령, 윈도우에서 만든 파일을 리눅스에 읽는 경우 두 개의 개행문자가 읽히는 문제가 발생 그렇기에 문자열 길이를 구할 때, 개행문자('\r', '\n')을 제거하여 구할 수 있다. int strlen(char *s, int len = 0){ while(*s &&.. 2021. 3. 18.
[Jungol] 정올 1133 UNIQUENESS2 출처: http://jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=413&sca=99 Approach - 중복없이 이름을 저장하기 위해서 Hash 구현 (+ Chaining 기법) - Hash에 자료저장시 문자열 주소와 고유 ID를 저장합니다. - 문자열의 등장하는 순서를 별도의 연결리스트로 관리합니다. ① Hash에 등록된 이름이 없다면 Hash에 새롭게 추가합니다. (문자열 비교) + 새로운 ID를 부여합니다. (ID는 1번부터 순차적으로 부여) ② 기존에 이름의 ID 혹은 새롭게 부여된 ID를 이용해서 나타난 순서를 리스트에 추가합니다. (head 다음 지점에 추가합니다.) ③ ID가 N번째까지 부여된 경우는 입력받은 이름에서 중복이 없는 것을 의미하므로 "u.. 2021. 3. 18.
[Jungol] 정올 3699 변장 출처: http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=3048&sca=2050 Approach 의상 이름은 유일하다고 했으므로 같은 옷이 두 번이상 입력되지 않습니다. 따라서 부류 이름이 몇 번 등장했는지만 세면됩니다. (의상 이름 입력할 필요가 없음) A라는 부류에 속한 의상의 개수가 K개라면 A부류의 의상을 입는 경우의 수는 몇 가지일까? → K + 1 (입지 않는 것도 1가지 경우) 따라서 등장한 모든 부류들의 경우의 수를 곱한 결과에서 한 가지(옷을 하나도 입지 않는 경우)를 뺀 결과가 답이 된다. #include int tc, N, ans; int cnt, eachCnt[33]; char name[33][22]; int strcmp(co.. 2021. 3. 18.
반응형

티스토리툴바