웹드루아 - 웹 개발자 드루아

 

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

 

첫 번째 풀이(오답)

1. 트럭 deque와 0으로 이루어진 다리 deque를 만든다.

2. 트럭 deque가 0일 될때까지 while문을 반복한다. 트럭을 하나 popleft해주고
'다리도 하나 popleft 해준다.'(다리를 이동하는 것을 0 하나를 빼고 트럭을 올리는 거로 표현) 

2-1. 다리 deque의 합과 앞으로 올릴려는 트럭 deque에서 pop한 트럭의 합이 w보다 작거나 같은 경우,

pop한 트럭을 다리에 올려준다.

2-2. 다리 deque의 합과 앞으로 올릴려는 트럭 deque에서 pop한 트럭의 합이 w보다 작거나 같은 경우,

pop한 트럭을 트럭 deque에 appendleft 해주고 '0을 넣어준다.' (다리에 아무것도 올라가지 않았다는 표현)

from collections import deque

def solution(b_l, w, t):
    time = 0
    tque = deque(t)
    bl = deque([0]*b_l)
    
    while tque:
        time += 1
        pop = tque.popleft()
        bl.popleft()
        
        if sum(bl) + pop <= w:
            bl.append(pop)
            continue
        
        if sum(bl) + pop > w:
            bl.append(0)
            tque.appendleft(pop)
            continue

    time += b_l
    return time

로직은 맞았지만 케이스 하나에서 시간 초과가 발생했다. sum을 사용해서 그런 것 같다.

 

두 번째 풀이 (정답)

sum을 어떻게 바꿀지 고민해보자

그리고 무조건 처음에 pop을 하여 트럭을 빼는 방식은 비효율적이다.

다리가 버티는 무게(wei)를 따로 만들어 무게를 더하고 빼주자.

무조건 while 반복문을 시작할때, 다리 deque에서 popleft한 요소를 빼준다.

그리고 트럭 deque도 먼저 빼주지 말고 트럭 deque의 0 인덱스와 wei를 더한 무게를 다리가 버틸 수 있는 하중과 비교해주면 훨씬 간단하게 해결할 수 있다.

 

deque를 사용한 풀이

from collections import deque

def solution(b_l, w, t):
    time = 0
    tque = deque(t)
    bl = deque([0]*b_l)
    wei = 0
    
    while tque:
        time += 1
        wei -= bl.popleft()
        
        if wei + tque[0] <= w:
            wei += tque[0]
            bl.append(tque.popleft())
            continue
        
        if wei + tque[0] > w:
            bl.append(0)
            continue

    time += b_l
    
    return time

 

deque를 사용하지 않는 풀이

def solution(b, w, t):
    time = 0
    bridge = [0]*b
    wei = 0
    
    while len(t) != 0:
        time += 1
        wei -= bridge.pop(0)
        
        if wei + t[0] <= w:
            wei += t[0]
            bridge.append(t.pop(0))
        else:
            bridge.append(0)
        
    time += b
        
    
    return time

 

스택/큐 문제를 풀 때 팁

스택이나 큐에 쌓이는 것을 확인하고 싶을 때 위에서 했던 것처럼 +/-를 이용해 표현할 수 있다.

위에서는 다리에 올라간 트럭의 무게를 빠른 속도로 파악하기 위해 wei를 0으로 초기화하고, 들어오는 트럭과 나가는 트럭의 무게를 뺐는데 이는 스택을 사용하는 것과 같은 효과를 가지고 있다.

 

다리는 지나는 트럭 문제 외에 대표적인 문제로 올바른 괄호 찾기 문제가 있다.

이 문제는 중괄호로 주어진 문자열이 열림과 닫힘의 짝이 맞는 지 확인하는 문제이다.

기본적으로는 무조건 false인 경우를 처리한 후 스택에 문자열 순대로 넣으면서 스택에 들어간 괄호가 (이고 이어서 들어가는 괄호가 ) 라면 없애주고 그렇지 않은 경우는 그냥 계속 넣어준다. 결과적으로 스택에 아무것도 남아있지 않으면 올바른 괄호이고, 스택에 남아있다면 올바른 괄호가 아닌 것이다. 이를 정말 간편하게 변수를 0으로 초기화하고 +와 -로 구현할 수 있다.

def solution(s):
	answer = True
    judge = 0
    
    if s[-1] == '(' or s[0] == ')':
    	return False
    
    while s:
    	pop = s.pop(0)
        
        if pop == '(':
        	judge += 1
        
        if  judge > 0 and pop == ')': 
        # 아무것도 들어오지 않은 상태(0)에서 ')'를 넣으면(-1) 의미가 없기 때문에 아무 조치도 하지 않는다.
        	judge -= 1
        
    if judge != 0:
    	return False
        
    return answer

 

위와 같이 0에 +1 -1을 하는 방식으로 스택을 표현했다. 이를 다른 문제를 풀 때도 고려해보고 적용해보면 좋을 것이라 생각된다.

|| 문제 설명 ||

 

 

 

틀린풀이 1

계속 이상하게 문제를 풀어서 이 문제만 3시간은 잡고 있었던거 같다ㅠㅠ

일단 처음에 했던 방식은 아래와 같다

from collections import deque

def solution(maps):
    answer = 0
    n = len(maps)
    m = len(maps[0])
    dh = [1, -1, 0, 0]
    dw = [0, 0, 1, -1]
    vis = []
    visForE = []
    dis = []

    s = []
    e = [] 

    # visit 만들기
    for i in range(n):
        arr = []
        for j in range(m):
            arr.append(0)
        vis.append(arr)
        visForE.append(arr)
        dis.append(arr)



    # 시작점 찾기
    for i in range(n):
        for j in range(m):
            if maps[i][j] == "S":
                s.append(i)
                s.append(j)

    # 탈출점 찾기
    for i in range(n):
        for j in range(m):
            if maps[i][j] == "E":
                e.append(i)
                e.append(j)            


    # 레버까지의 최단거리 + 레버 -> 탈출구 까지의 최단거리
    time = 0
    queue = deque()
    queue.append(s)

    equeue = deque()

    while queue:
        h, w = queue.popleft()
        vis[h][w] = 1 # 방문 처리

        if maps[h][w] == "L":
            equeue.append((h, w, 0))
            break

        for i in range(4):
            nh = h + dh[i]
            nw = w + dw[i]

            if nh < 0 or nh >= n or nw < 0 or nw >= m:
                continue

            if maps[nh][nw] == "X":
                continue

            if vis[nh][nw] == 1:
                continue

            if vis[nh][nw] == 0:
                queue.append((nh, nw))
                time += 1

    print(time)
    print(queue)
    print(equeue)

이렇게 레버까지의 걸린 시간을 구한 후에 레버에서 탈출구까지 걸리는 시간을 구할려고 했다. 하지만 이 방식은 탐색을 진행할 때마다 전역 변수인 time에 +1을 해주기 때문에 탐색하는 모든 시간을 구하므로 옳지 않다.

 

그래서 큐에 비용까지 포함해서 다시 코드를 작성했다.

 

틀린 풀이 2

 

from collections import deque

def solution(maps):
    answer = 0
    n = len(maps)
    m = len(maps[0])
    dh = [1, -1, 0, 0]
    dw = [0, 0, 1, -1]
    lastcost = 0
    
    vis = []
    visForE = []
    
    s = []
    
    # visit 만들기
    for i in range(n):
        arr = []
        for j in range(m):
            arr.append(0)
        vis.append(arr)
        visForE.append(arr)
    
    # 시작점 찾기
    for i in range(n):
        for j in range(m):
            if maps[i][j] == "S":
                s.append(i)
                s.append(j) 
    
    # 레버까지의 최단시간 구하기
    h, w = s
    vis[h][w] = 1
    queue = deque()
    queue.append((h, w, 0))
    
    
    while queue:
        h, w, cost = queue.popleft()
        
        if maps[h][w] == "L":
            queue.append((h, w, cost))
            break
        
        for i in range(4):
            nh = h + dh[i]
            nw = w + dw[i]
            
            if nh < 0 or nh >= n or nw < 0 or nw >= m:
                continue
            
            if maps[nh][nw] == "X":
                continue
            
            if vis[nh][nw] == 1:
                continue
            
            if vis[nh][nw] == 0:
                queue.append((nh, nw, cost + 1))
                vis[nh][nw] = 1
    
    # 레버에서 탈출점까지의 최단 시간 구하기
    
    while queue:
        x, y, cost = queue.popleft()
        
        if maps[x][y] == "E":
            return cost
            break
        
        for i in range(4):
            nh = x + dh[i]
            nw = y + dw[i]
            
            if nh < 0 or nh >= n or nw < 0 or nw >= m:
                continue
            
            if maps[nh][nw] == "X":
                continue
            
            if vis[nh][nw] == 1:
                continue
            
            if vis[nh][nw] == 0:
                queue.append((nh, nw, cost + 1))
                vis[nh][nw] = 1
    
    ## 비용으로 생각해서 풀자 전역적으로 time을 지정해서
    ## 풀려고 하니까 최단 거리가 아니라
    ## 모든 지점을 탐색하는데 걸린 시간이 출력되어서 계속 못 풀었다
    
    return -1

이 경우는 무조건 레버를 찾을 수 있다는 가정하에 다음 단계로 넘어가기 때문에 정답을 맞히지 못한건 같다 그래서 bfs 함수를 따로 만들어서 (시작점, 목표점, maps)를 입력해 cost 값을 받는 방식으로 바꿔보기로 했다.

 

옳은 풀이

from collections import deque

def bfs(start, end, maps):
    h, w = start
    eh, ew = end
    
    dh = [1, -1, 0, 0]
    dw = [0, 0, 1, -1]
    n = len(maps)
    m = len(maps[0])
    
    visit = []
    for i in range(n):
        arr = []
        for j in range(m):
            arr.append(0)
        visit.append(arr)
    
    que = deque()
    que.append((h, w, 0))
    visit[h][w] = 1
    
    while que:
        h, w, cost = que.popleft()
        
        if h == eh and w == ew:
            return cost
        
        for i in range(4):
            nh = h + dh[i]
            nw = w + dw[i]
            
            if nh < 0 or nh >= n or nw < 0 or nw >= m:
                continue
            
            if maps[nh][nw] == "X":
                continue
            
            if visit[nh][nw] == 1:
                continue
            
            if visit[nh][nw] == 0:
                que.append((nh, nw, cost + 1))
                visit[nh][nw] = 1
    
    return -1
    
def solution(maps):
    s = []
    e = []
    l = []
    
    n = len(maps)
    m = len(maps[0])
    
    for i in range(n):
        for j in range(m):
            if maps[i][j] == "S":
                s.append(i)
                s.append(j)
    
    for i in range(n):
        for j in range(m):
            if maps[i][j] == "L":
                l.append(i)
                l.append(j) 
    
    for i in range(n):
        for j in range(m):
            if maps[i][j] == "E":
                e.append(i)
                e.append(j)
    
    path1 = bfs(s, l, maps)
    path2 = bfs(l, e, maps)
    
    if path1 != -1 and path2 != -1:
        return path1 + path2
    
    return -1

 

함수를 따로 만들어서 시작점과 끝점을 정하고 각각 따로 bfs를 돌려서 각 비용을 계산하고 둘다 찾아진다면 두 비용을 합친 것을 리턴하고 아니라면 -1을 리턴해 마무리 해준다.

 

항상 차분하게 문제를 보고 신중하게 생각하자

푸는 과정은 일단 다 풀어보고 이해하게 된 점 정리와 사용된 자료구조를 정리하는 방식으로 진행할 것이다.

 

---

폰켓몬 문제

 

문제 풀이

풀이1

def solution(nums):
    setNums = list(set(nums))
    countMonster = len(setNums)
    
    if countMonster <= (len(nums)/2):
        return countMonster
    elif countMonster > (len(nums)/2):
        return (len(nums)/2)

 

처음에는 뽑는 경우의 수를 모두 가져오고 종류를 확인할려고 했는데, 코드를 작성하는 과정에서 너무 복잡하다는 생각에 다시 문제를 확인했다. 결론적으로 뽑을 수 있는 폰켓몬의 수는 정해져 있으므로 그 이상으로 여러 종류의 폰켓몬을 뽑을 순 없다.
따라서 뽑을 수 있는 수보다 종류가 적거나 같으면 가장 많이 뽑는 수는 뽑을 수 있는 수 그 자체가 될것이고,

뽑을 수 있는 수보다 종류가 적다면 무조건 파라미터로 받는 나열에 있는 종류의 수가 가장 많이 뽑은 종류의 수가 될것이다.

이 생각으로 위와 같이 풀었다.

 

풀이 2

근데 이는 더 간다한게 min 내장 함수를 통해 풀 수 있는데 그 풀이는 다음과 같다.

def solution(nums):
	return min( len(set(nums)), (len(nums)/2) )

 

위에서 작성한 코드와 똑같은 기능을 하지만 min을 이용에 훨씬 간결하게 짤 수 있다.

---

완주하지 못한 선수

 

문제 풀이

그 전 포스팅에서 적긴 했는데, 문제를 풀면서 느낀 것이 먼저 문제의 의도를 정확히 파악하고 머리로 알고리즘을 설계하는 것이 더 중요한 것 같다.

 

처음에는 set 함수를 이용해서 풀려고 했는데 set을 이용하면 동명이인을 잡아낼 수 없어 문제가 됐다. 그 다음에는 참여자 명단이랑 완주자 명단을 비교하며 참여자 명단에서 완주자 명단에 있는 사람을 없애려고 했는데, 이는 설정한 len(참여자명단)이 실시간으로 바뀌기 때문에 for문에서 에러가 나 실행하지 못했다.

 

그래서 hash를 이용해 풀었다.

주어지는 선수의 수는 100000이하기 때문에 O(NlogN) 이하의 시간으로 풀어야한다.

 

풀이 1

특정 문자열은 고유한 해시값으로 변환되기 때문에 이를 이용했다.

참여자 명단의 이름들을 해시로 변환해 더하고, 똑같이 완주자 명단의 이름들을 해시로 변환해 더했다.

그리고 빼면 특정 해시값이 나오고 그 해시값에 해당하는 이름을 가져오면 완주하지 못한 사람이다.

   

틀린 처음 풀이

def solution(participant, completion):
    mydict = dict()
    
    for i in participant:
        mydict[hash(i)] = i
    
    sumPartKey = sum(mydict.keys())
    sumComp = sum(map(lambda x : hash(x), completion))

    NotCompleteHash = sumPartKey - sumComp
    return mydict[NotCompleteHash]

 

이 방식은 오류가 났었다. 그 이유는 반복문으로 딕셔너리를 만들때 동명이인은 같은 키로 들어가기 때문에 위에서 만들어진 mydict은 동명이인을 받아도 하나로 넣어버린다. 그렇기 때문에 sumPartKey에서 sumComp를 빼면 해시값이 아닌 숫자가 나와 동명이인을 입력 받았을 때는 오류가 발생한다.

 

맞는 풀이

def solution(participant, completion):
    mydict = dict()
    sumPartKey = 0
    for i in participant:
        mydict[hash(i)] = i
        sumPartKey += hash(i)
        
    sumComp = sum(map(lambda x : hash(x), completion))

    NotCompleteHash = sumPartKey - sumComp
    return mydict[NotCompleteHash]

 

딕셔너리를 만들 때, 넣는 값들을 바로바로 더해줘서 위에서 있었던 문제를 해결할 수 있다.

 

풀이 2

collection 모듈의 Counter를 이용한 풀이 방식이다. Counter을 이용하면 배열에 각 원소들의 갯수가 몇개인지 뽑아주는데 참여자 명단과 완주자 명단에 적용을 하고 빼주면 완주하지 못한 참여자를 구할 수 있다. 

딕셔너리 끼리는 뺄 수 없지만 Counter를 통해 객체로 바뀌었기 때문에 빼는 것이 가능하다.

import collections

def solution(participant, completion):
	answer = collections.Counter(participant) - collections.Counter(completion)
    return list(answer.keys()[0])

---

전화번호 목록 문제

 

이 문제를 풀기 위해선 문자열 비교하는 것을 알아야한다.

• 완전 일치 : == !=
• 부분 일치 : in not in
• 전방 일치 : startswith
• 후방 일치 : endswith

위와 같이 비교를 할 수 있고 전방과 후방 일치는 문자열2. startswith / endswith (문자열1) 방식으로 사용하고 문자열1일 문자열2에 있는지 찾는 것이다.

 

그리고 정렬하는 기준에 대해 알아야한다. 배열의 원소가 정수형이나 실수형이라면 정렬의 기준의 숫자의 크기이지만 문자열인 경우는 제일 앞에 있는 문자를 기준으로 정렬한다. 제일 먼저 오는 문자 순으로 정렬한 후의 그 뒤에 오는 문자를 기준으로 다시 정렬한다. 예를 들어 133이 1222보다 작지만 1 다음으로 오는 2가 3보다 작기 때문에 ['133', '1222']를 sort하면 ['1222', '133']으로 정렬된다.

 

예를 하나 더 들어서 설명하자면,

[12, 134, 34, 456]에 sort()를 해주면 [12, 34, 134, 456]으로 정렬되고,

['12', '134', '34', '456']에 sort()를 해주면 다음과 같이 정렬한다. ['12', '134', '34', '456']

 

이러한 특성을 이용해 문제를 풀 수 있다.

 

파라미터로 오는 배열을 정렬하면 문자열 a가 그 다음에 오는 문자열 b에 포함되는지만 확인하면 되니까 먼저 배열을 정렬해준 뒤, 바로 옆에 있는 문자열끼리만 비교해주면 된다.

def solution(phone_book):
	answer = True
    phone_book.sort()
    
    for i in range (len(phone_book)-1):
    	if phone_book[i+1].startswith(phone_book[i]):
        	answer = False
            break
	retrun answer

 

이렇게 작성할 수 있다

 

|| 코딩 테스트를 위한 준비 ||

 

코딩 테스트를 볼 수 있는 사이트 >> 온라인 저지(프로그래모스, 백준 등등)

온라인 개발 환경 "리플릿" << 매우 유용하다

 

Replit: The software creation platform. IDE, AI, and Deployments

Run code live in your browser. Write and run code in 50+ languages online with Replit, a powerful IDE, compiler, & interpreter.

replit.com

 

 

알고리즘 성능 평가 - 알고리즘 문제를 알기 위해 알아야하는 개념

시간 복잡도 - 수행 시간 기준

공간 복잡도 - 메모리 사용향 기준

 

이들을 보통 빅오 표기법을 사용한다.

- 가장 빠르게 증가하는 항만을 고려한다.

- 즉 함수의 상한만을 나타낸다.

ex) 3N^3 + 3N^2 이면 복잡도는 O(N^3)이다.

    자세한건 아니지만 중첩을 기준으로 생각하면 편하다

        - 모든 이중for문이 O(N^2)인 것은 아니지만 대부분 O(N^2)이다. 

 

 

알고리즘 설계 Tip 

일반적으로 CPU 기반의 개인 컴퓨터에서 연산 횟수가 5억회 넘어가는 경우 

=> C언어 1-3초

=> Phthon 5-15초 (PyPy를 이용하면 더 빠르게 동작하기도 한다.)

정도의 시간이 소요된다.

 

요구사항에 따라 적절한 알고리즘 설계하기

알고리즘 문제는 시간제한이 걸려있기 때문에 고려해야한다.

시간제한이 1초인 문제를 만났을 때, 일반적으로 설계해야하는 기준은 다음과 같다.

- N의 범위가 500 => O(N^3) 인 알고리즘 설계

- N의 범위가 2,000 => O(N^2) 인 알고리즘 설계

- N의 범위가 100,000 => O(NlogN) 인 알고리즘 설계

- N의 범위가 10,000,000 => O(N) 인 알고리즘 설계

 

일반적인 알고리즘 문제 해결 과정

1. 지문 읽고 분석

2. 요구사항 분석

3. 문제 해결을 위한 아이디어 찾기

4. 소스코드 설계 및 코딩

---

|| 파이썬의 자료형 ||

 

정수형

양의 정수, 음의 정수, 0

정수 변환 int(변수)

 

 

실수형

소수점 아래의 데이터를 포함하는 수 자료형

X.X라고 작성하면 실수로 인식함

ex)

a = 5. => 5.0

a = -.7 => -0.7

 

    지수 표현 방식

 

    유효숫자e지수 = 유효숫자 X 10^지수

    ex)  1e9 = 1 X 10^9

    - 보통 임의의 큰 수를 표현하기 위해 자주 사용

        - 최단 경로 알고리즘에서 도달할 수 없는 노드에 대하여 최단 거리를 무한으로 설정

            - 이때 가능한 최댓값이 10억 미만이라면 무한값으로 1e9(10억 < 1e9)를 사용할 수 있다

 

    실수형 더 알아보기

    실수형을 저장하기 위해 4바이트 혹은 8바이트의 고정된 크기의 메모리를 할당

    => 컴퓨터 시스템은 실수 정보를 표현하는 정확도에 한계를 지님

    ex) a = 0.3+0.6 == 0.899999999

    이러한 한계를 극복하기 위해서 round()함수를 사용한다.

 

    round()함수

    round(특정숫자, 소수점 아래 어디서 반올림할건지)

 

 

수 자료형의 연산

나누기 / >> 나눠진 결과 실수

나머지 연산자 %

몫 연산자 //

거듭제곱 연산자 **

 

 

리스트 자료형

- 연결 리스트와 유사한 기능 

- C++ STL vector와도 기능적으로 유사

- 구조 : [  ,  , ...]

- 빈 배열 선언 : list() or []

- 원소 접근할 때는 인덱스 값 괄호에 넣어서 접근

    - 이를 인덱싱이라고 한다.

슬라이싱 : 대괄호 안에 콜론을 넣어 시작 인덱스와 끝 인덱스를 설정할 수 있다.

 

 

 

리스트 컴프리헨션

대괄호 안에 조건문과 반복문을 적용하여 리스트를 초기화할 수 있다.

a = [i for i in range(10)]
# => [0,1,2,3,4,5,6,7,8,9]

for문으로 하나씩 증가시키고 있는 i를 맨 앞의 i에 적어 배열의 원소로 넣는다.

 

조건문도 포함 가능하다

a = [i for i in range(20) if i%2==1]
# 20이하의 수 중에 홀수만 원소로 넣기

a = [i*i for i in range(1, 10)]
# 1에서 9까지 각각의 제곱근 원소롤 넣기

 

    nxm 크기의 2차원 배열 초기화 하기

a = [[0] * m for _ in range(n)]

 

※ 여기서 _ 는 for문에서 i를 사용할 필요없고 횟수 반복만 필요할 때 사용한다. ※

 

    리스트 관련 메소드

arr.append (원소) : 리스트에 원소 하나 삽입 || O(1)

arr.insert (삽입 위치, 삽입값) : 특정 위치에 특정 원소 삽입 || O(N)

arr.sort () : 원소 정렬 기본적으로 오름차순임 >> 내림차순은 .sort(reverse = True) || O(NlogN)

arr.reverse () :  리스트 원소 순서 뒤집기 || O(N)

arr.count(특정 값) : 배열 내의 특정값 갯수 반환 || O(N)

arr.remove(특정 값) : 배열 내 특정 값 제거 || O(N)

 

    리스트에서 특정 값을 가지는 원소 모두 제거

a = [0, 1, 2, 3, 4, 5]
remove = {2, 4}

result = [i for i in a if not in remove]
# [0, 1, 3, 5]

 

문자열 자료형

" "나 ' '로 표현

\로 " " 안에서 " "를 사용가능

ex) a = "my \"Love\"" => my "Love"

 

    문자열 연산

덧셈과 곱셉 가능

ex)

a + B => aB

A *  3 => AAA

인덱싱과 슬라이싱도 할 수 있다

단, 특정 인덱스의 값은 변경 불가하다.

 

튜플 자료형 

리스트와 비슷하지만 살짝 차이가 있다. 

인덱싱과 슬라이싱 가능

- 한번 선언된 값은 변경 불가하다

- ()로 표현한다

위의 특징 덕분에 리스트에 비해 상대적으로 공간 효율적이다.

 

    튜플을 사용하는 경우

- 서로 다른 성질의 데이터를 묶어서 관리해야할 때,

    - 최단 경로 알고리즘에서 (비용, 노드 번호)의 형태로 튜플 사용

- 데이터의 나열을 해싱의 키 값으로 사용해야할 때

    - 튜플은 변경이 불가능하기 때문에 키 값으로 사용 가능하다

- 리스트보다 메모리를 효율적으로 사용해야할 때

 

 

사전 자료형

- 키와 값의 쌍을 데이터로 가지는 자료형 >> JS의 JSON 형식과 똑같다

     - 값을 순차적으로 저장했던 리스트와 튜플과는 차이가 있음 >> 키를 지정해 값을 넣을 수 있다.

- 키로 사용하는 것은 변경 불가능한 자료형이다.

- 해시 테이블을 사용하기 때문에 데이터 조회 및 수정에 있어서 O(1)의 시간에 처리하므로 효율적이다.

 

data = dict()
data["키값0"] = "aaa"
data["키값1"] = "aaaa"
data["키값2"] = "aaaa"

# {"키값0":"aaa", "키값1":"aaaa", "키값2":"aaaaa"}

 

키 혹은 값만 뽑고 싶을 때:

    data.keys() => 키들을 반환

    data.values() => 데이터들 반환

배열로 변환 해줘야한다.

 

집합 자료형

- 중복을 허용하지 않는다

- 순서가 없다

- 리스트나 문자열을 이용해 초기화할 수 있다

    - set() 함수 사용

    - {} 안에 , 로 구분하여 삽입하며 초기화 가능

- 데이터 조회와 수정 O(1) 시간에 처리

 

합집합 A | B

교집합 A & B

차집합 A - B

을 제공한다.

 

.add(원소) : 원소 삽입

.updata([원소1, 원소2, ...]) : 여러 원소 삽입

.remove(특정 원소) : 특정 원소 제거

 

사전 자료형과 집합 자료형의 특징

순서가 없기 때문에 인덱싱으로 값을 얻을 수 없다.

    - 사전은 키를 이용해 원하는 값을 조회할 수 있고, 집합은 튜플이난 리스트로 변환하여 조회한다.

---

|| 파이썬 기초 문법 ||

 

자주 사용되는 표준 입력 방법

- input() : 한 줄의 문자열을 입력받을 때, 사용 

- map() : 리스트의 모든 원소 각각에 특정 함수를 적용할 때 사용

 

ex) list(map(int, input.split()))

받은 것(input 사용)을 공백 기준으로 나누어 배열로 만들고( split 사용 )

정수형으로 변경(map 함수 사용)

 

 

빠르게 입력받기

사용자로부터 입력을 최대한 빠르게 받아야 하는 경우

sys를 import하여 

- sys.stdin.readline() 메서드를 사용한다.

    -단, 입력을 받은 후에 줄바꿈 기호가 자동으로 입력됨으로 rstrip() 메서드를 함께 사용해준다.

import sys

inputdata = sys.stdin.readline().rstrip()

 

입력을 받는 것만으로도 많은 시간이 소요되는 경우에 사용하여 효율을 높인다

이진 탐색, 정렬, 그래프 문제에서 많이 사용

 

 

자주 사용되는 표준 출력

print()

    줄바꿈을 원하지 않을때, end 속성 이용 => print(7, end = ' ')

 

    f-string 문법

대답 = 7

print(f"문자열 사이에 {대답}을 넣어서 사용")

 

 

조건문

if 키워드를 이용해 만들 수 있음

elif == else if

else

a = 5

if a == 5:
    print("a는 5여")
elif a == 0:
    print("a는 0이여")
else :
    print("아무것도 아니여")

 

 

    파이썬의 조건문에서는 대수학에서의 부등식을 그대로 사용할 수 있다

0 < x < 10 와 같은 방식으로 조건을 설정할 수 있다 

다른 언어의 경우 위와같이 쓴다면 0 < x를 먼저 확인해서 true 혹은 false를 내보내는데 true는 1 false는 0 이므로 

무조건 10보다 작기 때문에 x가 조건에 맞지 않더라고 조건문을 실행한다.

 

    pass 키워드

아무것도 처리하고 싶을 때, pass를 사용

continue는 현재 반복문을 넘어가는 것이고 pass는 정말 아무것도 하지 않는 것이다.

 

    논리 연산자

X and Y 둘다 참이여야 참

X or Y 둘 중 하나만 참이여도 참

not X X의 반대 : true라면 false 반환 false라면 true 반환

 

 

    파이썬의 기타 연산자

x in 리스트 : 리스트 안에 x가 있으면 참

x not in 문자열 : 문자열 안에 x가 들어있지 않으면 참

 

 

    조건문의 간소화

조건문이 간소하게 한줄로 적을 수 있다면 줄바꿈을 하지 않고 작성 가능하다.

 

        조건부 표현식

if ~ else문을 한줄에 작성 가능

ex) result = "Success" if score >= 80 else "fail"

 

 

반복문

while문과 for문이 있지만  코테에서는 더 간결하고 편한 for문을 사용한다

    while 문

while 조건:

    코드

코테에서 무한루프가 나오지 않도록 만든다.

 

    for 문

for 변수 in 리스트:

    실행 코드

for 변수 in range(시작, 끝 값(실제로 순회하고 싶은 끝 값) + 1):

    실행 코드

 

- range를 사용하는 for문에서 숫자 하나면 적는다면 시작값이 디폴트로 0이되고 적은 숫자는 끝값이 된다.

- 특정 조건을 만족했을 때, for문을 탈출하고 싶다면 break를 사용하면 된다.

- 중첩해서 사용할 수 있다

 

 

함수와 람다 표현식

함수의 종류

- 내장 함수

- 사용자 정의 함수

 

함수 정의하기

반복적으로 사용되는 코드를 함수로 만들어 소스코드의 길이를 줄일 수 있다.

def 함수이름(매개변수):
    실행 코드
    return 반환 값

리턴 값이 존재하지 않아도 된다.

 

    global 키워드

함수 바깥에서 선언된 변수를 함수 안에서 사용하고 싶을때 함수 내에서 global을 붙여서 가지고 온다.

a = 10

def func():
    global a
    print(a)

func()

 

전역 변수로 설정된 리스트 객체는 global 키워드가 없어도 참조할 수 있다.

 

- 여러개의 반환 값을 가질 수 있다.

여러개를 반환 하는 것을 테킹 순서에 맞게 결과값을 담는 것을 언테킹이라고 한다

 

람다 표현식

람다 표현식을 이용해 함수를 간단하게 작성

    - 특정한 기능을 수행하는 함수를 한 줄에 작성할 수 있다.

print((lambda a, b : a + b)(3, 7))

# 위의 방식은

def add(a, b):
    return a+b

# 와 같다

 

 

보통 정렬함수에서 많이 사용하기도 한다.

 

여러개의 리스트에 동일한 규칙을 적용시킬 때도 사용한다

list1 = [1, 2, 3, 4, 5]
list2 = [6, 7, 8, 9, 10]

result = map(lambda x y : x + y, list1, list2)

실행 결과 [7, 9, 11, 13, 15]

 

 

자주 사용되는 표준 라이브러리

• itertools : 순열(permutations)과 조합(combinations) 라이브러리가 포함되어있다.
• heepq : 힙의 자료구조를 제공 >> 우선순위 큐 기능을 구현하기 위해 사용
• bisect : 이진 탐색 기능 제공
• collections : 덱, 카운터 등의 자료구조 포함
• math : 필수적인 수학적 기능 제공 >> 팩토리얼, 제곱근, 최대공약수, 삼각함수 관련함수 혹은 파이와 같은 상수 포함

    자주 사용되는 내장 함수

• sum 함수 : 리스트나 튜플이 들어왔을 때, 합 반환
• min, max 함수 : 가장 작은 값 혹은 작은 값 반환
• eval 함수 : 문자열 내 수식을 계산하여 반환
• sorted() :
  • 오름차순
  • 내림차순 >> sorted(배열, reverse = True)
  • 키 속성으로 정렬 기준 설정이 가능하다

array = [('홍길동', 89), ('이순신', 77), ('아무개', 40)]
sorted(array, key = lambda x : x[1] )

 

    순열과 조합

- 순열 : 서로 다른 n개에서 서로 다른 r개를 선택하여 일렬로 나열 >> 순서가 있다

from itertools import permutations

data = ['A', 'B', 'C']

result = permutations(data, 몇개 선택한건지 설정 if 3)
print(result)

 

- 조합 : 서로 다른 n개에서 순서 상관없이 서로 다른 r 선택 >> 순서가 없다

from itertools import combinations

result = combinations(data, 뽑는 개수 if 2)
print(result)

 

중복 순열 : product

중복 조합 : combinations_with_replacement

 

Counter  

등장 횟수를 세는 기능

 

 

최대 공약수와 최대 공배수

import math

a = 21
b = 14

print(math.gcd(21, 14)) # 최대 공약수
print(lcm(21, 14)) # 최대 공배수 

det lcm(a, b):
    return a * b / math.gcd(a, b)