https://www.acmicpc.net/problem/1676 1676번: 팩토리얼 0의 개수 N!에서 뒤에서부터 처음 0이 아닌 숫자가 나올 때까지 0의 개수를 구하는 프로그램을 작성하시오. www.acmicpc.net 1. Preview 시간 복잡도: O(N) 공간 복잡도: O(1) 유형: 수학 2. 초기 접근 방법 N! 값을 계산하고 결과값(처음으로 0이 아닌 숫자가 나올 때까지 0의 개수)을 구하기에는 N!의 값이 너무 커진다. N! 의 값을 구할 때 1의 자리만 남겨줘도 0의 개수를 구할 수 있기 때문에, N! 계산 도중. 10으로 나눠질 경우 바로 나눠주어 zeroCount를 진행해준다. 3. 생각 - 4. 코드 N = int(input()) fact = 1 zeroCount = 0 for..

https://www.acmicpc.net/problem/9466 9466번: 텀 프로젝트 이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 있을 www.acmicpc.net 1. Preview 시간 복잡도: O(N) 공간 복잡도: O(N) 유형: 그래프 탐색, dfs 2. 초기 접근 방법 그래프 탐색을 하면서 자기자신을 만날 때, 즉 사이클이 형성이 되어야 한 팀이다. def dfs(start, x): for k in graph[x]: if not visited[k]: visited[k] = True judge.append(k) dfs(start, k) if visited..

https://www.acmicpc.net/problem/16928 16928번: 뱀과 사다리 게임 첫째 줄에 게임판에 있는 사다리의 수 N(1 ≤ N ≤ 15)과 뱀의 수 M(1 ≤ M ≤ 15)이 주어진다. 둘째 줄부터 N개의 줄에는 사다리의 정보를 의미하는 x, y (x < y)가 주어진다. x번 칸에 도착하면, y번 칸으 www.acmicpc.net 1. Preview 시간 복잡도: O(6*NM), bfs 공간 복잡도: O(NM) 유형: 그래프 탐색, bfs 2. 초기 접근 방법 visited[e] : 사다리 visited[nx] : 일반 주사위 길 2가지 경우 모두 queue에 삽입하여, 해당 경우를 고려해 탐색하게 된다. for s, e in road: if s == nx and not vis..

https://www.acmicpc.net/problem/5015 5015번: ls 첫째 줄에 패턴 P가 주어진다. P는 1글자~100글자이고, 알파벳 소문자와 '.', '*'로만 이루어져 있다. 둘째 줄에는 디렉토리의 파일 개수 N이 주어진다. (1 ≤ N ≤ 100) 다음 N개의 줄에는 디렉토리에 www.acmicpc.net 1. Preview 시간 복잡도: p * n (= 패턴 길이 * 문자열 길이) 공간 복잡도: n 유형 : DP, 문자열(✋ 유형에는 없지만 문자열로 풀었다) 2. 초기 접근 방법 "문자열" 탐색으로 풀었다. '패턴'에 문자 중 '*'은 무엇이든 들어갈 수 있으니 무시하고, 알파벳 문자와 '.' 이 순서대로 있는지 파악했다. 1. 먼저 '*'을 기준으로 패턴을 split 한다. 2..

https://www.acmicpc.net/problem/16724 16724번: 피리 부는 사나이 첫 번째 줄에 지도의 행의 수를 나타내는 N(1 ≤ N ≤ 1,000)과 지도의 열의 수를 나타내는 M(1 ≤ M ≤ 1,000)이 주어진다. 두 번째 줄부터 N개의 줄에 지도의 정보를 나타내는 길이가 M인 문자열이 주 www.acmicpc.net 1. Preview 풀이 시간: 35분 + 30분 시간 복잡도: O(NM) 공간 복잡도: O(NM) 2. 초기 접근 방법 board[][] 에서 모두 방문하는데 "dfs 탐색를 진행한 횟수" 라고 생각해 풀었다. 3 4 DLLL DDDU RRRU 곰곰히 고민해보니, 위와 같은 case에서 dfs 탐색이 3번 일어나지만, 필요한 safezone은 1개이다. 3. ..

https://www.acmicpc.net/problem/9019 9019번: DSLR 네 개의 명령어 D, S, L, R 을 이용하는 간단한 계산기가 있다. 이 계산기에는 레지스터가 하나 있는데, 이 레지스터에는 0 이상 10,000 미만의 십진수를 저장할 수 있다. 각 명령어는 이 레지스터에 www.acmicpc.net 1. Preview 시간 복잡도: O(4*commands) 공간 복잡도: O(commands) 2. 초기 접근 방법 현재 풀이와 똑같이, queue()를 사용해 수행한 연산을 순서에 맞게 처리하여, 최소 연산 커맨드를 찾으려고 했다. 하지만 2가지 간과한 점이 있어 '시간초과'와 '틀렸습니다'를 받았다. 1) visited[num] = T/F (시간초과) 방문한 숫자에 대해서, 이전에..