Sad Puppy 3 개발자 아지트 :: 개발자 아지트

https://www.acmicpc.net/problem/1620

문제 해결 방법

 

딕셔너리를 잘 활용하여 문제를 해결한다. 

 

코드 구현

정답 코드 

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
dic = {}
revDic = {}
for i in range(n):
    tmpS = input().strip()
    dic[i+1]=tmpS
    revDic[tmpS]=i+1

for i in range(m):
    tmpV = input().strip()
    if tmpV.isdigit():
        tmpV= int(tmpV)
        print(dic[tmpV])
    else:
        print(revDic[tmpV])

 

시간/공간 복잡도

O(n)

 

어려웠던 점

  • 자료구조 조회할 때, 시간초과를 해결하기 위해서는 리스트보다 해시테이블을 구조인 딕셔너리 사용(O(1)) 이 더 빠르기 때문에 효과적이다.  

알게된 점

  • 키 값을 통해 값을 찾거나 밸류 값을 통해 값을 찾아야 하는 경우, 두개의 딕셔너리를 활용하면 아주 효율적이다. 
  • 문자열이 숫자 값인지 확인할때, 대상.isdigit()함수를 사용하면 확인할 수 있다. (숫자일 경우 True 반환)

'코딩테스트 > 문제 풀이 - Python' 카테고리의 다른 글

[백준1003] 피보나치 함수  (0) 2024.09.09
[백준11723] 집합  (0) 2024.09.09
[백준1012] 유기농 배추  (0) 2024.09.09
[백준1926] 그림  (0) 2024.08.26
[백준9252] LCS 2  (0) 2024.08.14

https://www.acmicpc.net/problem/1003

 

문제 해결 방법

재귀함수 혹은 DP를 활용한다. 

코드 구현

정답 코드 

import sys
input = sys.stdin.readline
t = int(input())


def fibonacci(n, count):
    if n<=1:
        if n ==0:
            count[0]+=1
        if n==1:
            count[1]+=1

        print(count[0], count[1])
        return n
    
    a = 0
    b = 1

    for i in range(2, n+1):
        c = a + b
        a = b
        b = c


    print(a, b)
    return b 
        

for i in range(t):
    n = int(input())
    count = [0, 0]
    fibonacci(n, count)

# 0 1 1 2 3 5 8

 

시간/공간 복잡도

O(n)

 

최적화 및 개선

  • 피보나치 함수 알고리즘을 구현할 때, 재귀함수로 구현후 시간 초과가 나면 DP로 구현하면 시간 복잡도를 줄일 수 있다. 

 

'코딩테스트 > 문제 풀이 - Python' 카테고리의 다른 글

[백준1620] 나는야 포켓몬 마스터 이다솜  (0) 2024.09.09
[백준11723] 집합  (0) 2024.09.09
[백준1012] 유기농 배추  (0) 2024.09.09
[백준1926] 그림  (0) 2024.08.26
[백준9252] LCS 2  (0) 2024.08.14

https://www.acmicpc.net/problem/11723

문제 해결 방법

리스트를 잘 활용하여 문제를 해결한다. 

 

코드 구현

정답 코드 

 

import sys
input = sys.stdin.readline

n = int(input())
tmp = []
for i in range(n):
    entire = input().strip()
    if entire=='all': 
        tmp = list(range(1, 21))
    elif entire=='empty':
        tmp.clear()
    else:
        s, v = entire.split()
        v = int(v)
        if s == 'add':
            if v not in tmp:
                tmp.append(v)
        
        if s == 'check':
            if int(v) in tmp:
                print(1)
            else:
                print(0)
        
        if s == 'remove':
            if v in tmp:
                tmp.remove(v)
        
        if s == 'toggle':
            if int(v) in tmp:
                tmp.remove(v)
            else:
                tmp.append(v)

 

시간/공간 복잡도

O(n)

 

어려웠던 점

  • 입력값의 타입에 대해 잘 고려하지 않아서 조건문이 제대로 실행되지 않았던 점
  • sys모듈에서 input()함수를 사용할 때, 개행문자(/n)가 붙어서 조건문이 제대로 실행되지 않았던 점

 

느낀점

  • sys모듈에서 input()함수를 사용할 때, 개행문자(/n)를 꼭 처리하여 문제를 해결해야겠다. 
  • 변수 타입에 대해 잘 고려하고 문제를 풀어야겠다. 
  • 리스트를 비우기 위해 대상.cleare() 함수를 사용하면 된다. 

'코딩테스트 > 문제 풀이 - Python' 카테고리의 다른 글

[백준1620] 나는야 포켓몬 마스터 이다솜  (0) 2024.09.09
[백준1003] 피보나치 함수  (0) 2024.09.09
[백준1012] 유기농 배추  (0) 2024.09.09
[백준1926] 그림  (0) 2024.08.26
[백준9252] LCS 2  (0) 2024.08.14

https://www.acmicpc.net/problem/1012

 

문제 해결 방법

 

배추가 심긴 위치를 순회한다. 방문여부를 알 수 있는 visited 배열이 필요하다. 

좌표를 순회할때 1을 만나고, 방문한 적이 없으면 bfs함수를 실행한다. 

이때, deque를 활용해 큐를 만들고 큐에 bfs함수를 실행할 당시의 좌표값을 넣어준다. 이때 지렁이의 개수를 +1 한다 

bfs함수에서는 큐에서 값을 꺼내어 방문처리를 해주고, 자신의 자리에서 심겨진배추가 이어져 있다는 판단 기준인 위, 아래, 양옆을 조회 한다. 이때, 새로 조회하는 위치가 그림 정보가 적힌 좌표의 범위를 벗어나서도 안되고, 이미 방문 한 적이 있어도 안된다. 또한 0이여도 안된다. 값이 0이 아니고 방문한 적이 없으면 현재자리의 방문체크를 해준다.  

 

그림 정보 순회가 모두 끝나면 임의의 리스트의 원소의 개수와 원소의 최대값을 출력한다. 

 

코드 구현

정답 코드 

import sys
from collections import deque
input=sys.stdin.readline

dx= [0, 0, 1, -1]
dy= [1, -1, 0, 0]

answer=[]
def bfs(y, x):
        queue = deque()
        visited[y][x] = True
        queue.append([y, x])

        while queue:
            ny, nx = queue.popleft()
            for ii in range(4):
                yy= ny+dy[ii]
                xx= nx+dx[ii]

                if 0<=yy<n and 0<=xx<m and mapp[yy][xx]==1 and  visited[yy][xx] == False:
                    visited[yy][xx] = True
                    queue.append([yy, xx])

t = int(input())
for j in range(t):
    m, n, k = map(int, input().split())
    mapp = [[0] * m for _ in range(n)]
    visited = [[False] * m for _ in range(n)]
    cnt = 0
    for i in range(k):
        wm, wn = map(int, input().split())
        mapp[wn][wm] = 1
    
    for ix in range(n):
        for jx in range(m):
            if mapp[ix][jx]==1 and visited[ix][jx] == False:
                    cnt+=1
                    bfs(ix, jx)
    answer.append(cnt)

for i in answer:
  print(i)

 

시간/공간 복잡도

따로 생각하지 않았다. 

 

최적화 및 개선

  • 따로 하지않음

 

어려웠던 점

  • BFS는 큐에 넣기 전에 방문처리를 해야 중복 방문처리를 하지 않게 된다는 것을 알게됐다. 

 

'코딩테스트 > 문제 풀이 - Python' 카테고리의 다른 글

[백준1003] 피보나치 함수  (0) 2024.09.09
[백준11723] 집합  (0) 2024.09.09
[백준1926] 그림  (0) 2024.08.26
[백준9252] LCS 2  (0) 2024.08.14
[백준17829] 222-풀링  (0) 2024.08.14

6-1. 스택 개념

 

스택은 먼저 입력한 데이터를 제일 나중에 꺼낼 수 있는 자료구조이다. 

먼저 들어간 것이 마지막에 나오는 규칙을 선입후출, FILO(First In Last Out)이라고 한다. 

이때, 스택에 삽입하는 연산을 push, 빼는 연산을 pop이라고 한다. 

 

6-1. 스택의 정의

 

스택 자료형의 동작 형태를 설계하는 것은 추상 자료형(ADT)을 정의하는 것이다. 

추상 자료형ADT(abstract data type) 이란?

=> 인터페이스만 있고 실제 구현은 되지 않은 자료형

 

스택은 push, pop, 스택이 가득 찼는지 확인(isFull), 스택이 비었는지 확인isEmpty)과 같은 연산을 정의해야 한다. 

또한 스택에는 최근에 삽입한 데이터의 위치(현재 가리키는 인덱스)를 저장할 함수인 top도 있어야 한다. 

 

스택 구현하기

 

스택은 최근에 삽입한 데이터를 대상으로 뭔가 연산 해야 할 경우 적합. 

 

# 스택 ADT 구현

stack = [] #스택 리스트 초기화 
max_size = 10 # tmxordml 최대 크기 

def ifFull(stack):
    # 스택이 가득 찼는지 확인하는 함수 
    return len(stack) == max_size

def isEmpty(stack):
    # 스택이 비어있는지 확인하는 함수 
    return len(stack) == 0

def push(stack, item):
    # 스택에 데이터를 추가하는 함수
    if ifFull(stack):
        print("스택이 가득 찼다.") 
    else:
        stack.append(item)
        stack.append("데이터가 추가됐다. ")

def pop(stack):
    # 스택에서 데이터를 꺼내는 함수
    if isEmpty(stack):
        print("스택이 비었다. ")
        return None
    else:
        return stack.pop()

 

그러나 파이썬의 리스트는 크기를 동적으로 관리하기 때문에 max_size나 isFull(), isEmpty()함수는 따로 구현하지 않는다. 

코드의 push(), pop()함수는 기존의 원소 추가 함수append(), 원소 꺼내는 함수 pop()이 있기 때문에 따로 구현하지 않아도 된다. 

 

 

주의: 실전에서는 문제에 스택을 활용해야 풀 수 있다는 생각을 하지 못해서 문제를 풀지못하는 경우가 대부분임

따라서 스택 관련 문제를 많이 풀어보고, 해당 문제는 스택을 사용하면 좋겠다는 감을 익히는 것이 중요함

 


 

질문

  1. 스택을 이용하여 주어진 문자열을 뒤집는 알고리즘을 설계하고 구현해 보세요. 이 알고리즘의 시간 복잡도와 공간 복잡도는 각각 어떻게 되나요? 스택을 사용하지 않고도 문자열을 뒤집을 수 있는 다른 방법을 설명해 보세요.

답:

 

<스택을 이용하여 주어진 문자열을 뒤집는 알고리즘을 설계>

 

문자열의 길이가 n이라고 가정한다. 

1. 문자열의 문자를 임의의 리스트에 하나씩 넣는다. 

2. 빈 임의의 문자열 변수를 하나 선언한다. 

3. 임의의 리스트에서 pop()을 하여 꺼낸 값을 빈 임의의 문자열 변수에 + 연산을 하여 추가한다. 

3번은 문자열의 길이만큼 행한다. 

 

<위 알고리즘의 시간 및 공간 복잡도>

 

전체 시간복잡도 = 1번 과정에 대한 시간 복잡도 n + 3번 과정에 대한 시간복잡도 n^2 = O(n^2)

전체 공간 복잡도 = 문자열의 길이 n만큼 nbyte = O(n)

 

<스택을 사용하지 않고도 문자열을 뒤집을 수 있는 다른 방법>

 

파이썬의 슬라이스를 사용해 뒤집는 방법이 있다. 

 

 

2. 스택이 재귀적인 함수 호출과 어떻게 관련이 있는지 설명해 보세요. 재귀 함수를 스택을 사용하여 비재귀적으로 변환하는 방법을 예시를 통해 설명할 수 있나요?

 

답:

 

<스택이 재귀적인 함수 호출과 어떻게 관련이 있는가?>

 

재귀적인 함수 호출은 함수 호출 조건을 5로 준다면, 첫번째로 함수를 호출 한것이 해당 함수를 두번째로 호출하게되고 두번째로 호출 한 함수에서 해당 함수를 세번째로 호출하게 되고 , , ,이런식으로 진행이 되다가 조건에 따라 추가적인 함수 호출을 하지않게 된다. 마지막으로 함수를 호출한 것이 실행되면서 실행이 끝나면 해당 함수는 처리가 완료되어 끝난다. 직전에 네번째로 호출한 함수에서 다섯번째로 함수 호출한 이후의 로직이 실행되고 실행이 끝나면 해당 함수는 처리가 완료되어 끝난다. 직전에 세번째로 호출한 함수에서 네번째로 함수 호출을 한 이후의 로직이 실행되고 실행이 끝나면 해당 함수는 처리가 완료되어 끝난다... 이렇게 첫번째 함수까지 처리되어 재귀 함수의 실행이 끝난다. 

 

이렇듯 재귀적인 함수의 호출은 스택의 LIFO(Last In, First Out) 원칙에 따라 진행되는 것을 알 수 있다. 

 

<재귀 함수를 스택을 사용하여 비재귀적으로 변환하는 방법과 그 예시>

 

비재귀적 방식이란 함수가 자기 자신을 호출하지 않고, 대신 반복문과 같은 구조를 사용해서 문제를 해결하는 방식이다. 

예를들면 대상인 피보나치 함수를 재귀로 구현하면 다음과 같다. 

 

def fibonacci(n):
    if n <= 1:
        return n
    return fibonacci(n - 1) + fibonacci(n - 2)
    
print(fibonacci(3))

 

위 재귀 함수를 비재귀적 방식으로 다시 구현하면 다음과 같다. 

def fibonacci(n):
    if n <= 1:
        return n

    a = 0
    b = 1
    
    for i in range(2, n+1):
        c = a + b
        a = b
        b = c
    
    return b

print(fibonacci(3))

 

 

* 정리된 개념 출처: 코딩 테스트 합격자 되기 - 박경록(파이썬 편)

5-1. 배열 개념

 

배열은 인덱스와 값을 1대 1 대응하여 관리하는 자료구조이다. 

배열은 인덱스를 통해 어떤 위치에 있는 값이든 한 번에 접근할 수 있다. 

이런 방식을 임의 접근(random access)라고 한다. 

 

파이썬에서 배열 선언하는 방법

arr = [0, 0, 0]
arr = [0] * 3

 

 

리스트 생성자를 사용하는 방법

arr = list(range(3)) #[0, 1, 2]

 

 

리스트 컴프리헨션을 활용하는 방법

arr = [0 for _ in range(3)] # [0, 0, 0]

 

파이썬에서는 배열을 지원하는 문법은 따로 없고, 대신 리스트라는 문법을 지원한다. 

(사실 엄밀히 말하자면 배열과 리스트는 다른 개념임)

 

파이썬의 리스트는 동적으로 크기를 조절할 수 있도록 구현됐다. 

파이썬의 리스트는 다른 언어의 배열 기능을 그대로 사용하면서 배열의 크기는 가변적으로 사용할 수 있다. 

 

배열과 차원

 

배열은 2차원, 3차원, ..., 다차원 배열 까지 사용할 수 있다. 

그러나 컴퓨터의 메모리 구조는 1차원이다. 

이는 2차원, 3차원, ..., 다차원 배열도 실제로는 1차원 공간에 저장된다는 뜻이다. 

배열은 몇 차원이든 상관없이 메모리에는 연속적으로 할당된다. 

 

1차원 배열

 

배열의 각 데이터는 메모리의 낮은 주소에서 높은 주소 방향으로 연속적으로 할당된다. 

 

2차원 배열

 

2차원 배열은 1차원 배열을 확장한 것이다. 

 

2차원 배열 활용 예시 

# 2차원 배열을 리스트로 표현
arr = [[1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12]]

# arr[2][3]에 저장된 값 출력
print(arr[2][3]) # 12

# arr[2][3]에 저장된 값을 15로 변경
print[2][3] = 15

 

리스트 컴프리헨션을 통한 2차원 배열 활용 예시 

 

# 크기가 3 * 4인 리스트를 선언하는 예시 
arr = [[i]*4 for i in range(3)] # [[0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0]]

 

arr = [[1, 2, 3], [4, 5, 6]]

 

위의 배열에서  첫번째 행과 두번째 행의 메모리 주소는 연속된다. (1행의 인덱스 2 다음 바로 2행의 인덱스0의 주소가 이어진다. )

 

 

5-2. 배열의 효율성

 

배열 연산의 시간복잡도를 통해 배열의 효율성은 아래와 같다. 

 

배열 연산의 시간 복잡도

 

아까 배열은 인덱스를 통해 임의 접근 방법을 사용한다고 했다. 따라서 데이터에 접근하기 위한 시간 복잡도는 O(1)이다. 

만약 배열에 데이터를 추가하거나 삭제해야 한다면? 추가후에 기존에 있던 것들을 처리할 필요가 있는지,  혹은 대상을 삭제하고 기존에 있는 것들을 처리할 필요가 있는지 확인이 필요하다. 

 

1. 맨 뒤에 삽입할 경우

  • 임의 접근을 통해 맨뒷 자리를 찾을 수 있다. 
  • 맨 뒤에 값을 추가한 후에 기존의 값들을 이동할 필요가 없다. 
  • 즉, 시간 복잡도는 O(1)이다. 

 

2. 맨 앞에 삽입할 경우

  • 임의 접근을 통해 맨 앞 자리를 찾을 수 있다. 
  • 기존 데이터 들을 뒤로 한칸씩 밀어야 데이터의 소실 없이 맨 앞에 값을 삽입할 수 있다. (== 현재 갖고 있는 데이터의 개수가 N개라면,  O(N))
  • 즉, 시간 복잡도는 O(N)이다. 

 

3. 중간에 삽입할 경우

  • 임의 접근을 통해 중간에 삽입할 자리를 찾을 수 있다. 
  • 기존 데이터 들을 뒤로 한칸씩 밀어야 데이터의 소실 없이 맨 앞에 값을 삽입할 수 있다. (== 뒤로 밀어야 야 하는 데이터의 개수가 N개라면,  O(N))
  • 즉, 시간 복잡도는 O(N)이다. 

 

위의 경우 들을 봤을때, 배열로 데이터를 저장하기 전에는 항상 이런 비용을 생각하는 것이 바람직하다. 

이렇듯 배열을 선택할 때 고려할 점은 다음과 같다. 

 

배열을 선택할 때 고려할 점

 

1. 할당할 수 있는 메모리 크기를 확인해야 한다. (파이썬에서는 리스트를 사용하므로, 배열 크기에 대한 고민은 할 필요가 없다. 공부를 위해 읽어두기)

  • 운영체제마다 배열을 할당할 수 있는 메모리의 값은 다르지만, 보통 정수형 1차원 배열은 1천 만개, 2차원 배열은 3천*3천 크기를 최대로 생각한다. 따라서 이 이상의 값의 데이터를 관리하고자 하면 런타임에서 배열 할당에 실패할 수 있다. 

2. 중간에 데이터 삽입이 많은지 확인해야 한다. 

  • 배열은 선형 자료구조이기 때문에, 중간이나 맨 처음의 위치에 데이터를 자주 삽입하면 시간복잡도가 높아져, 시간초과가 발생할 수 있다. 

 

5-3. 코딩테스트에서 자주 활용하는 리스트 기법

 

리스트에 데이터를 추가하는방법 

 

1. append()

# 리스트의 맨 끝에 데이터 추가
tmp_list = [1, 2, 3]
tmp_list.append(4) # [1, 2, 3, 4]

 

2. + 연산자

tmp_list = [1, 2, 3]
tmp_list = tmp_list + [4, 5] # [1, 2, 3, 4, 5]

 

3. insert()

# 특정 위치에 데이터를 삽입할 수 있다. 
tmp_list = [1, 2, 3]
tmp_list.insert(2, 9) #[1, 2, 9, 3]

 

 

 

 

리스트에서 데이터를 삭제하는 방법

 

1. pop() 

# 특정 위치에 데이터를 삭제할 수 있다. 
# 삭제한 데이터의 값을 반환한다. 
tmp_list = [1, 2, 3]
pop = tmp_list.pop(2) # 3
print(tmp_list) # [1, 2]

 

 

2. remove()

# 특정 데이터를 찾아 삭제할 수 있다. 
# 인수로 받은 값이 처음 등장하는 위치의 데이터를 삭제한다. 
tmp_list = [1, 2, 3]
tmp_list.remove(2) # [1, 3]

 

 

리스트 컴프리헨션으로 데이터에 특정 연산 적용하기

 

리스트 컴프리헨션은 기존 리스트를 기반으로 새 리스트를 만들거나, 반복문이나 조건문을 통해 복잡한 리스트를 생성하는 등 다양한 상황에서 사용할 수 있는 문법이다. 

 

 

리스트에 제곱 연산 적용 예시 

tmp_list = [1, 2, 3]
squares = [num**2 for num in tmp_list] #[1, 4, 9]
# tmp_list의 값은 여전히 [1, 2, 3] 이다.

 

 

리스트 컴프리헨션은 연산이 끝난 리스트를 반환할 뿐, 연산 대상 리스트를 바꾸지 않는다. 

 

 

 

유용하게 쓰이는 리스트 연관 메서드 

 

alphabet = ["a", "b", "c", "a"]

# 리스트의 전체 데이터 개수 반환 함수 len()
len(alphabet) # 4

# 특정 데이터가 처음 등장할 적의 인덱스를 반환하는 index()메서드, 만약 값이 없는경우 -1 반환
alphabet.index("a") # 0

# 사용자가 정한 기준에 따라 데이터를 정렬하는 sort()메서드
# 함수안에 인수가 없을 경우, 오름차순으로 데이터 정렬
alphabet.sort() # ["a", "a", "b", "c"]
# 역순 
alphabet.sort(reverse=True) # ["c", "b", "a", "a"]

# 특정 데이터 개수를 반환하는 count() 메서드
alphabet.count("a") # 2

 

* 정리된 개념 출처: 코딩 테스트 합격자 되기 - 박경록(파이썬 편)

https://www.acmicpc.net/problem/1926

 

문제 해결 방법

 

그림 정보가 적힌 좌표를 순회한다. 대신 방문여부를 알 수 있는 visited 배열이 필요하다. 

좌표를 순회할때 1을 만나고, 방문한 적이 없으면 bfs함수를 실행한다. 

이때, deque를 활용해 큐를 만들고 큐에 bfs함수를 실행할 당시의 좌표값을 넣어준다. 

bfs함수에서는 큐에서 값을 꺼내어 방문처리를 해주고, 자신의 자리에서 그림이 이어져 있다는 판단 기준인 위, 아래, 양옆을 조회 한다. 

이때, 새로 조회하는 위치가 그림 정보가 적힌 좌표의 범위를 벗어나서도 안되고, 이미 방문 한 적이 있어도 안된다. 또한 0이여도 안된다. 

값이 0이 아니고 방문한 적이 없으면 현재자리의 값에서+1을 해준다.  큐에 해당 좌표와 얼마나 끊기지 않고 값을 조회하고있는지에 대한 값 현재 자리의 값+1을 넣어준다. 

 

순회를 하면서 더이상 큐에 값을 이어 넣을 수 없으면(그림이 끊기면), 얼마나 끊기지 않고 값을 조회했는지에 대한 값을 임의의 리스트에 넣어준다. 

 

그림 정보 순회가 모두 끝나면 임의의 리스트의 원소의 개수와 원소의 최대값을 출력한다. 

 

코드 구현

정답 코드 

import sys
input=sys.stdin.readline
n, m = map(int, input().split())
from collections import deque

if n==0 and m==0:
    print(0)
    print(0)
    exit(0)

dy=[1, -1, 0, 0]
dx=[0, 0, 1, -1]

tmp=[]
for i in range(n):
    tmp2=list(map(int, input().split()))
    tmp.append(tmp2)

# 그냥 카운트만 하는애 cnt
# 방문 확인용 visited
cnt = 0
visited = [([False] * m) for _ in range(n)]
bigN = 0
def bfs(cnt, dequeA, visited):
    bigN=1
    while dequeA:
        yy, xx, _ = dequeA.popleft()
        visited[yy][xx] = True
        for i in range(4): 
            nx=xx+dx[i]
            ny=yy+dy[i]

            if ny<0 or nx<0 or ny>=n or nx>=m:
                continue
            if visited[ny][nx]==True or tmp[ny][nx]==0:
                continue
            if tmp[ny][nx]>=1 and visited[ny][nx]==False:
                tmp[ny][nx] = bigN+1
                bigN=bigN+1
                visited[ny][nx]=True
                dequeA.append([ny,nx, bigN])
    return cnt, bigN

tmp3=[]
check = 0
dequeA = deque()
for i in range(n):
    for j in range(m):
        if tmp[i][j] == 1 and visited[i][j] == False:
            dequeA.append([i,j, 1])
            cnt+=1
            cnt, bigN = bfs(cnt, dequeA, visited)
            tmp3.append(bigN)
            check =1

print(cnt)

if n == 0 and m ==0 or check ==0:
    print(0)
else:
    print(max(tmp3))

 

시간/공간 복잡도

따로 생각하지 않았다. 

 

최적화 및 개선

  • 따로 하지않음

 

어려웠던 점

  • BFS 문제를 효율적으로 푸는 방법이 가물가물해서 문제 풀기 어려웠다. 

 

알게된 것

 

함수 객체 할당과 함수 호출 구문을 구분하지 못해서 생긴 일 

 

여러줄을 받을 때 속도 감소를 위해 input()함수 말고 sys 에서 제공하는 readline()함수를 사용하려는 상황이다. 

import sys

n, m = map(int, input().split())

input=sys.stdin.readline()

tmp=[]
for i in range(n):
    
    # tmp2=list(input.split())
    tmp2=input.split()
    print('tmp2', tmp2)
    tmp.append(tmp2)

print(tmp)

 

문제가 있는 코드: 이코드에서는 2번째줄 3번째줄만 입력을 받는게 된다. 

 

  • 괄호를 붙이지 않은 경우 (input = sys.stdin.readline):
    • 이 경우 sys.stdin.readline 함수 객체를 input이라는 변수에 직접 할당하는 것이다. 이 상태에서는 input은 함수 객체 자체를 참조하게 된다.
  • 괄호를 붙인 경우 (input()):
    • 괄호를 붙이면 함수가 실제로 호출된다. 함수 호출은 해당 함수가 수행하는 작업을 실행하고, 그 결과를 반환한다. 

 

import sys

n, m = map(int, input().split())

input=sys.stdin.readline

tmp=[]
for i in range(n):
    
    tmp2=input().split()
    tmp.append(tmp2)

print(tmp)


문제 인지후 바꾼 코드 

'코딩테스트 > 문제 풀이 - Python' 카테고리의 다른 글

[백준11723] 집합  (0) 2024.09.09
[백준1012] 유기농 배추  (0) 2024.09.09
[백준9252] LCS 2  (0) 2024.08.14
[백준17829] 222-풀링  (0) 2024.08.14
[백준2504] 괄호의 값  (0) 2024.08.12

파이썬에서는 기본적으로 제공하는 데이터 타입들이 있다.

 

집을 사면 딸려오는 가구(사실 그 딸려오는 가구 값도 포함되는건 맞지만)처럼 파이썬에서는 기본 데이터 타입과,

컬렉션 데이터 타입을 제공한다. 

 

04-1 빌트인 데이터 타입

 

기본 데이터 타입

 

기본 데이터 타입에는 정수형, 부동소수형, 문자열 타입이 있다.

 

정수형

: 양, 음의 정수와 0을 포함한다.

사칙연산 뿐만 아니라 그 외의 연산도 가능하다. 

예를들어, **을 통한 지수 연산, //을 통한 나눗셈에서 몫만 반환하는 연산 등

 

아래는 정수형 데이터 정의 및 활용 방법이다. 

 

# 정수형 변수 선언

a = 4
b = 3

# 정수형 산술 연산

print(a + b) # 더하기 1
print(a - b) # 빼기 12
print(a * b) # 곱하기 45
print(a / b) # 나누기(소수점 포함) 1.3...
print(a // b) # 나누기(소수점 제외) 1
print(a % b) # 모듈러 연산(나머지 값 출력) 1
print(-a) # 부호 바꿈 -4
print(abs(-a)) # 절대값 4
print(a**b) # a의 b승 64

# 정수형 비교 연산

print(a == b) # 같은 값인지 비교 False
print(a != b) # 같은 값이 아닌지 비교 True
print(a > b)  # 왼쪽값이 더 큰지 비교 True
print(a < b)  # 오른쪽 값이 더 큰지 비교 False
print(a >= b) # 왼쪽값이 더 크거나 같은지 비교 True
print(a <= b) # 오른쪽값이 더 크거나 같은지 비교 False

# 정수형 비트 연산

a = 13
b = 4

print(a & b) # AND 4
print(a | b) # OR 13
print(a ^ b) # XOR 9
print(~a) # NOT -14
print(a << 2) # 왼쪽 시프트 (a에 2^2를 곱한 것과 동일) 52
print(a >> 1) # 오른쪽 시프트 (a에 2^1로 나눈 것과 동일) 6 

#정수형 논리 연산

print(a and b) # 논리 연산 AND 4
print(a or b) # 논리 연산 OR 13
print(not a) # 논리 연산 NOT / False

 

*~a가 14인 이유

a는 2진수로 표현하면 0000 1101 이다. ~(not)을 하면 0000 1101이 반전돼서 1111 0010이 된다. 

 

맨 왼쪽의 값이 0이면 양수, 1이면 음수를 나타내는 것이다. 

1111 0010은 음수의 값이고, 컴퓨터에서 음수는 2의 보수로 표현된다. 

 

2의 보수를 읽기 위해서는 값을 한번 반전해주고 => 0000 1101 

그대로 1을 더해준다. => 0000 1110 이는 10진수로 14이다.

 

하지만 이 값은 음수이므로 -14로 표현할 수 있는 것이다. 

 

*논리 연산 AND 연산자

파이썬에서 논리 연산 AND는 두 피연산자가 모두 참이면 마지막 값을 반환한다. 

만약 첫 번째 피연산자가 거짓이거나 NULL이면, 첫 번째 피연산자를 반환한다. 

 

 

부동소수형

부동소수형에서는 사칙 연산, 정수형 나누기, 모듈러, 제곱 연산, 논리 연산을 할 수 있다. 

 

부동소수형에서 눈여겨 봐야할 곳은 10 % 3.2의 값이 0.4가 나와야 하지만 파이썬에서는 

0.39999999999999947이 나온다. 

그 이유는 파이썬에서는 부동소수형 데이터를 이진법으로 표현하기 때문에 발생하는 거고, 표현 과정에서 오차가 발생한다.

이를 엡실론이라고 한다. 

 

따라서 부동소수형 데이터를 활용한 문제에서는 오차 허용 범위의 언급을 확인하고, 주의 해야한다. 

 

 


04-2 컬렉션 데이터 타입

컬렉션 데이터 타입은 여러 값을 담는 데이터 타입을 말한다. 그 유형으로 리스트, 튜플, 딕셔너리, 셋, 문자열 등이 있다.

또한 컬렉션 데이터 타입은 두가지로 나눌 수 있는데, 이는 데이터의 수정 가능 여부에 따라 변경할 수 있는 객체(mutable object)와 변경할 수 없는 객체(immutable object)로 나눌 수 있다. 

 

변경할 수 있는 객체(mutable object)

: 객체 생성 후 객체를 수정할 수 있다. 리스트, 딕셔너리, 셋이 이 유형에 해당한다. 

 

변경할 수 없는 객체(immutable object)

: 객체 생성 후 객체를 수정할 수 없다. 문자열, 튜플이 이 유형에 해당한다. 

(정수나 부동소수점은 컬렉션 데이터 타입은 아니지만 이뮤터블 객체에 속한다)

 

<리스트>

: 리스트는 뮤터블 객체이고, 순서가 있는 자료형이다. 리스트는 인덱스를 활용해 특정 위치의 원소에 접근할 수 있다. 

 

기본적인 리스트 사용법은 다음과 같다. 

# 리스트 선언
tmp_list = [1, 2, 3, 4]
tmp_list2 = [5, 6] + [7, 8, 9]
tmp_list3 = list(tmp_list)
print(tmp_list) # [1, 2, 3, 4]
print(tmp_list2) # [5, 6, 7, 8, 9]
print(tmp_list3) # [1, 2, 3, 4]

# 리스트 인덱싱
tmp_list.append(5)
print(tmp_list) # [1, 2, 3, 4, 5]

# 인덱싱으로 값 삭제
del tmp_list[0]
print(tmp_list) # [2, 3, 4, 5]

 

 

리스트의 활용방법 중에 리스트 슬라이싱이라고 있다. 

슬라이싱은 시퀀스 자료형의 범위를 지정해 값을 복사하여 가져오는 방식을 말한다. 

 

리스트 슬라이싱 활용법은 다음과 같다. 

print(tmp_list[0:2]) # [2, 3]
print(tmp_list[1:]) # [3, 4, 5]
print(tmp_list[2:3]) # [4]
print(tmp_list[-2:-1]) # [4]

 

 

<딕셔너리>

: 딕셔너리는 뮤터블 객체이고, 키와 값 쌍을 저장하는 해시테이블로 구현돼 있다. 

키를 사용하여 값을 검색하는 자료형이다. 

 

기본적인 딕셔너리 사용법은 다음과 같다. 

# 딕셔너리 초기화 
dic = { }

# 딕셔너리 삽입과 출력
dic["yellow"] = 1
dic["green"] = 3
dic["blue"] = 5

print(dic) #{'yellow': 1, 'green': 3, 'blue': 5}

 

딕셔너리 검색 활용법은 다음과 같다.

키에 해당하는 문자열인지 확인하고, 키의 값이 딕셔너리에 존재하면 키-값을 출력한다. 

 

key = "yellow"
if key in dic:
    value = dic[key]
    print(f"{key}: {value}")
else:
    print(f"{key}는 딕셔너리에 존재하지 않습니다. ")

 

딕셔너리 수정 방법은 다음과 같다. 

dic["green"] = 5
print(dic) #{'yellow': 1, 'green': 5, 'blue': 5}

 

 

딕셔너리 삭제 방법은 다음과 같다.

del dic["green"]
print(dic) #{'yellow': 1, 'blue': 5}

 

 

 

<튜플>

: 튜플은 이뮤터블 객체이다. 한 번 생성하면 삽입하거나 삭제할 수 없다. 

 

기본적인 튜플 사용법은 다음과 같다. 

 

# 튜플 초기화 
tup = (1, 2, 3)

 

튜플은 인덱싱과 슬라이싱을 활용할 수 있고, 리스트와 활용법이 같다.

 

<문자열>

: 문자열은 문자의 집합 형태이며, 이뮤터블 객체이다. 

 

기본적인 문자열 사용법은 다음과 같다.

 

# 문자열 초기화 

string = "Hi" # 큰 따옴표 사용
string2 = 'Hello'# 작은 따옴표 사용

# 문자열 추가, 삭제 
string3 = "A-"
string3 += "yo" # 이때, string3은 기존의 문자열의 메모리 주소와의 연결은 끊고, 문자열을 새로 만들고 해당 문자열이 담길 메모리 주소를 새로 할당한다. 
print(string3) # "A-yo"

# 문자열 수정 
string4 = "Ha"
string4 = string4.replace("a", "o")
print(string4) # "Ho"

 


 

04-3 함수

 

파이썬에서의 함수 사용법은 다음과 같다.

 

def add(num1, num2):
    result = num1 + num2
    return result 

# 함수 호출

ret = add(5, 10)
print(ret)

 

 

함수를 더 간단하게 사용하기 위한 방법으로 파이썬에서는 람다식을 사용할 수 있다. 

또한 람다식은 익명 함수를 만드는데 사용한다. 

익명 함수는 이름 없는 함수이고, 코드에서 일시적으로 실행할 목적으로 사용하거나, 다른 함수의 인수로 사용할 수 있다. 

 

람다식의 사용법은 다음과 같다. 

 

# 람다식 정의

lambda x, y : x + y # x와 y를 받아서 더한 값을 반환하는 람다식

# 람다식 사용 유형 1

add = lambda x, y: x + y
print(add(5, 4)) # 9

# 람다식 사용 유형 2

num = [1, 2, 3, 4, 5]
squares = list(map(lambda x: x**2, num))
print(squares) # [1, 4, 9, 16, 25]

 

 

 


04-4 코딩 테스트 코드 구현 노하우

 

1. 조기 반환

: 코드 실행 과정이 끝나기 전에 반환하는 기법

 

2. 보호 구문

: 본격적인 로직 진행 전 예외 처리 코드를 추가하는 기법 

 

3. 합성 함수

: 2개 이상의 함수를 활용해 함수를 추가로 만드는 기법

보통 합성 함수로 람다식을 활용한다. 

 

 

 

 

* 정리된 개념 출처: 코딩 테스트 합격자 되기 - 박경록(파이썬 편)

 

+ Recent posts