1. 문제 1987번: 알파벳 (acmicpc.net) 1987번: 알파벳 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으 www.acmicpc.net 2. 풀이1 기본적인 DFS문제긴한디 분명히 맞는데 시간초과에 애먹었다.. from sys import stdin def dfs(x,y,s): global answer for i in range(4): dx = x + d[i][0] dy = y + d[i][1] if dx >= 0 and dx = 0 and dy = 0 and dx = 0 and dy = 0 and dx = 0 and dy = 0 a..
1. 문제 12904번: A와 B (acmicpc.net) 12904번: A와 B 수빈이는 A와 B로만 이루어진 영어 단어가 존재한다는 사실에 놀랐다. 대표적인 예로 AB (Abdominal의 약자), BAA (양의 울음 소리), AA (용암의 종류), ABBA (스웨덴 팝 그룹)이 있다. 이런 사실에 놀란 수 www.acmicpc.net 2. 풀이 S에서 T를 만들려고만 한다면 이 문제가 상당히 어렵다 그냥 왠지 모르지만 어떤 문제든 역으로 시도해볼때 뭔가 보일수도 있다 조금 생각해보면 1) 문자열의 뒤에 A를 추가한다 2) 문자열을 뒤집고 뒤에 B를 추가한다 두 연산만으로 S에서 T가 만들어졌는데 문자열 T가 ABBA인 경우를 생각해보자. ABBA는 이전에 어떤 문자열이었을까? 오직 1가지인 ABB인..
1. 반복문으로 구현하는 세그먼트 트리 세그먼트 트리 기본 버전은 재귀함수로 구현되어 있다 import math def create_segment(A,tree,tree_index,start,end): if start == end: tree[tree_index] = A[start] else: mid = (start+end)//2 create_segment(A,tree,2*tree_index,start,mid) create_segment(A,tree,2*tree_index+1,mid+1,end) tree[tree_index] = tree[2*tree_index] + tree[2*tree_index+1] def query_sum(tree,tree_index,start,end,left,right): if lef..
1. 문제1 13023번: ABCDE (acmicpc.net) 13023번: ABCDE 문제의 조건에 맞는 A, B, C, D, E가 존재하면 1을 없으면 0을 출력한다. www.acmicpc.net 2. 풀이 A는 B의 친구이다 B는 C의 친구이다 C는 D의 친구이다 D는 E의 친구이다 이 말은 무슨말일까? A에서 시작해서 B로 가고, B에서 C로 가고 C에서 D로 가고 D에서 E로 갈 수 있는 경우가 존재하는지 아닌지를 판단하라는 말 주어진 그래프에서 DFS 탐색으로 깊이 4까지 갈 수 있다면 1을 return하면 될 것 깊이가 4이면 1을 return하고.. 깊이가 4가 아니면.. 탐색을 수행 현재 방문하는 점 x에 대한 방문처리 visited[x] = 1 x와 연결된 점 graph[x]에서 순회해..
1. 문제 24463번: 미로 (acmicpc.net) 24463번: 미로 첫 번째 줄에는 미로의 크기 $N, M$이 주어진다. $(3 \le N, M \le 2,001$, $N, M$은 홀수$)$ 두 번째 줄부터는 미로의 정보가 주어진다. 두 번째 줄부터 $N$줄에 거쳐 각 줄에는 길이가 $M$이고 .과 +만으로 이 www.acmicpc.net 입구에서 출구로 가는데, 최단 경로가 아닌 경로는 모두 @로 바꿔서 표시하는 문제 2. DFS 풀이 최단 경로가 아닌 경로를 찾는게 그냥 찾을려하면 생각보다 까다롭다 아이디어의 핵심은 이동할 수 있는 모든 위치 .을 먼저 @로 바꿔놓는다 n,m = map(int,stdin.readline().split()) maze = [list(stdin.readline()...
1. 문제 15712번: 등비수열 (acmicpc.net) 15712번: 등비수열 첫째 줄에 a, r, n, mod가 공백으로 구분되어 주어진다. a, r, n, mod는 모두 1보다 크거나 같고, 109보다 작거나 같은 자연수이다. www.acmicpc.net 초항이 a, 공비가 r, 항 수가 n인 등비수열의 합을 mod로 나눈 나머지를 구하는 간단한 문제 초항이 a이고 공비가 r이며 항 수가 n인 등비수열의 합은.. 공비 r이 1이 아니면, $$S = a \times \frac{r^{n}-1}{r-1}$$ 이라는 아주 쉬운 공식이 있고 이거에 따라 계산해서 mod로 나눈 나머지 구하면 되는거 아니냐 라고 쉽게 생각하면 이 문제는 풀수가 없다 a,r,n이 작으면 상관 없겠지만... 매우 크면 $r^{n..
딥러닝/머신러닝, 통계학, IT프로그래밍, 알고리즘을 좋아하는 사람 https://github.com/yundaehyuck
