알고리즘

KMP알고리즘 개념 정리

KMP알고리즘 이해가 안되어서, 정리가 잘 된 블로그를 찾다가 깔끔하게 설명해주시는 블로그 URL을 첨부합니다. KMP알고리즘에 대해 정말 자세하고 이해하기 쉽게 설명되어있습니다. 이글 정독 2번하면, KMP 이해는 다 되고 코드 작성까지 스스로 완벽하게 하실 수 있으실거라고 생각합니다. bowbowbow.tistory.com/6 KMP : 문자열 검색 알고리즘 문자열 검색이 뭐지? 워드프로세서를 사용할 때 찾기 기능을 사용한적 있을 겁니다. 브라우저에서도 Ctrl+F 단축키를 눌러 검색할 수 있습니다. 아래 이미지는 브라우저에서 "테이프"를 검색했 bowbowbow.tistory.com

[백준 2178] 미로 탐색 Swift

www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 이번 문제는 단순한 BFS, DFS탐색 문제입니다. 기본 문제이지만, Swift 언어 활용을 위해 풀어보려고 합니다. 최소 거리는 BFS탐색을 이용해서 자주 풀기 때문에 BFS코드로 풀었습니다. map함수는 갈 수 있는 곳 1과 갈 수 없는 곳 0으로 입력으로 받았고요. check함수는 방문했는지 여부, distance는 최소거리를 구하기 위해 사용했습니다. 주의 해야할 점은 입력값의 map이 숫자가 붙어서 나오는데, Swift는 readLi..

[백준 11724] 연결 요소의 개수 C++

https://www.acmicpc.net/problem/11724 11724번: 연결 요소의 개수 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주�� www.acmicpc.net 이번 시간은 그래프의 기본인 연결 요소의 개수를 구하는 문제의 풀이법을 설명하겠습니다. 문제에서 조건은 방향이 없는 그래프라고 말하고 있습니다. 입력으로 정점의 개수 N과 간선의 개수 M을 입력받고요, 연결된 요소가 총 몇개 있는지 구하는 문제입니다. 이 문제는 DFS, BFS로 어느것으로 풀어도 되지만, 저는 DFS를 이용해서 깊..

[백준 16929] Two Dots C++

https://www.acmicpc.net/problem/16929 16929번: Two Dots 첫째 줄에 게임판의 크기 N, M이 주어진다. 둘째 줄부터 N개의 줄에 게임판의 상태가 주어진다. 게임판은 모두 점으로 가득차 있고, 게임판의 상태는 점의 색을 의미한다. 점의 색은 알파벳 대문�� www.acmicpc.net 이번 시간은 Tow Dots 문제 풀이법에 대해 설명드리겠습니다. 같은 색깔에 한해서 Circle이 존재하느냐를 찾는 문제입니다. 그래프 탐색 알고리즘인 BFS와 DFS 중 어떤 것을 사용하면 좀 더 효율적으로 사용할지 고민하다가 DFS 깊이 탐색으로 일정하게 쭉 들어가면서 탐색하면 될 것이라고 생각했습니다. DFS를 구현하는 방법은 대표적으로 2가지가 있습니다. 1. Stack을 이..

[백준 2667] 단지번호붙이기 C++

https://www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집들의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. � www.acmicpc.net 안녕하세요. 현's story 입니다. 이번 시간에는 단지번호붙이기 풀이법에 대해 설명해드리겠습니다. 이 문제의 경우 여러가지 변형된 문제를 다수 풀어본 경험이 있습니다. 자신감(?)에 넘쳐서 바로 풀었더니!!!땅 하고 프로그램이 안돌아가더라고요.. 다시 주의깊게 보니까 입력이 변수 간에 서로 띄워져있지 않고 모두 붙여져 있는 형태로 입력이 들어오기 때문에 한자리만 입력받을 필요가 생겼습니다. i..

[백준 17090] 미로 탈출하기 C++

https://www.acmicpc.net/problem/17090 17090번: 미로 탈출하기 크기가 N×M인 미로가 있고, 미로는 크기가 1×1인 칸으로 나누어져 있다. 미로의 각 칸에는 문자가 하나 적혀있는데, 적혀있는 문자에 따라서 다른 칸으로 이동할 수 있다. 어떤 칸(r, c)에 적힌 문� www.acmicpc.net 오늘은 Gold 2 난이도를 가지는 미로 탈출하기 문제 풀이를 하려고 합니다. Gold 2난이도라고 해서 큰 맘먹고 문제를 풀었는데, 생각외로 10분만에 문제를 풀어버렸습니다.. 대단한건아니지만....문제 길이도 짧고 규칙성을 바로 찾아서 바로 풀게 되었습니다. 문제에서 각 적힌 칸에서 U, R, D, L, 문자 그대로 (Up, Right, Down, Left)방향으로 이동해서 ..