campkim

https://www.acmicpc.net/problem/1963 1963번: 소수 경로 소수를 유난히도 좋아하는 창영이는 게임 아이디 비밀번호를 4자리 ‘소수’로 정해놓았다. 어느 날 창영이는 친한 친구와 대화를 나누었는데: “이제 슬슬 비번 바꿀 때도 됐잖아” “응 지금 www.acmicpc.net 알고리즘을 너무 안 풀었더니 너무 오랜시간동안 붙잡고 풀었다. 소수판별하는 방법은 은근히 자주 보이는 것 같다. 제대로 숙지할 필요가 있어보인다. 애먹은 부분 문자열에서 특정 인덱스 변경하는 것은 C가 오히려 쉬운 것 같다. list( ) / join( ) 을 사용하는 방법과 slicing을 하는 두가지 방법이 있다. https://pythonexamples.org/python-string-replace-..

이진 탐색 트리(Binary search tree ; 이하 BST)의 개념과 이진 탐색 트리의 일종인 레드블랙 트리(이하 RB트리로 명명)에 대한 설명입니다. 요약하면, RB트리는 BST의 한계를 개선한 트리이며 방대한 데이터를 다룰 때, 성능은 더 우수하고 기능적으로는 동일합니다. 이진탐색트리(BST)는 왜 나왔을까? BST, RBTREE 두 가지 모두 방대한 데이터를 효율적으로 관리하기 위한 자료구조 입니다. 여기서 말하는 관리란 탐색(searching), 수정(insert), 삭제(delete)를 의미하는데, 탐색 기능에는 이진 탐색(Binary Seach)이라는 방법을 사용합니다. 요약하자면, 전체 데이터에서 중앙값 기준으로 찾고자 하는 데이터가 왼쪽인지 오른쪽인지 비교판단을 반복하여 탐색 범위를..

https://www.acmicpc.net/problem/2098 2098번: 외판원 순회 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 16) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j www.acmicpc.net 외판원 순회 문제의 경우 TSP 문제라고, 컴퓨터 과학에서 상당히 오랜 기간, 많은 사람들이 연구해온 분야라고 한다. 문제 내용은 간단하지만 해답을 구하는 과정의 시간복잡도가 상당히 높아서 관련연구가 계속 진행되어 온 것 같다. 연구가 오래된 만큼 아주 다양한 풀이 방법이 있다고 한다. 완전탐색과 순열을 이용한 풀이로 각각 한번씩 풀어봤는데, 이번에 다이나믹 ..

https://www.acmicpc.net/problem/1946 1946번: 신입 사원 첫째 줄에는 테스트 케이스의 개수 T(1 ≤ T ≤ 20)가 주어진다. 각 테스트 케이스의 첫째 줄에 지원자의 숫자 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개 줄에는 각각의 지원자의 서류심사 성 www.acmicpc.net 언제나 최고만을 지향하는 굴지의 대기업 진영 주식회사에 관한 문제다. 이전에 공부했던 정렬개념의 중요성에 대해 일깨워준 문제인 것 같다. 처음에 문제 제출시에는 sort()내장 함수를 사용해서 풀었고, 풀고나서 counting sort(기수정렬)로 다시 풀어봤다. 두가지 풀이에서 시간 차이가 약 3배가까이 났다. 기수 정렬의 경우, 자료의 범위가 한정되어 있을 때, 효율적인 ..

https://www.acmicpc.net/problem/1700 1700번: 멀티탭 스케줄링 기숙사에서 살고 있는 준규는 한 개의 멀티탭을 이용하고 있다. 준규는 키보드, 헤어드라이기, 핸드폰 충전기, 디지털 카메라 충전기 등 여러 개의 전기용품을 사용하면서 어쩔 수 없이 각종 전 www.acmicpc.net 일단 문제에서 요구하는 대로 풀이를 작성한 후, 뭔가 함정이 있을거라고 생각하고 제출했는데 한번에 통과해서 놀랐다. 이 문제가 탐욕법, 그리디 기법이 어떤식으로 사용되었는지는 고찰이 필요해보인다. 문제의 요구사항 멀티탭에 슬롯이 N개 있고, 제한된 수량의 몇 가지 제품을 K번에 걸쳐서 순서대로 사용한다. 제품 종류는 최대 K개이며, 종류가 K보다 적을 경우 중복사용이 가능한듯하다. 이때, 슬롯에 ..

문제가 길고 장황해서 살짝 쫄았지만, 몇 가지 포인트를 고려하니 어렵지 않게 풀리는 문제였다. 노드간 간격이 일정하고 가장 빠른시간을 묻는 문제이기 때문에 BFS풀이가 적합하다. 문제풀이 포인트 고슴도치는 물을 피해서 'D'로 도착해야함. 고슴도치는 한번에 1칸 이동 / ' . ' 으로만 이동 가능 물은 인접한 영역으로 한번에 한칸씩 확장 / 'X', 'D' 일 경우 이동 불가 고슴도치는 물이 이동 예정인 곳으로 이동 불가능 → 큐에 물을 먼저 넣고 그 이후 고슴도치를 넣는다. from collections import deque import sys input=sys.stdin.readline R,C=map(int,input().split()) arr=[list(input().strip()) for _ ..

https://www.acmicpc.net/problem/2294 2294번: 동전 2 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. 가치가 같은 동전이 여러 번 주 www.acmicpc.net 문제 접근 (DFS ? BFS?) 문제가 BFS로 분류되어 있었는데도, 처음에 이 문제를 DFS로 잘 못 접근해서 고집스럽게 풀려고 시도했다.ㅎㅎ 해보면 될 줄 알았다. DFS 접근의 이유는 동전의 개수가 최소인 개수를 찾기 위해서 입력 받은 동전들을 내림 차순으로 정렬한 뒤, 가치가 높은 동전을 우선 탐색하면 빠르게 찾을 수 있다고 생각했기 때문이다. 하지만 문제점..

BFS 기본예제임 이전에 올렸던 BFS 알고리즘 포스팅 내용을 참고하면 좋을 것 같다. BFS는 경로탐색시 가장 적은 개수의 간선을 가지는 방향을 우선적으로 탐색하게 된다. 미로탐색 문제의 경우 인접한 노드간의 거리가 일정하기 때문에 간선이 최소로 목적지에 도착하는 경로가 최단경로가 된다. #BFS from collections import deque N,M=map(int,input().split()) miro=[] miro=[list(map(int,input())) for _ in range(N)] dx=[-1,1,0,0] dy=[0,0,-1,1] def bfs(x,y): queue=deque([[x,y]]) # queue.append([x,y]) while queue: x,y=queue.popleft..

트리의 부모를 찾아주자. 노드(1~N)와 노드들과 연결된 간선들이 주어짐. 이때 1번 노드를 root이라고 할 때, 각 노드의 부모노드를 매칭하는 문제 문제 풀이 포인트 그래프 탐색 이론중 DFS, BFS는 알고리즘상 가장 최근에 탐색한 노드의 인접한 노드를 우선적으로 탐색하는데, 이 특성을 고려하면 특정 노드가 어떤 노드에 의해 탐색이 결정되었는지 알 수 있다. 루트에서 시작하여 BFS 혹은 DFS를 이용하여 탐색을 시작해보자. 새로운 노드가 탐색리스트에 추가 될 때마다, 그 노드가 어떤 노드에 의해 탐색 리스트에 추가되었는지 살펴보자. 이 문제의 경우 노드의 개수가 최대 100,000개까지 가능하다, 루트에서 리프까지 깊이가 깊어질 수 있다는 부분을 고려하면 재귀를 이용한 DFS 풀이는 조금 불리할 ..

대표적인 그래프탐색 알고리즘 DFS, BFS 핵심 요약 및 백준 기본문제풀이. *하기 글에서 노드(node), 정점(vertex)를 혼용해서 사용하는데 동일한 것을 의미함 BFS (Breadth First Search, 너비 우선 탐색) Introduction to algoritm 번역본 중 주어진 그래프 G(V, E)에서 출발절 s에 대해 너비우선검색은 도달가능한 모든 정점을 체계적으로 탐색함. s(시작점)에서 도달할 수 있는 모든 v(정점)에 대해, 너비우선트리의 단순경로는 그래프 G의 s에서 v까지의 최단경로에 해당하고, 이는 가장 적은 개수의 간선을 가지는 경로다. 너비 우선 검색은 발견된 정점과 발견되지 않은 정점 사이에 있는 경계선(frontier)을 균등하게 확장해 나간다는 의미로 이름이 붙..