sweetdev

var num: Int = Int(readLine()!)! for _ in 1...num{ var array: [Int] = [] array = (readLine()?.split(separator: " ").map { Int($0)! })! print(array[0] + array[1]) }

var num: Int = Int(readLine()!)! var string = readLine() var sum: Int = 0 string?.forEach{ sum += Int(String($0))! } print(sum)

var array: [Int] = readLine()!.split(separator: " ").map{ Int($0)! }.sorted() print(array[1])

switch Int(readLine()!)!{ case 90...100: print("A") case 80...89: print("B") case 70...79: print("C") case 60...69: print("D") default: print("F") }

let value = Int(readLine()!)! for i in 1...value{ for _ in stride(from: value, to: i, by: -1){ print(" ", terminator: "") } for _ in stride(from: 0, to: i, by: 1){ print("*", terminator: "") } print("") }

for i in stride(from: Int(readLine()!)!, to: 0, by: -1){ print(i) } 스위프트 갓갓..한줄^^

let newArr: [String] = readLine()!.split(separator: " ").map{ String($0) } print(Int(newArr[0])! * Int(newArr[1])!)

var input = readLine()! var resultArray = input.split(separator: " ") while (resultArray != ["1", "2", "3", "4", "5"]){ for i in 0.. resultArray[i+1] { resultArray.swapAt(i, i+1) resultArray.forEach{ print("\($0)" + " ", terminator: "") } print("") } } } terminator 써서 print()가 newLine이 자동으로 들어가지 않게 막았다. \-/ swapAt()이런것도 너무 편하고, split으로 배열 바로 만드는것도 정말 정말 편하다!!

let number: Int = Int(readLine()!)! var arrayOfGivenData: [String] = [] for _ in 1...number { arrayOfGivenData.append(readLine()!) } arrayOfGivenData = Array(Set(arrayOfGivenData)).sorted(by: { $0

import Foundation let givenString = readLine()!.uppercased() // 선언과 초기화 var dictionary: [Character: Int] = [:] "ABCDEFGHIJKLMNOPQRSTUVWXYZ".forEach{ dictionary[$0] = 0 } // 값 추가 for letter in givenString { dictionary[letter]! += 1 } // 가장 큰 값 찾기 let biggest = dictionary.max{ a, b in a.value

let numOfTestCases = Int(readLine()!)! var testArray: [Int] = [] for _ in 1...numOfTestCases{ testArray.append(Int(readLine()!)!) } let fibonacciSequence = [0, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610] for i in testArray{ switch i { case 0: print ("1 0") case 1: print("0 1") case 2: print("1 1") case 3...15: print("\(fibonacciSequence[i-2])" + " " + "\(fibonacciSequence[i-1])") case..

import Foundation let givenString = readLine() ?? "" var sum: Int = 0 for char in givenString{ switch(char){ case "A", "B", "C": sum += 3 case "D", "E", "F": sum += 4 case "G", "H", "I": sum += 5 case "J", "K", "L": sum += 6 case "M", "N", "O": sum += 7 case "P", "Q", "R", "S": sum += 8 case "T", "U", "V": sum += 9 case "W", "X", "Y", "Z": sum += 10 default: sum += 0 } } print(sum)

가정 '그림'과 같이 방향이 없는 weighted edge로 구성된 그래프라고 가정한다. 방향이 있는 edge도 가능하다. 결과 내가 정한 시작 노드 한 개에서 모든 노드로 가는 가장 빠른 길과 cost를 알 수 있다. 과정 초기화 먼저 시작 노드를 정한다. (나는 U라고 정했다.) U에 인접한 노드들의 distance를 저장해준다. 루프 저장한 노드들 중에 가장 빠르게 갈 수 있는 노드를 고른다. 그리고 그 노드에서 갈 수 있는 길들을 찾아서 업데이트 해준다. (기존 distance와 새로 찾은 node를 통해서 가는 것중에 짧은 distance로 업데이트 한다. distance = min(저장된 값, 새로 찾은 노드까지 가는 값 + 새로운 노드에서 원하는 노드까지 거리)) 모든 노드를 방문할때까지 반..

void dfs(int v){ nodePointer w; visited[v] = TRUE; printf("%5d", v); for (w=graph[v]; w; w=w->link){ if (!visited[w->vertex]) dfs(w->vertex); } }

undirected graph: (u,v)로 edge표현 directed graph: 로 edge표현, u가 tail이고 v가 head임.

트리를 사용해서 '집합'을 표현해보자 집합의 모든 원소는 0, 1, 2, ..., n-1이라고 가정한다. 모든 집합은 disjoint된다고 가정한다. (각각 집합들끼리 겹치는 원소가 없음) 얘는 0~9인 예제이다. 집합에 대해 수행하고자 하는 연산은 다음 두 가지이다. (1) disjoint set union (2) find(i) (1)은 A∪B를 할 수 있다는 의미, 즉 (2)는 원소 i가 속한 집합을 리턴받는거 가능 A∪B을 하려면 어케 할까... 두 트리중 하나를 다른 트리의 서브트리로 만들면 된다. 저 위에 그림에서 S1 ∪ S2를 하려고 하면, 하면 되는것처럼 말이다! 두가지 함수를 짜보자! void simpleUnion(int i, int j){ parent[i] = j; } int simpl..

forest F에 대응하는 binary tree T의 preorder, inorder traverse는 F의 순회와 자연스러운 대응 관계를 가진다. [Preorder Traverse] T의 preorder traverse는 다음과 같이 정의된 forest preorder로 F의 노드들을 traverse하는 것과 동일하다. (1)F의 첫번째 tree의 node 방문 (2)첫번째 tree의 subtree를 preorder traverse한다. (3) F의 나머지 tree들을 preorder traverse한다 [Inorder Traverse] T의 preorder traverse는 다음과 같이 정의된 forest inorder로 F의 노드들을 traverse하는 것과 동일하다. (1)F의 첫번째 tree의 ..

중앙대학교 소프트웨어대학 강현철교수님의 "자료구조" 과목을 듣는 과정에서 학습 목적으로 작성한 포스트입니다. Selection Tree(선택 트리)는 merge sort에 사용하는 특수한 구조를 가지는 트리 자료구조다. selection tree에는 크게 winner tree와 loser tree가 있다. 다른 말로는 tournament tree라고도 불린다. (merge sort가 뭔지 모른다면 merge sort를 공부하고 와야 이 포스팅을 이해할 수 있다..!) 쪼갠 리스트들을 합치는 과정에서 각 리스트의 최솟값(최댓값)들을 비교해야 하기 때문에 n/2 , n/2개를 합칠때마다 (n-1)번의 비교횟수가 필요하다. 이걸 줄이기 위해서 선택트리를 이용한다. #include #include #includ..

Forest로 시작한다. 장점 : 트리가 여러개 나올 수 있다.

트리를 만들기 위한 시작 노드를 하나 지정하고(어떤 노드여도 괜찮다), 그 노드에 minimum cost edge를 더해준다. 만약 노드를 더하는데, 이미 있는 노드 두개로 만들게 되는 edge라면 더하지 않는다.

* greedy algorithm을 따른다 * minimum cost spanning tree를 얻기 위한 과정 * 과정 1. edge를 다 지운다 2. 제일 cost가 작은 edge를 하나 더해준다 3. Q) global optimum을 얻지 못할 수도 있지 않을까? A) 항상 global optimum을 얻을 수 있다는 것이 증명되었다. 교재에 proof 있음

Binary search tree는 탐색, 삽입, 삭제, 연산에 있어서 지금까지 공부했던 어떤 자료구조보다도 성능이 좋다고 한다!! 열심히 공부할 이유가 되는군!! [Definition] (1) 모든 원소는 키를 가지며, 어떤 두 원소도 동일한 키를 갖지 않는다 (2) 왼쪽 subtree에 있는 키들은 루트의 키보다 작다 (3) 오른쪽 subtree에 있는 키들은 루트의 키보다 작다 (4) 왼쪽, 오른쪽 subtree도 모두 binary search tree이다. BST(binary search tree, 앞으로는 BST라고 부를게요) 의 가장 큰 특징은, inorder로 traverse했을 때 작은 순서대로 라는것 !!

이렇게 생긴 max heap에서 root인 50을 지운다고 해 보자. 우리가 쓰는 알고리즘은 가장 오른쪽에 있던 값을 떼서 루트에 넣고 본다.(대책 노...) 이제 adjust를 하는데, 31이랑 49랑 바꿔본다. 31이랑 또 48이랑 바꾼다. 이러면 다시 max heap의 조건을 충족한다. 근데 바꾸는 기준이 뭘까?? 44랑 바꿔도 max heap은 됐는데...? 이건 코드를 보면 알 수 있다. //코드가 정말 보기싫다. 다음에 정리하자

이런 max heap에서 원소 하나를 삽입한다고 해 보자. complete binary tree의 조건을 만족하려면, 원소 하나가 들어갔을 때 트리는 무조건 저 자리에 들어갈 수 밖에 없다. 삽입되는 원소의 정확한 위치를 결정하기 위해서는, 트리의 새 노드에서 시작해서 루트 쪽으로 올라가는 bubbling-up 방법을 사용하면 된다고 한다. 삽입되는 원소는 삽입이 완료된 뒤, 최대 힙이 되는 것이 확인될 때 까지 위쪽으로 계속 올라간다. 예를 들어서 생각해보자! 새로운 원소가 30이라면, 바로 저 자리에 넣으면 된다. 그러나 값이 49이면 넣을 수 없다. 그러므로 31을 검은색 위치에 넣고, 최대 힙이 되는지 본다. 여전히 안 된다. 그럼 48을 그 자리에 넣는다. 여전히 안된다. 51을 그 자리에 넣는..

1. priority queue란? 우선순위 큐에서는 우선순위가 가장 높은, (또는 낮은) 원소를 먼저 삭제한다고 하고, 임의의 우선순위를 가진 원소를 우선순위 큐에 삽입할 수 있다고 합니다. FIFO인 일반 큐와는, 우선순위 순서로 pop하는 기능이 다릅니다. 우선순위 큐가 왜 필요하냐면, 똑같은 기계를 쓰는 소비자 중에 3000원을 낼 사람, 1000원을 낼 사람, 2000원을 낼 사람이 있다고 하면 기계는 3000원을 낼 사람을 먼저 쓰게 해주고, 그 다음 2000원, 그 다음 1000원을 낼 사람 순으로 써주게 하는 것이 가게 주인 입장에서 최고이죠? 이런식으로 큐에 넣는 원소들에 우선순위를 부과해야 할 때, 우선순위 큐를 쓰면 됩니다. 이 경우는 max priority queue이고, 반대 경우..

https://sweetdev.tistory.com/120 불러오는 중입니다... 이 글에서 '스택 없이 트리를 traverse 하는 법에 threaded binary tree를 쓰는 방법'이 있다고 했는데, 오늘은 그 방법에 대해서 다뤄보려고 한다. binary tree에서는 inorder traverse 하기 위해서 스택을 썼었다. (이제 혼자서도 잘짜요!..ㅎㅎ) 그럼, threaded binary tree에서는 어떻게 구현할까?? 이렇게 구현하면 된다고 한다.

쓰레드라는 표현을 굉장히 자주 들었는데 뭔지는 몰랐었다. 여기서 살펴보고자 한다! binary tree의 링크 표현을 보면, 실제 표현보다 더 많은 null link가 있다고 한다. 이진 트리에는 총 2n개의 링크 중에 n+1개의 null link가 있으니까, 과반수 이상이 놀고있는 링크인 것이다. 이것을 안타까워한 어떤 공머생이, null link를 Thread라는, 다른 노드를 가리키는 포인터로 대치하였다고 한다. 규칙은 다음과 같다 (1) ptr-> leftChild가 null이면, ptr-> leftChild를 inorder traverse 할 때, ptr 앞에 방문하는 노드에 대한 포인터로 대치한다. 이것은 null link를 ptr의 inorder predecessor에 대한 포인터로 대치하는..

명제 해석 식에 대한 만족성 문제는, 식의 값이 true가 되게 지정할 수 있는 방법이 있는지를 묻는 문제라고 한다. 책의 설명을 보니 되게 중요한 문제인가보다. 1950년대에 휴리스틱 프로그래밍의 가능성을 증명하기 위해서 썼다고 한다. 잘 모르겠어서 여기까지만 쓴다 ^^;;

copy코드와 비슷하게, 재귀로 짰다

재귀를 이용해서 짜면 쉽다! leftChild, rightChild, data이케 해버리면 개꿀