Python TMI

String 조회 # x의 첫 번째 위치 반환. 없으면 -1 리턴 .find(x) # x의 첫 번째 위치 반환. 없으면 오류 발생시킴 .index(x) 바뀐 결과의 String을 리턴 # 바꿀 대상 글자를 새로운 글자로 바꿔서 반환. # count를 지정하면 해당 갯수만큼만 시행. .replace(old, new[, count]) # 특정한 문자를 양쪽에서 제거하거나 왼쪽에서 제거하거나(lstrip), 오른쪽을 제거(rstrip). # 지정하지 않으면 공백을 제거 .strip([chars]) # 문자열을 특정한 단위로 나누어 리스트로 반환 .split(sep=None) # 앞글자를 대문자로 만들어 반환 .capitalize() # 어포스트로피나 공백 이후를 대문자로 만들어 반환 .title() # 모두 ..

BFS(너비 우선 탐색) 시작 노드부터 출발해서 가까운 노드부터 우선적으로 탐색하는 형태 큐 자료 구조를 이용한다는 점이 특징 시작 노드를 큐에 넣고 방문 처리를 해야 합니다. 큐에서 노드를 꺼낸 뒤에 그 꺼낸 노드에 인적 노드 중에서 방문하지 않은 노드를 모두 취해놓고 방문 처리를 수행. bfs는 해당 시점에서 인접한 노드를 한 번에 전부 큐에 넣는다는 점이 특징 큐를 위해서 하나의 deque 라이브러리를 부르자. dfs 때와 마찬가지로 이 0번 노드에 대한 내용을 비우고 8개의 노드를 모두 처리할 수 있도록 총원소가 9개인 리스트 객체를 만들어 그래프를 표현해준다. 그래서 1번 노드는 2, 3, 8번 노드와 인접해 있고 2번 노는 1, 7번 노드와 인접해있다. 방문 처리 목적으로 visited라는 이..

DFS(깊이우선탐색) dfs는 이름에서부터 알 수 있듯이 깊이를 우선으로 하여 탐색하는 알고리즘. dfs를 구현하고자 할 때는 스택 자료구조 혹은 재귀 함수를 이용. 먼저 탐색을 시작할 노드를 스텍에 넣고 방문 처리. 스택의 최상단 노드에 방문하지 않은 인접 노드가 하나라도 있다면 그 노드 또한 스택에 넣고 방문 처리. 혹은 만약 스택에 최상단 노드에 방문하지 않은 인접 노드가 없으면 그냥 스택에서 해당 노드를 꺼내면 된다. 이러한 과정을 더 이상 수행할 수 없을 때까지 반복. 어떤 노드부터 방문할지를 결정하기 위한 기준은 문제에서 요구하는 내용에 따라서 달라질 수 있고 어떤 노드부터 방문하더라도 상관이 없는 경우도 있다. 흔히 번호가 낮은 로드부터 방문한다고 가정하고 설명을 진행하는 경우가 많다. 파이..

DFS, BFS 공부 전에 알아야 할 것 Stack 자료구조 입구와 출구가 동일한 형태로, 선입후출 자료구조. Python에서는 다른 표준 라이브러리를 이용할 필요 없이 리스트 자료형을 이용하여 스택을 구현한다. 가장 오른쪽에 자료를 산입하는 append()와 가장 오른쪽에서 하나의 원소를 꺼내는 pop()를 지원하는데, 이를 그대로 이용해서 스택과 같이 사용할 수 있다. 나중에 모든 작업이 끝난 후 스택을 출력할 땐, 최상단 원소부터 출력하려면 [::-1]을 통해 출력해야한다. Queue 자료구조 선입선출의 자료구조, 차례대로 작업을 시행하는 대기열을 나타내고자 할 때 사용. 큐 자료구조를 Python에서 이용하고자 할 땐 deque(덱) 라이브러리를 사용하면 된다. Stack과 같이 리스트 자료형으로..

2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어 www.acmicpc.net 문제 신종 바이러스인 웜 바이러스는 네트워크를 통해 전파된다. 한 컴퓨터가 웜 바이러스에 걸리면 그 컴퓨터와 네트워크 상에서 연결되어 있는 모든 컴퓨터는 웜 바이러스에 걸리게 된다. 예를 들어 7대의 컴퓨터가 과 같이 네트워크 상에서 연결되어 있다고 하자. 1번 컴퓨터가 웜 바이러스에 걸리면 웜 바이러스는 2번과 5번 컴퓨터를 거쳐 3번과 6번 컴퓨터까지 전파되어 2, 3, 5, 6 네 대의 컴퓨터는 웜 바이러스에 걸리게 된다. 하지만 4번과 7번 컴퓨터는 1번 컴퓨..

list.append(x)는 list의 끝에 1개의 x를 집어넣는다. list.extend(iterable)는 list의 끝에 iterable의 모든 항목을 집어넣는다. append() x = ['Hi', 'Hello', '안녕'] y = ['나는', '파이썬'] x.append(y) print(x) ['Hi', 'Hello', '안녕', ['나는', '파이썬']] extend() x = ['Hi', 'Hello', '안녕'] y = ['나는', '파이썬'] x.extend(y) print(x) ['Hi', 'Hello', '안녕', '나는', '파이썬'] 만약 리스트가 아닌 문자열 형태가 된다면 아래와 같습니다. append() x = ['Hi', 'Hello', '안녕'] y = '나는 파이썬' x...

그래프 탐색 하나의 정점에서 시작하여 모든 정점을 한 번씩 방문하는 것 예) 회로에서 특정 단자와 단자가 연결되어있는지 너비우선탐색(BFS, Breadth-First Search) 임의의 노드에서 시작하여 인접한 노드를 탐색하는 방법. 시작 노드에서 부터 가까운 노드를 먼저 방문하고 멀리 떨어진 정점은 나중에 방문하는 순회방법. 두 노드사이의 최단경로를 찾아야하거나 임의 경로를 찾고싶을 때 사용. 어떤 노드를 방문했는지 반드시 검사해야 한다. 하지 않으면 무한루프에 빠질 수 있다. BFS는 차례로 저장하고 꺼낼 수 있는 큐를 사용하여 선입선출 원칙으로 탐색한다. BFS는 방문 노드의 인접한 노드를 큐에 저장하는 것이 DFS와 다른 점. 🔽 REFERENCE 알고리즘 - BFS(너비 우선 탐색) 이번에 살..

17298번: 오큰수 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다. www.acmicpc.net 문제 크기가 N인 수열 A = A1, A2, ..., AN이 있다. 수열의 각 원소 Ai에 대해서 오큰수 NGE(i)를 구하려고 한다. Ai의 오큰수는 오른쪽에 있으면서 Ai보다 큰 수 중에서 가장 왼쪽에 있는 수를 의미한다. 그러한 수가 없는 경우에 오큰수는 -1이다. 예를 들어, A = [3, 5, 2, 7]인 경우 NGE(1) = 5, NGE(2) = 7, NGE(3) = 7, NGE(4) = -1이다. A = [9, 5, 4, 8]인 경우에는 NGE(1) = -1, ..

17608번: 막대기 아래 그림처럼 높이만 다르고 (같은 높이의 막대기가 있을 수 있음) 모양이 같은 막대기를 일렬로 세운 후, 왼쪽부터 차례로 번호를 붙인다. 각 막대기의 높이는 그림에서 보인 것처럼 순서대로 www.acmicpc.net 문제 아래 그림처럼 높이만 다르고 (같은 높이의 막대기가 있을 수 있음) 모양이 같은 막대기를 일렬로 세운 후, 왼쪽부터 차례로 번호를 붙인다. 각 막대기의 높이는 그림에서 보인 것처럼 순서대로 6, 9, 7, 6, 4, 6 이다. 일렬로 세워진 막대기를 오른쪽에서 보면 보이는 막대기가 있고 보이지 않는 막대기가 있다. 즉, 지금 보이는 막대기보다 뒤에 있고 높이가 높은 것이 보이게 된다. 예를 들어, 그림과 같은 경우엔 3개(6번, 3번, 2번)의 막대기가 보인다. ..

1100번: 하얀 칸 체스판은 8*8크기이고, 검정 칸과 하얀 칸이 번갈아가면서 색칠되어 있다. 가장 왼쪽 위칸 (0,0)은 하얀색이다. 체스판의 상태가 주어졌을 때, 하얀 칸 위에 말이 몇 개 있는지 출력하는 프로그램 www.acmicpc.net 문제 체스판은 8*8크기이고, 검정 칸과 하얀 칸이 번갈아가면서 색칠되어 있다. 가장 왼쪽 위칸 (0,0)은 하얀색이다. 체스판의 상태가 주어졌을 때, 하얀 칸 위에 말이 몇 개 있는지 출력하는 프로그램을 작성하시오. 입력 첫째 줄부터 8개의 줄에 체스판의 상태가 주어진다. ‘.’은 빈 칸이고, ‘F’는 위에 말이 있는 칸이다. 출력 첫째 줄에 문제의 정답을 출력한다. 예제 입력 1 .F.F...F F...F.F. ...F.F.F F.F...F. .F...F...