teunteun2

https://www.acmicpc.net/problem/1525  2차원 배열의 인덱스를 1차원 배열 인덱스로,반대로 1차원 배열 인덱스를 2차원 배열의 인덱스로 변경하여 불필요한 배열을 생성하지 않는유틸리티 함수들을 알고리즘 스터디 대장님 덕분에 처음 알게 되었다. 목표한 번호판에 도달하기 위한 '최소이동' 횟수를 구하는 문제,도달하지 못하는 경우라면 -1 반환 import Foundation// 최소 이동으로 번호판 만들기 (빠진 숫자는 0으로 표시)// MARK: - Util Methodfunc from2DTo1D(_ r: Int, _ c: Int) -> Int { return 3 * r + c}func from1DTo2D(_ idx: Int) -> (Int, Int) { return ..

그래프는 꼭지점(Vertices)과 변(Edges) 로 이루어져 있을 뿐 ! 변 == 꼭지점과 꼭지점을 잇는 선 꼭지점을 노드라고 표현하겠습니당 그래프 데이터를 표현하는 기본 데이터 구조 [1] Edges Lists 노드와 꼭지점을 잇는 변을 List로 나타낸다 ex) 0 -> 1 은 [0,1]로 표현한다 장점 : 간단하다 단점 : List에서 특정 변(Edge)을 찾아야하는 경우 모든 목록을 검색하는 선형 검색이 필요하다 O(n) [2] Adjacency Matrices 노드로 이루어진 2차원 배열에서 연결된 꼭지점을 1로 표현하여 변을 나타낸다 장점 : 조회가 매우 빠르다 O(1) 단점 : 공간이 효율적이지 않다. 만약 연결된 곳이 많지 않다면 거의 대부분 0이 차지할 것이다 [3] Adjacency..

배열 맨 앞에 요소를 넣으려고 하면 배열 전체를 복사해야하기 때문에 O(n) 임 배열은 공간을 차지한다 그리고 배열을 생성할 때마다 크기를 지정해야 하기도 한다 그래서 공간을 모두 차지하지 않는다면 공간 낭비이다 연결리스트는 요소를 추가하는데에 매우 빠르며 미리 크기를 지정할 필요 없이 축소 확장이 용이하다 기본적인 노드 구현 // Node는 data와 자신의 다음에 연결될 노드의 정보를 가지고 있다 // 마지막 노드는 다음 노드가 없으므로 nil이 와야함 class Node { var data: Int var next: Node? init(_ data: Int, _ next: Node? = nil) { self.data = data self.next = next } } let node3 = Node(3..

Array 특징 세가지 - Arrays can contain anything - Arrays are of a fixed size 배열은 고정된 크기를 가지고 있다. Swift 에서는 배열을 생성할 때 크기를 지정하지 않기 때문에 Swift에서는 그 크기를 볼 수 없음 다른 언어에서는 배열을 초기화할 때 크기를 지정하기도,, Swift는 좀 다르지만 주의해야할 사항이 있음 (근데 알고리즘 문제 풀 땐 꽤나 많이 사용하는 Array(repeating: , count: ) ...) - Arrays support random access 연결리스트, 스택, 큐, 이진트리 모두 불가능하지만 Array는 가능한 것이 모든 요소에 접근 가능한 것 배열이 아무리 커지더라도 인덱스를 알면 O(1)로 그 인덱스의 값을 가..

다시 기초부터 다지는 느낌으로 Swift로 알고리즘 강의를 들어보면 어떨까 싶어서 듣게 된 Udemy 사이트의 The Swift Arcade Data Structures and AlgorithmsBootcamp https://www.udemy.com/course/the-swift-arcade-data-structures-and-algorithms-bootcamp/ What We Learned 1. BigO is the language used to compare performance of algorithms (time and space) 빅O 표현기법은 알고리즘 수행능력을 비교하기 위한 것 ( 수행능력 -> 시간복잡도 & 공간복잡도 ) 1-1. Constant O(1) / Linear O(n) / Qua..

뭔가 풀이가 굉장히 다양하게 나올 것 같은 문제였다 Swift가 문자열 다루기 까다로우니까 .. 냅다 배열로 받아 풀었다는 🐥 문제 세준이는 영어로만 이루어진 어떤 문서를 검색하는 함수를 만들려고 한다. 이 함수는 어떤 단어가 총 몇 번 등장하는지 세려고 한다. 그러나, 세준이의 함수는 중복되어 세는 것은 빼고 세야 한다. 예를 들어, 문서가 abababa이고, 그리고 찾으려는 단어가 ababa라면, 세준이의 이 함수는 이 단어를 0번부터 찾을 수 있고, 2번부터도 찾을 수 있다. 그러나 동시에 셀 수는 없다. 세준이는 문서와 검색하려는 단어가 주어졌을 때, 그 단어가 최대 몇 번 중복되지 않게 등장하는지 구하는 프로그램을 작성하시오. 입력 첫째 줄에 문서가 주어진다. 문서의 길이는 최대 2500이다. ..