글 읽기 - 파이썬 또 질문드려요ㅜㅜ

algoshipda 8년 전 0

아직 파이썬을 잘 모르는데요. 오답 뜰 이유가 없는거 같은데 자꾸 오답처리가 되네요. 어디가 잘못 됐을까요..

---------------------------------------

혹시 리스트와 인트변수의 스코핑룰이 다른가요?

M이 값이 원래 100입니다. dfs 함수안에서 M=5라고 하고 print cnt 전에 print M 해봤더니 원래값인 10가 출력됐습니다.

그런데 dfs 함수안에서 bat[x][y]=0 했을땐 밑에서 출력해보면 0으로 출력됐습니다.

주소를 바꾸는건지 값을 바꾸는건지의 차이 같기도 하고.. 잘 모르겠네요 ㅜㅜ

---------------------------------------

다른분 소스에서 큐를 리스트로 구현한걸 봤는데 이게 단순히 큐의 push연산은 리스트의 끝에 원소를 추가하고

pop연산은 리스트의 0번 인덱스 원소를 제거하는 식이였습니다. c++의 vector를 써도 이런게 가능하겠지만

굉장히 비효율적이잖아요. 검색해보니깐 저런식의 큐 구현이 자주 쓰이는거 같은데 파이썬의 리스트는 내부구현이

어떻게 되있는건가요?

---------------------------------------

혹시 파이썬 for문에서 c나 c++의 for(i = 0; i<n; i*=3) 처럼 변수를 곱하기로 증가시키며 반복하는게 가능한가요?

bat = []
dx = [0,1,0,-1]
dy = [1,0,-1,0]
M = N = K = 0
def dfs(x,y):
	bat[x][y]=0;
	for k in range(4):
		i = x + dx[k]
		j = y + dy[k]
		if(i>=M or i<0 or j>=N or j<0):continue
		if(bat[i][j]==1):
			dfs(i,j)
	return

for t in range(input()):
 	(M,N,K)= map(int, raw_input().split())
	cnt = 0
	bat = [[0 for j in range(N+1)] for i in range(M+1)]
	for i in range(K):
		(a,b) = map(int, raw_input().split())
		bat[a][b] = 1
		
	for i in range(M):
		for j in range(N):
			if(bat[i][j]==1):
				dfs(i,j)
				cnt = cnt + 1
	print cnt

1.
딱히 알고리즘에 큰 문제는 없긴 한데... recursion depth 문제일 가능성이큽니다.
배추로 가득찬 50*50짜리 밭일 경우 재귀 깊이가 2500이 될텐데, 파이썬은 재귀가 대충 1000을 넘어가면 런타임에러를 내며 뻗어버립니다.
sys.setrecursionlimit(n) 으로 깊이를 재설정할수 있긴 합니다만, 이런 한계 때문에 저는 웬만하면 재귀를 안쓰려고 노력하고있습니다.

2.
제가 질문을 잘 이해할수가 없습니다. 이건 다른분이 잘 설명해 주시리라 믿고 넘기겠습니다(...)

3.
일단 제가 q.pop(0)을 즐겨쓰는건 queue를 import하는것보다 코드가 짧아서 사용하고있었습니다.
생각난대로 timeit으로 테스트해봤는데 그냥 리스트를 이용하는게 더 빠릅니다.
제 컴퓨터만 이런걸까 해서 온라인저지의 코딩을 이용해봤더니(이경우엔 import timeit을 이용할 수 없으니 각각 for문을 이용해서 테스트하고, 수행시간을 비교했습니다) 여전히 queue 모듈을 사용하는게 더 느리더군요.

4.
파이썬의 for문은 (반복자가 구현된)순회가능한 객체에 차례대로 접근하는거라서 일반적인 방법으로는 힘듭니다.
아무튼 몇가지 방법을 생각해보자면....

1) while 문 이용
증감식이 맨 아랫줄에 들어가야 하기때문에 읽기가 영 불편합니다.

2) 리스트 내포
log값에 1을 더해야 하기 때문에 이거 까먹고 실수하기 쉽습니다.

3) 반복자를 직접 구현
귀찮습니다

이리저리 고민하면 다른 방법도 있겠습니다만, 딱히 쉬운길은 없어보입니다.

# 리스트, Queue의 비교
import timeit
print(timeit.timeit('q+=[1];q.pop(0)',setup='q=[]',number=10**5))  #0.14371540954330975
print(timeit.timeit('q.put(1);q.get()',setup='import queue;q=queue.Queue()',number=10**5))  #1.9744283995186522
 
#while문
i=1
while i<n:
    print(i)
    i*=3
     
#리스트 내포
from math import log
n=10
for i in [1*(3**k)for k in range(int(log(n,3))+1)]:
    print(i)
     
#반복자
class MultipleIter:
    def __init__(self,n,m):
        self.i=1
        self.n=n
        self.m=m
    def __iter__(self):
        return self
    def __next__(self):
        temp=self.i
        self.i*=self.m
        if temp<self.n:
            return temp
        else:
            raise StopIteration
 
for i in MultipleIter(10,3):
    print(i)

algoshipda 8년 전 0

으어 엄청 복잡하네요. 감사합니다!

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

파이썬 또 질문드려요ㅜㅜ

algoshipda 8년 전 0

skygarlics 8년 전 2

algoshipda 8년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말