[ASAC 8일차] 특강, 탐색: DFS, BFS

4월 1일의 기록

 

오전에는 간단한 특강이 예정되어 있었다. 주말에 날이 너무 좋아서 한강에서 좀 놀았더니, 풀어봐야 했던 문제를 풀지 못했다. 그래서 조금 더 일찍 와서 아침부터 문제를 풀어보았다.

0. 목차

1. 특강: 데이터 분석가는 무엇을 하는가
2. stack/queue 리뷰
3. 연습문제 : 미로 탐색(백준 2178)
4. 구현_카카오2022_주차요금문제

 

1.  특강) 데이터 분석가는 무엇을 하는가

---

1-1. 업의 본질

데이터 분석가란?

• ‘데이터’를 ‘분석’ 하는 ‘모든’ 사람

그렇다면 분석가의 본질은 무엇인가?

1. 분석 / 기획 / 환경 구축
2. 즉, 문제점 분석하는 과정과 세운 가설이 논리적으로 설득되는 부분인지가 제일 중요한 부분이다.

1-2. 실습

google merchandise store 의 Google analytics 지표를 확인해보면서 문제점을 찾고

이를 바탕으로 목표 개선을 위한 기획서를 간단하게 작성해보자

 

목표:  google merchandise store 다음 한달의 수익을 높이기

Action: 상품 Super G Timbuk2 Recycled Backpack의 프로모션을 통해 google merchandise store의 수익을 높이자.

KPI :
1. 다음달 Super G Timbuk2 Recycled Backpack의 상품 조회수 3000회 달성
2. Super G Timbuk2 Recycled Backpack의 구매 전환율 3% 달성

 

가설 및 근거

아래 사진을 참고해서 실제 상품 수익을 기준으로 보면 가장 많은 수익을 올린 상품은 Super G Timbuk2 Recycled Backpack이다. 

따라서, Super G Timbuk2 Recycled Backpack의 프로모션을 통해 구매 전환율을 높이면 매출 상승에 기여할 수 있을 것이다.

 

1위 상품은 8천 조회수 정도가 나오므로 1위 상품만큼 상품 조회수를 올리면서 평균 구매 전환율 2%의 가드레일 지표를 달성한다고 가정하면 해당 상품을 60개를 더욱 판매할 수 있을 것이라고 예측할 수 있으며 이에 따라 높은 수익을 얻을 수 있을 것이다.

 

2. stack/queue 리뷰

---

2-1. stack / queue

1. stack
   1. 가장 최근에 들어온 데이터가 가장 먼저 나간다! (LIFO)
   2. 자료의 출력 순서가 입력 순서의 역순으로 이루어질 때 아주 요긴하게 사용되는 자료구조
2. queue
   1. 가장 먼저 들어온 데이터가 가장 먼저 나간다! (FIFO)
   2. 말 뜻 그대로 '표를 사기 위해 줄을 서는 사람들'을 생각

2-2. 탐색 : 내가 방문할 곳, 방문한 곳

• 처리방식 :
  • Stack ⇒ 뒤 : 할일에 최신, DFS (재귀함수 O)
  • Queue ⇒ 앞: 일단 앞에서, BFS (재귀함수 x)
  참고 ) 다양한 지도/상황/전제조건 —> 여러 문제!→ 좌표 평면 : 좌표→ 경우의 수 : 다양하게… (효율성 : 필요없으면 Cut)
• → 지도 : 인접행렬, 인접 리스트(리스트, dict, etc)
• 판 모양 : 지도(점/선), 좌표 평면(미로), 경우의 수

2-3. BFS( Breadth First Search)

기본 원리 및 동작

• 기본적인 동작 : 가까운 노드부터 탐색하는 알고리즘이며(→ 그렇기 때문에 아래로 들어가는 것이 아니라 같은 level 에 있는 것부터, 수평적인 탐색이 된다..), 이미지 적으로는 수평적인 방향으로(동일 레벨을 기준으로 먼저 탐색) 탐색을 하는 과정임.

잠시) deque에 대해서...

• collections 패키지에서 구현한 deque 라는 자료형태가 있음.
  • Stack과 Queue 기능을 모두 가진 객체로 출입구를 양쪽으로 가지고 있는 것
  • Stack,. Queue 모두 필요에 따라서 사용할 수 있는 기능을 제공하고 있어서, 특히 Queue에 대해서 할 때 주로 많이 사용을 하는 부분임.
• 아래 그림과 같이 앞뒤에 다 출입구가 있는 경우라고 개념을 잡으면 된다.

[ deque 주요 기능들 ]

deque.append(item): item을 데크의 오른쪽 끝에 삽입

deque.appendleft(item): item을 데크의 왼쪽 끝에 삽입

deque.pop(): 데크의 오른쪽 끝 엘리먼트를 가져오는 동시에 데크에서 삭제

deque.popleft(): 데크의 왼쪽 끝 엘리먼트를 가져오는 동시에 데크에서 삭제

deque.extend(array): 주어진 배열(array)을 순환하면서 데크의 오른쪽에 추가

deque.extendleft(array): 주어진 배열(array)을 순환하면서 데크의 왼쪽에 추가

deque.remove(item): item을 데크에서 찾아 삭제

deque.rotate(num): 데크를 num만큼 회전한다(양수면 오른쪽, 음수면 왼쪽)

 

 

참고 ) 다양한 지도/상황/전제조건 —> 여러 문제!

• 판 모양 : 지도(점/선), 좌표 평면(미로), 경우의 수
  • 지도 : 인접행렬, 인접 리스트(리스트, dict, etc)
  • 경우의 수 : 다양하게… (효율성 : 필요없으면 Cut
  • 좌표 평면 : 좌표

Deque 사용 예제 코드

from collections import deque

# deque만들기
dq = deque("coding")
dq

# stack 구현
dq.append("a")
dq
dq.pop()
dq

# queue 구현
dq.appendleft("a")
dq
dq.pop()
dq

# deque 확장 : extend, extendleft
dq.extend("test")
dq

dq.extendleft("x")
dq

# 주의사항!!!) 여러개의 덩어리를  할 때 순서가 뒤집어서 들어감!!!
dq.extendleft("abc")
dq

dq.extendleft(["A","B"])
dq

# dequeu를 리스트처럼 중간에 대새허 할 때 : insert, remove
dq[1] = "XX"
dq

dq.insert(0, "AAAA")
dq

dq.remove("XX")
dq

# deque에 대한 반전
dq.reverse()
dq

 

참고) 일반적인 list와 비교해서 deque가 속도가 얼마나 빠른지에 대한 간략 비교

stack보다는 queue의 구현에서 특히나 많은 시간차이가 발생을 하며, 그 이유는 list.pop( 0 ) 을 하면서 리스트에 대해서 메모리를 재할당을 하기때문에 queue에서 시간의 차이가 많이 발생을 한다.

 

DFS와 BFS의 차이

 

상황별 접근 알고리즘

 

3. 연습문제 : 미로 탐색(백준 2178)

---

 

[문제 상황]

문제 상황

[입력 조건]

첫째 줄에 두 정수 N, M(2≤N, M ≤1000)

- 다음 N개의 줄에는 M개의 정수로 미로가 주어짐

- 각각의 수들은 붙어서 입력으로 주어진다.!!!

- 그리고 항상 도착위치로 이동할 수 있는 경우에만 입력으로 주어짐. [출력조건]

- 첫재 쭐에 지나야 하는 최소의 칸 술을 출력함.

입력 예시

 

작성 코드

 

# 실제 탐색에 대한 구현
# 2차원 LRUD에 대한 움직임!!! : 좌표를 도입할까
# 1칸씩 움직인다고 하는게 LRUD
# dict, dx/dy list etc
# 이 문제에서는 LRUD 구별을 하지 않음 
# L자 이동처럼 그냥 4가지 이동에 대한 표현만 하면 됨.
from collections import deque

# 입력값에 대해서 처리 : 2차원 움직임에 대한 세팅
n, m = map(int, input().split(" "))
graph = []
for i in range(n):
    graph.append( list( map(int,input())))
def bfs_miro(start): # 처음 출발 위치 --> 문제상 (1,1)로 파이썬(0,0)
    # 기본 세팅
    # 1-1) 할 일 : q --> deque(큐) [(x_pos,y_pos)]
    # 1-2) 한 일 : 거리 -> graph에 직접! : 즉, 세팅 필요 없다.
    ##### ----> 1-1에 대한 구체화 작업
    dx = [-1, 1, 0, 0]
    dy = [ 0, 0, 1, -1]
    x_pos = start[0]
    y_pos = start[1]
    # 문제상 (1,1)을 파이썬에서 0,0으로 바꿔서 계산

    # To Do List
    q = deque()


    # 2) 초기화 : 출발점에 대한 할 일 추가
    # 할 일에 대한 초기화
    q.append((x_pos, y_pos))

    # 출발점 좌표를 가지고 할 일을 시작

    while q:
        #어디로 갈까 ==> BFS 큐 앞에서 뽑아라
        now_x, now_y = q.popleft()

        # 앞에서 1번 도시에서 연결된 도시 순회가 
        # 지금 위치에서 LRUD 이동 순회로 변경된다.
        for i in range(4):
            next_x = now_x + dx[i]
            next_y = now_y + dy[i]
            
            # --> next_node를 떙겨오는건데, 좌표로 순회
            # 체크 1) 인바운드!! in/out 체크
            if 0 <= next_x < n and 0 <= next_y < m: #파이썬 기준 인덱스
                # 지도 안쪽에 있을 때 이동이 가능한 경우
                # # 체크 2) 내가 온 곳이 처음 방문한 곳인지?
                if graph[next_x][next_y] == 1:
                    # 값을 갱신 !! 기준은 (지금값 + 1)
                    graph[next_x][next_y] = graph[now_x][now_y] + 1
                    # 여기서 또 할일을 주어야 한다.
                    # LRUD 이동해서 갈 수 있으면 가봐!
                    q.append((next_x,next_y))
                else:
                    pass
            else:
                pass

    return graph[n-1][m-1]
print(bfs_miro((0,0)))



# 출발점에서 한 단계씩 할 일을 해야하므로 : bfs
# ==> 큐 방식으로 할 일을 선택한다.

 

 

4. 구현_카카오2022_주차요금문제

---

https://dongdong-hoon.tistory.com/47

[Programmers][stack] 주차 요금 계산

작성한 코드와 풀이 주석은 위 블로그 글에서 함께 확인할 수 있다.