분류 전체보기
[백준/1874/파이썬] 스택 수열
https://www.acmicpc.net/problem/1874 1874번: 스택 수열 1부터 n까지에 수에 대해 차례로 [push, push, push, push, pop, pop, push, push, pop, push, push, pop, pop, pop, pop, pop] 연산을 수행하면 수열 [4, 3, 6, 8, 7, 5, 2, 1]을 얻을 수 있다. www.acmicpc.net 조건 1~N 까지 수를 스택에 넣었다가, 뽑아서 늘어놓음으로써, 하나의 수열을 만들 수 있다. 해당 수열을 오름차순으로 stk에 PUSH,POP을 통해서 만들 수 있는 수열이 있음 . 임의의 수열이 주어졌을 떄, 스택을 이용해서 그 수열을 만들 수 있는지 없는지, IF possible) 어떤 순서로 push와 pop..
[백준/1918/파이썬] 후위 표기식(postfix)
https://www.acmicpc.net/problem/1918 1918번: 후위 표기식 첫째 줄에 중위 표기식이 주어진다. 단 이 수식의 피연산자는 알파벳 대문자로 이루어지며 수식에서 한 번씩만 등장한다. 그리고 -A+B와 같이 -가 가장 앞에 오거나 AB와 같이 *가 생략되는 등의 www.acmicpc.net 조건 중위 표기식을 후위 표기식으로 바꾸세요! -A+B와 같이, - 가 가장 앞에 오거나, AB와 같이 *가 생략되는 등의 수식은 주어지지 않음. 표기식은 +,-,*,/,(,)로만 이루어져 있으며, 길이는 100을 넘지 않음. 입력 IN: A*(B+C) Out: ABC+* IN : A+BC Out: ABC+ SOl) 일단, 후위 표기식은 진짜 Stack의 스테디 셀러 같은 느낌이라, Stack..
[알고리즘,개념,활용] 길을 찾자!
이 글은 BFS/DFS에 대한 저의 이해를 기록한 글 입니다. 사람마다 이해하는 방법이 다를 수 있으니, 너그러운 시선으로 봐주세요! 대신, 틀린 부분이 있다면, 거침없이 지적/tackle해주세요 ! 경로 찾기 문제 알고리즘 문제를 풀다보면 , BFS 관련해서 자주 등장하게 되는게 , 길찾기 문제이다. 이 길찾기 문제에 대해서, 하나하나 뜯어볼 생각이다. 왜 BFS,DFS는 경로 찾기 문제에 쓰일까 당연하다. BFS, DFS는 완전 탐색 알고리즘 중, 하나이고 모든 경우의 수를 보는 알고리즘이기 때문에, 답을 못찾을 수가 없다고 말하면 알고리즘을 배우는 의미가 없으니까 , 말해주면 길찾기 문제의 Map을 그래프 관계로 나타낼 수 있고, 이 배열을 하나하나 다 순회하면서 탐색하는것보단, BFS,DFS로 쭊..
[백준/1743/파이썬] 음식물 피하기
https://www.acmicpc.net/problem/1743 1743번: 음식물 피하기 첫째 줄에 통로의 세로 길이 N(1 ≤ N ≤ 100)과 가로 길이 M(1 ≤ M ≤ 100) 그리고 음식물 쓰레기의 개수 K(1 ≤ K ≤ N×M)이 주어진다. 그리고 다음 K개의 줄에 음식물이 떨어진 좌표 (r, c)가 주어진다 www.acmicpc.net 조건 - 음식물들은 근처에 있는 것끼리 뭉치게 돼서 , 큰 음식물 쓰레기가 된다. - N*M 행렬, 음식물 쓰레기의 좌표가 입력됨. 입력 - Test 케이스 3 4 5 3 2 2 2 3 1 2 3 1 1 Output:4 SOL) 이 문제에서 핵심은 음식물 쓰레기가 모여있다는 개념을 잘 이해하는거다. 테스트 케이스에서, 아래와 같은 상황일 때, 큰 음식물 사..
[백준/1406/파이썬] 에디터
https://www.acmicpc.net/problem/1406 1406번: 에디터 첫째 줄에는 초기에 편집기에 입력되어 있는 문자열이 주어진다. 이 문자열은 길이가 N이고, 영어 소문자로만 이루어져 있으며, 길이는 100,000을 넘지 않는다. 둘째 줄에는 입력할 명령어의 개수 www.acmicpc.net 조건 영어 소문자가 input으로 옴. 최대 60,000글자 'Cusor'가 있는데, 커서는 문장의 맨앞, 맨뒤 또는 문장의 임이의 곳에 위치할 수 있음. 길이가 L인 문자열이 편집기에 있으면, L+1가지 경우가 있음. 이 편집기가 지원하는 명령어 L: 커서를 왼쪽으로 한 칸 옮김.( 커서가 맨 앞이면, 무시) D:커서를 오른쪽으로 한 칸 옮김.(커서가 맨 뒤면 , 무시) B 커서 왼쪽에 있는 문자..
[개념/파이썬/알고리즘] BFS(Breadth First Search)
BFS 한 경우에 대한, 모든 가능한 경우의 수를 탐색한다. Queue를 이용한다. 최단거리(최단경로)를 탐색하는 대표적인 알고리즘 중 하나이다. 완전탐색 알고리즘 중 , 하나이다. 방문했던 Node는 방문하지 않는다. Web crawling,SNS,Network broadcasting,grabage collection 등에 이용된다고 합니다. 순서: A->B->C ->D ->E->F ->G ->H ->J -> J -> K BFS는 큐를 사용합니다! Queue를 이용해서, 어떻게 탐색하는지 봅시다. 큐에서도 2가지 동작이 있습니다. popleft: 큐의 왼쪽에서 노드를 꺼냅니다. appendleft:큐의 왼쪽에 노드를 추가합니다. popleft 하면서, 자식 노드들을 추가하면서, 하나하나씩 출력합니다! ..
[개념/파이썬/알고리즘] DFS (Depth First Search)
그래프를 배우게 되면, 제일 처음 배우게되는 일종의 정립되고, 문제에서 아주 자주나오는 스테디셀러인 친구들이 있다. DFS , BFS가 뭔지 살펴보기 전에, DFS,BFS는 완전탐색알고리즘이고, 가능한 수를 전부 다 뒤지는 알고리즘의 일종이다.그래서, 느리지만, 정답을 무적권 찾을수 있다는 기본적인 특성이 있기 때문에, 이건 알고가자. 오목을 한다고 생각해보자! 여러분은 백돌이고, 여러분의 차례이다. 그럼 , 어디를 막을 수 있을까? 생각을 하게 될것이다. 여러분은, 위와 깉이 다양한 경우의 수를 생각하면서, 오목을 할 것이다. 그럼 , 이때, 여러분의 생각의 방식에 따라서, 2가지로 나눌 수 있다. 첫번째. 1가지의 경우에 대해서 생각한 뒤, 그 경우일 때, 일어나는 경우를 계속 생각하는 방법 . 오목..
[개념,그래프] 인접행렬 ,인접리스트 - 그래프를 코드로 !
그래프의 개념은 뭔지 알았으니, 이제 그걸 코드로 구현해보는 연습을 해보자. 2가지 방법이 있는데, 각각의 장/단점은 뭐고, 어떨때 쓰면 이득인지 알아봅시다. 사실 그래프의 종류는 워낙 많아서, 나중에 차근차근 더 살펴보는 걸로 하자. 언어 : Python 1. 인접 행렬 Vertex * Vertex 크기 만큼 행렬을 만들어서, 그 두개의 Vertex가 Edge로 이어져있다면 1 , 아니면 0을 넣어 그래프를 표현하는 방식이다. 인접 행렬로 구현을 할 경우, 그래프(무방향의 한해서) 대각 성분을 기준으로 대칭인 성질을 갖게된다 위의 그래프를 인접행렬로 생각한다면, 옆의 그림과 같이 될것임. 그럼 이걸 코드로 어떻게 구현할까. 보통, 문제에서는 구성하는 정점의 개수(Vertex),간선의 개수(Edge), ..