월 15,400원
5개월 할부 시다른 수강생들이 자주 물어보는 질문이 궁금하신가요?
- 미해결파이썬 알고리즘 문제풀이 입문(코딩테스트 대비)
15. 토마토(BFS : Breadth First Search) 질문
첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다.라고 해서 m, n 을 입력 받았는데 왜 틀린지 모르겠습니다.강사님 풀이에서 n, m이라고 받으신 이유도 모르겠습니다....아래 코드에서 제대로 array 받아오는 것 같은데 이유를 틀리는 이유를 모르겠습니다...!강사님이 제공해주신 테스트 케이스는 다 통과하지만 백준에서는 틀리는 이유를 모르겠습니다... 6 4 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 # 받아온 array [0, 0, 0, 0, 0, 0] [0, 0, 0, 0, 0, 0] [0, 0, 0, 0, 0, 0] [0, 0, 0, 0, 0, 1] 8import sys sys.setrecursionlimit(10 ** 6) # sys.stdin=open("in5.txt", "r") def valid_coord(x, y): if 0 <= x < m and 0 <= y < n: return True else: return False def print_array(array): for elem in array: print(elem) def bfs(): while queue: # tmp_len = len(queue) # for _ in range(tmp_len): temp = queue.popleft() temp_dis = dis[temp[0]][temp[1]] for dx, dy in zip(dxs, dys): nx = temp[0] + dx ny = temp[1] + dy # 익지 않은 상태이거나 유효한 좌표일 때 if valid_coord(nx, ny) and arr[nx][ny] == 0: queue.append((nx, ny)) arr[nx][ny] = 1 dis[nx][ny] = temp_dis + 1 if __name__ == '__main__': from collections import deque n, m = map(int, input().split()) arr = [] for _ in range(m): arr.append(list(map(int, input().split()))) dis = [] for _ in range(m): dis.append([0] * n) dxs = (-1, 1, 0, 0) dys = (0, 0, -1, 1) # print_array(arr) # print('----') # print_array(dis) queue = deque() for i in range(m): for j in range(n): if arr[i][j] == 1: queue.append((i, j)) bfs() # print_array(dis) # arr에서 0을 발견하면 flag = False로 설정 flag = True for i in range(m): for j in range(n): if arr[i][j] == 0: flag = False result = 0 if not flag: print(-1) else: result = max(max(dis)) print(result)
- 미해결파이썬 알고리즘 문제풀이 입문(코딩테스트 대비)
문제 2-2
안녕하세요 선생님 열심히 알고리즘 강의 수강하고 있는 학생입니다.다름이 아니라 질문드릴게 있어서 글 쓰게 되었습니다.섹션 2의 2번째 문제에서 for i in range(T): n,s,e,k = map(int,input().split()) a=list(map(int,input().split())) a=a[s-1:e] a.sort() print("#%d %d" %((i+1),a[k-1]))코드를 이렇게 짰습니다. 이렇게 짜면 맞지만, 저 코드중 굵게 표시한 곳을 붙여서 a=a[s-1:e].sort() 라고 붙여쓰면 오류가 납니다.구글링을 해봐도 알 수 없기에 질문 드렸습니다.감사합니다.
- 해결됨파이썬 알고리즘 문제풀이 입문(코딩테스트 대비)
sum == int(total/2)
선생님께서는 sum==(total-sum) 을sum == total // 2로 바꾸면 홀수일 때 문제가 생긴다고 하셨는데만약 sum == int(total / 2)로 코드를 짜도 잘 작동할까요?감사합니다.
- 해결됨파이썬 알고리즘 문제풀이 입문(코딩테스트 대비)
DFS와 For문
DFS, BFS강의를 보고 있는데,왠지 DFS 문제를 다중 for문을 이용해도 되는건지 궁금해서 질문 올립니다.DFS문제를 for문을 이용해서 풀어도 되는건가요?섹션 6의 중복 순열 구하기는 for문도 될 것 같아서 여쭤봅니다
- 미해결파이썬 알고리즘 문제풀이 입문(코딩테스트 대비)
case 2번 질문드립니다.
안녕하세요 선생님 질문드립니다.2번 케이스 인풋이 아래와 같습니다AKDEF5AYKGDHEJAQKWDERTFYPCTFKSBDEAASKGHDEFWOPASFKGHDEF저는 문제를푸니no,yes,no,yes,yes 로 나오는데마지막 WOPASFKGHDEF 이건 yes 아닌가요?정답은no,yes,no,yes,no 여서 2번만 wrong 앤서가 나와서요..문제를 제가 잘못이해한걸까요? 아래는 제코드입니다.import sys from collections import deque sys.stdin = open("in2.txt",'r') need = input() n = int(input()) for i in range(n): plan = input() dq = deque(need) for x in plan: if len(dq) != 0: if dq[0] == x: dq.popleft() if len(dq) == 0: print("#%d YES" %(i+1)) else: print("#%d NO" %(i+1))
- 미해결파이썬 알고리즘 문제풀이 입문(코딩테스트 대비)
이렇게 코드 짜도 되나요?
강사님 항상 감사합니다.아래와 같이 코드 짜도 문제없나요?
- 미해결파이썬 알고리즘 문제풀이 입문(코딩테스트 대비)
이렇게 코드 짜도 되나요?
강사님 안녕하세요. 강의 잘 듣고 있습니다. 감사합니다.세가지 질문이 있습니다.1. 아래와 같이 코드 짜도 되나요?2. 코드가 맞다면, 제가 탐색 알고리즘 원리로 푼게 맞나요?3. 강사님 코드가 더 효율이 높다고 보면 되는건가요? 이정도 차이면 코딩테스트에서 큰건가요?- 제 코드 실행시간: 0.00021576881408691406 - 강사님 코드 시간: 0.00020885467529296875
- 미해결파이썬 알고리즘 문제풀이 입문(코딩테스트 대비)
12. 단지 번호 붙이기(DFS) 코드 질문
import sys sys.setrecursionlimit(10**6) n = int(input()) arr = [] for _ in range(n): temp = input() arr.append([int(num) for num in temp]) dxs, dys = (-1, 1, 0, 0), (0, 0, -1, 1) def valid_coord(x, y): if 0 <= x < n and 0 <= y < n: return True else: return False # 1인 부분을 전부 탐색한 후 다 탐색하면 True를 return하는 함수 def dfs(x, y): global cnt if arr[x][y] == 0: return False if arr[x][y] == 1: arr[x][y] = 0 cnt += 1 for dx, dy in zip(dxs, dys): nx = x + dx ny = y + dy if valid_coord(nx, ny): dfs(nx, ny) return True return False cnt_arr = [] # arr[0][0] = 0 # 이 것이 문제 for i in range(n): for j in range(n): cnt = 0 if dfs(i, j): cnt_arr.append(cnt) print(len(cnt_arr)) cnt_arr.sort() for elem in cnt_arr: print(elem) 질문 1.정답은 똑같이 나오는데 위의 문제와 똑같은 문제인https://www.acmicpc.net/problem/2667위의 문제는 위의 코드로 통과가 되지 않습니다..ㅠㅠ계속 고민해봤지만 왜 그런지는 모르겠습니다 선생님--> 해결 되었습니다. arr[0][0] = 0 # 이 것이 문제 2번 질문또한, 아래 강사님 풀이의 DFS 함수는 return 조건이 없는데 이럴 경우, 어떻게 함수가 탈출을 하는지 이해가 안갑니다...보통 재귀 문제에서는 return 조건을 통해서 탈출을 하던데아래 문제에는 return이 없어서 혼동이 옵니다... def DFS(x, y): global cnt cnt+=1 board[x][y]=0 for i in range(4): xx=x+dx[i] yy=y+dy[i] if 0<=xx<n and 0<=yy<n and board[xx][yy]==1: DFS(xx, yy) 아래는 전체 코드 입니다.import sys sys.stdin=open("input.txt", "r") dx=[-1, 0, 1, 0] dy=[0, 1, 0, -1] def DFS(x, y): global cnt cnt+=1 board[x][y]=0 for i in range(4): xx=x+dx[i] yy=y+dy[i] if 0<=xx<n and 0<=yy<n and board[xx][yy]==1: DFS(xx, yy) if __name__=="__main__": n=int(input()) board=[list(map(int, input())) for _ in range(n)] res=[] for i in range(n): for j in range(n): if board[i][j]==1: cnt=0 DFS(i, j) res.append(cnt) print(len(res)) res.sort() for x in res: print(x)
- 미해결파이썬 알고리즘 문제풀이 입문(코딩테스트 대비)
이 코드도 괜찮나요?
강사님 안녕하세요. 강의 잘 듣고있습니다. 감사합니다. 맥 환경이라 정답이 맞는지 모르겠네요.. 이렇게 코드 짜도 되나요?혼자서 풀면 풀리긴하는데.. 뭔가 알고리즘적 사고라기 보다는, 생각나는대로 풀기도하고, 강사님 코드보다 대부분 다 길어서.. 잘 공부하고 있는건지 모르겠습니다..
- 미해결파이썬 알고리즘 문제풀이 입문(코딩테스트 대비)
reverse 함수 관련 질문드립니다
n = int(input()) a = input().split() def reverse(x): x = str(x) return int(x[::-1]) def isPrime(x): for i in range(2, x+1): if x==i: return True elif x%i==0: return False for i in a: if isPrime(reverse(i)): print(reverse(i), end=" ")위처럼 슬라이싱으로 reverse함수를 작성해도 괜찮을까요?
- 미해결파이썬 알고리즘 문제풀이 입문(코딩테스트 대비)
이분검색 while문 조건
안녕하세요 강사님 수업을 듣다가 궁금한 점이 생겨서 질문드립니다.while문의 조건이 lt<=rt: 인데 lt>rt가 되는 경우는 탐색이 완료되는 동안에는 없을것같아서 while문의 조건을 true로 하고 실행 시켜봤는데 채점프로그램을 돌려보면 오류가 발생합니다.true가 아니라 lt<=rt를 써야되는 이유가 어떤 상황일까요
- 미해결파이썬 알고리즘 문제풀이 입문(코딩테스트 대비)
증가 수열 만들기 ( deque 사용 ) 코드 질문
전 시간에 deque 구조를 배워서한번 이용해봤습니다 처음에 맨왼쪽과 맨오른쪽 비교하여 제일 작은 값을 구하고 (tmp) 1부터n까지의 수열이니까 제가 구한값 tmp 에 1씩 증가시켜 n까지 반복 코드의 효율성면에서 문제될 것이 있을까요?
- 미해결파이썬 알고리즘 문제풀이 입문(코딩테스트 대비)
options - configure idle 이 없습니다 ㅠ
새로 실행할때 마다 나오는 저장문구를 없애고 싶은데 강의 대로 options 을 눌러도 configure IDLE이 나오지 않습니다
- 미해결파이썬 알고리즘 문제풀이 입문(코딩테스트 대비)
최소힙 문제를 이분정렬로 풀어보았습니다. 코드 조언 부탁드릴게요!
from collections import deque List = [] List = deque(List) List2 = [] while(True): x = int(input()) if x != 0 and x != -1: m = 0 n = len(List) -1 answer = len(List) if List: while(m <=n): if x <= List[(m+n)//2]: answer = (m+n)//2 n = (m+n)//2 -1 else: m = (m+n)//2 + 1 List.insert(answer, x) else: List.append(x) elif x == 0: if len(List) == 0: List.append(-1) else: List2.append(List.popleft()) else: break for _ in List2: print(_)정답 출력을 위해 List2 로 정답들을 담았고pop 시간을 줄이기 위해 deque를 썼습니다.이렇게 풀어도 괜찮을까요?
- 미해결파이썬 알고리즘 문제풀이 입문(코딩테스트 대비)
교육과정설계 질문 드립니다
import sys from collections import deque sys.stdin = open("input.txt", 'r') e = input() n = int(input()) for i in range(1,n+1): cur = deque(input()) cnt = 0 idx = 0 while cur and idx <len(e): cur_pop = cur.popleft() if cur_pop == e[idx]: cnt += 1 idx += 1 if cnt == len(e): print("#%d YES" %i) else: print("#%d NO" %i)이렇게 코드 작성했더니 다른 case에 대해서는 다 맞지만 case2에 대해서 틀린 답이 나옵니다.어디가 잘못된 걸까요?
- 미해결파이썬 알고리즘 문제풀이 입문(코딩테스트 대비)
동전교환 효율성
안녕하세요동전교환문제에서 저는 부분집합을 만들고 계산은 마지막에 하는 방식으로 풀어봤습니다.효율성 방식에서 상태트리로 쭉 나가는 강사님 방식이랑 비교하면 뭐가 더 나은가요?def DFS(L): money= m global minn cnt=0 if L==n: #계산은 여기서 for i in range(0,n): if ch[i]==1: cnt+=(money//p[i]) money%=p[i] if cnt<minn and money==0: minn=cnt else: # 깊이탐색해서 경우의 수 만들기 ch[L]=0 DFS(L+1) ch[L]=1 DFS(L+1)
- 해결됨파이썬 알고리즘 문제풀이 입문(코딩테스트 대비)
gcd 최대공약수
안녕하세요 선생님정보 올림피아드같은 대회에서는 gcd같은 함수를 사용할 수 있을까요?만약 최대공약수를 구하는 문제가 나온다면gcd를 이용해서 풀어도 되는건가요? 아니면 최대공약수를 구하는 코드를 작성해야 하나요? 그리고, 혹시 파이썬 내장함수 math의 gcd 함수가 작동되는 원리를 알고계신가요?? 감사합니다.
- 해결됨파이썬 알고리즘 문제풀이 입문(코딩테스트 대비)
이항계수
안녕하세요 선생님 https://www.acmicpc.net/problem/11050제가 이항 계수1 이라는 문제를 풀고 있는데, 이항 계수가 뭔지 잘 모르겠어서 질문 올립니다.이항정리에 대해서 검색도 해보았는데,를 어떻게 구해야 할까요?감사합니다.
- 미해결파이썬 알고리즘 문제풀이 입문(코딩테스트 대비)
약수K, 시간 복잡도
요렇게 하면 시간 복잡도를 줄일 수 있을 것 같아욤. def input_function(line_string: str): n, k = map(int, line_string.split(' ')) half_value: float = n ** 0.5 temp_results: list[int] = [] for value in range(1, int(half_value) + 1): if n % value == 0: temp_results.append(value) final_results: list[int] = [] for i in temp_results: final_results.append(i) for i in temp_results[::-1]: final_results.append( 6 // i) if k > len(final_results): return -1 return final_results[k-1]
- 미해결파이썬 알고리즘 문제풀이 입문(코딩테스트 대비)
exit_code1 오류코드
안녕하세요후위연산 채점 프로그램을 돌리면 exit_code1 오류코드가 나옵니다. 이 오류가 뭔지 알 수 있을까요?직접 int1~5까지 돌려을때는 정답 일치 하는데 프로그램 돌리면 exit_code1가 뜹니다.그나마 의심가는게 eval같은데 혹시 eval함수는 사용하면 안되나요?코드 첨부합니다. import sys #채점할떄는 주석 #sys.stdin=open('코딩테스트\input.txt','rt') n=sys.stdin.readline() stack=[] for i in n: if i.isdigit(): stack.append(int(i)) elif not i.isdigit(): b=stack.pop() a=stack.pop() stack.append(eval(f'{a}{i}{b}')) print(stack[0])