전체 글

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..

[운영체제 메모리관리] 메모리 구조(Memory Structure)

메모리 구조란? 프로그램이 실행되기 위해서는 먼저 프로그램이 메모리에 로드(load)되어야 합니다. 또한 프로그램에서 사용되는 변수들을 저장할 메모리도 필요합니다. 따라서 컴퓨터의 운영체제는 프로그램의 실행을 위해 다양한 메모리 공간을 제공하고 있다. 프로그램이 운영체제로부터 할당받는 대표적인 메모리 공간(RAM)은 다음과 같습니다. 코드(code) 영역 데이터(data) 영역 힙(Heap) 영역 스택(Stack) 영역 코드(Code) 영역 메모리의 코드(code) 영역은 실행할 프로그램의 코드가 저장되는 영역으로 텍스트(code) 영역이라고도 부릅니다. 실행할 프로그램의 코드는 프로그래머가 작성한 소스 코드입니다. 프로그램이 시작하고 끝날 때까지 메모리에 계속 남아있습니다. 또한 상수도 여기에 들어갑니..