분류 전체보기

https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 배열로 입력이 들어오고 하나 하나 찾아가는 느낌이 그래프와 BFS 로 풀면 되겠다고 생각했습니다. 토마토는 익은 토마토 주변 상하좌우로 안 익은 토마토들을 익게 만드는 것 또한 BFS 라고 생각했습니다. 여기에서 문제는 끝까지 탐색했을 때 모든 토마토가 안 익는 경우가 생기고 이를 어떻게 일반적인 경우와 구분할 것 인지 탐색이 끝까지 진행 되었을 때 며칠이 지났는지 어떻게 알 수 ..

https://www.acmicpc.net/problem/5430 5430번: AC 각 테스트 케이스에 대해서, 입력으로 주어진 정수 배열에 함수를 수행한 결과를 출력한다. 만약, 에러가 발생한 경우에는 error를 출력한다. www.acmicpc.net 리스트를 만들어 요소들을 저장하고 각 명령에 맞게 리스트의 값들을 수정하는 문제입니다. 해당 문제에는 2 가지의 명령이 있습니다. R: 배열의 순서를 뒤집습니다. D: 가장 앞에 요소를 삭제합니다. 만약 배열에 요소가 없을 때, D 명령을 수행하려 하면 error 를 출력하고 아닐 경우는 결과 배열을 출력합니다. 특이한 점은 배열의 요소들을 입력해줄 때 [ ] 를 포함하여 입력해준다는 점 입니다. [ ] 처리를 잘 하는 것이 중요해보입니다. 또한 R 연..

자료구조 수업을 바탕으로 저의 생각을 정리하는 글 입니다. 0. String Matching 긴 텍스트형식의 문자열에서 패턴을 찾아주는 것을 말합니다. 생각보다 실생활에 많이 쓰입니다. 워드에서 ctrl+F 를 통해 원하는 단어를 찾는 것웹 페이지에서 원하는 검색어를 갖는 페이지를 찾아주는 것생명공학에서 DNA 염기 서열 중 원하는 염기 서열을 찾아주는 것etc...String Matching 에 사용되는 용어들과 문제를 재정의 해보겠습니다. Text : Simple String of CharactersPattern : Simple String of Characters to findTo Do : Find where in the Text the Pattern is 0.1 알고리즘 알고리즘시간 공간Naive..

자료구조 수업을 바탕으로 저의 생각을 정리하는 글 입니다. 0. Array 배열에서 요소의 탐색(* Search), 삽입(* Insert), 삭제(* Delete)는 매우 중요한 이슈입니다. 이에 그 배열이 Packed 되었는지 Unpacked 인지, Sorted 되었는지 Unsorted 되었는지에 따라 SID 의 성능의 차이가 발생합니다. 이에 Packed 의 유무와 Sorted 의 유무에 따라 4 가지 경우의 Array 들을 따져보겠습니다. (* 편의를 위해 중복된 값은 허용하지 않는다고 가정합니다.) 1. Packed, Unsorted 아마도 가장 간단한 방법이 아닐까 싶습니다. index 0 1 2 3 4 5 6 value 5 2 3 8 11 1.1 Search 해당 배열이 정렬이 되어있지 않기 ..

https://www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net 2178 미로 찾기와 비슷한 input 이라서 "DFS BFS 를 활용하면 되지 않을까" 먼저 생각했습니다. 2178 번 문제와 비슷하게 시작하는 노드에서 부터 동 서 남 북으로 이동 가능한데, 한 번 방문한 곳은 더이상 방문하지 않는다. 0이 적혀있는 곳은 방문하지 않는다. 를 지켜가며 DFS 든 BFS 든 해서 노드의 개수를 구하는 방식으로 풀었습니다. 2178 번 문제와 달리 해당 문제에서는 ..

자료구조 수업을 바탕으로 저의 생각을 정리하는 글 입니다. 1. 재귀 이진 탐색 앞서 반복문을 통한 이진탐색을 보았는데 아래는 재귀를 통한 이진탐색입니다. // binary search with Recursion int binarySearch(int a[], int n, int target) { // Base if(n target) return binarySearch(a, m - 1, target); else return m + binarySearch(a + m + 1, n - m, target); ..

자료구조 수업을 바탕으로 저의 생각을 정리하는 글 입니다. 알고리즘의 완전성을 증명하는 것은 중요합니다. 완전성을 증명하는 방법에는 여러가지가 있습니다. 알고리즘의 단계별로 하나하나 들어가서 이해하고 완전성을 확인하는 방법도 있습니다. 하지만 이는 그리 좋은 방법은 아닙니다. 해당 글에서는 수학적 귀납법을 사용하겠습니다. 1. 수학적 귀납법 임의의 공리 P가 존재한다고 할 때, 수학적 귀납법의 기본형은 다음과 같습니다. P(0) 가 성립한다. (* Base) 임의의 n 에 대하여 만약 P(n) 이 성립한다면, P(n+1) 역시 성립한다. (* Step) 수학적 귀납법의 강한 형태도 존재합니다. P(0), P(1), P(2) ... P(n-1) 이 성립한다. P(n) 이 성립한다면, P(n+1) 역시 성립..

https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 미로 탐색의 경우 BFS 를 사용해야 한다는 것은 아는데... 어떻게 구현해야 할지 몰랐습니다. 우선 Node 클래스를 만들었습니다. 그리고 미로에 해당하는 행렬을 입력받아 maze 변수에 넣어줍니다. 처음 시작하는 노드(* 0,0) 를 생성하고 그 노드에 인접 리스트에 (0,0)에 대해 상, 하, 좌, 우에 1이 있고 방문한 적이 없다면 노드를 추가해주는 방식을 사용했습니다. (* 상, 하, 좌, 우로 움직였을 때 행렬의 in..