Hyun's_Devlog

https://www.acmicpc.net/problem/20530

그래프 탐색과 유니온파인드로 접근했다.

풀이

정점 N개와 간선 N개를 가진 트리는 한 개의 사이클을 가지고 있는 트리이다. 따라서 정점 u에서 v로 가는 경로가 사이클을 거쳐가게 된다면 경로는 2개가 되고, 경로에 사이클이 없다면 경로는 1개가 되는 것이다.

따라서 사이클에 속해있는 정점을 파악한 뒤 유니온 파인드를 수행하다. 연결하려 하는 두 정점의 경로가 사이클에 속한 경로라면, 정점을 연결하지 않고 넘어간 뒤, 쿼리가 주어질 때, 두 정점의 부모가 같다면 1 아니면 2를 출력하면 정답이다.

주어진 예제를 통해 보면 정점 1 - 2 - 3으로 사이클이 이루어진다. 따라서 정점 1, 2, 3 사이의 간선을 없애고 쿼리에서 서로 다른 컴포넌트의 경로를 물어보면 해당 경로는 사이클을 통한 경로가 있다는 뜻이므로 2를 출력, 같은 컴포넌트 내의 경로를 물어보면 1을 출력하면 된다.

사이클 검출은 진입차수가 1인 정점부터 너비 우선 탐색을 수행하여 찾아내었다. 

정답 코드

https://www.acmicpc.net/problem/15559

유니오 파인드와 그래프 탐색으로 접근했다.

풀이

2차원 지도를 1차원 배열로 매핑한 뒤 지도에 적힌 움직임 대로 그래프 탐색을 수행한다.

탐색을 수행하면서 현재 위치와 다음으로 이동할 위치의 번호끼리 합병해 주면 된다.

컴포넌트의 개수를 출력해 주면 정답이다.

단, 중복 방문을 막는 과정에서 실수하여 WA를 받았다.

반례는 문제에 주어진 예제를 보고 생각해 냈다.

3 4

SWWW

SEEN

EEEN

방문했던 위치여도 아직 방문하지 않은 곳에서 진입이 가능하기에 방문했던 위치도 무조건 유니온 동작을 수행해야 한다.

정답 코드

https://www.acmicpc.net/problem/1765

유니온 파인드로 접근했다.

풀이

원수를 담는 배열 enemy 2차원 배열을 생성하여 원수 관계가 들어오면 양방향으로 추가.

친구 관계가 입력되면 유니온을 통해 컴포넌트를 합친다.

모든 입력이 들어오고 나면 enemy 배열을 탐색하면서 원수의 원수를 찾아 서로 연결해 주면 된다.

남아있는 컴포넌트의 개수를 출력하면 정답이다.

정답 코드

유니온 파인드로 접근하였다.

풀이

문제의 핵심은 가중치가 주어지는 간선은 오로지 한 개라는 것. 즉 가중치가 있는 간선을 거쳐가는 경로의 개수를 찾는 문제다. 가중치가 없는 간선들을 먼저 연결해 준 뒤 마지막으로 가중치가 존재하는 간선을 연결할 때, 연결하려는 두 컴포넌트의 개수를 서로 곱해주면 해당 간선을 거쳐가는 간선의 개수를 구할 수 있게 된다. 예제를 기준으로 그림으로 설명하면 다음과 같다.

2번 정점과 3번 정점을 연결할 때, 1-3, 1-4, 1-5, 2-3, 2-4, 2-5의 경로에서 2-3 간선을 이용해야만 한다. 즉 2번 정점이 속한 컴포넌트의 정점개수와 3번 정점이 속한 컴포넌트의 정점 개수를 서로 곱해주면 정답이다.

단, 예제입력 2와 같이 가중치가 존재하는 간선을 연결할 때 이미 두 정점이 같은 컴포넌트인 경우 비용 0인 간선으로 우회가 가능하기에 이때는 정답이 0이다.

따라서 유니온 파인드 알고리즘을 통해 각 컴포넌트의 개수를 핸들링하여 정답을 출력해 주면 된다.

정답 코드

https://github.com/hyun083/CS193p-Spring-2021/tree/main/Assignments/Assignment%202

Lecture3와 Lecture4를 시청하고 작성한 두 번째 programming Assignment. More Memorize라는 주제에 맞게 첫 번째 programming Assignment에 몇 가지 task를 추가한 결과물이다.

Required Tasks

• 테마추가 (제목, 색상, 이모지, 카드쌍의 수)
• 테마에서 사용가능한 이모지보다 적은 수의 쌍을 생성
• 쓰이지 않는 이모지가 발생하면 안 된다.
• 같은 이모지가 두 쌍 이상 생성되면 안 된다.
• 테마는 최소 6가지 이상 사용해라.
• 테마의 추가는 한 줄로 가능하다.
• new game 버튼을 생성해라.
• new game 생성마다 무작위 테마가 나와야 한다.
• 게임에 사용되는 카드는 무작위 순서여야 한다.
• UI에 테마의 이름이 나오게 할 것.
• 점수를 표시하여 나타내라.

Extra Credit

• 카드의 색상에 그라데이션 적용
• 점수에 시간요소를 추가
• 고정된 수의 카드쌍이 아닌, 매 순간의 랜덤 개수의 카드쌍을 생성해라.
• 테마 생성 시 카드쌍의 수와 관계없이 초기형태의 모든 이모지 셋이 고정된 상태로 생성되어야 한다.

Lecture 4에서 실습한 코드를 기반으로 EmojiMemoryGame에서 대부분의 요구사항을 만족시킬 수 있었다.

6개의 고정된 이모지 배열과 테마를 표현하기 위한 [(title:String, color:Color, emoji:[String])] 배열을 생성하였다.

이후 CreateMemoryGame 함수를 통해 무작위 테마와 순서가 섞인 이모지를 통해 카드쌍을 생성을 통해 요구사항을 만족하였다.

고민이 많았던 요소인 점수, 테마 제목, 테마 색상은 Model을 담당하는 MemoryGame에 작성하였다.

페널티 요소를 다루기 위해 card 구조체에 Bool 타입의 alreadyBeenSeen 속성을 추가하였다.

Extra Credit을 위한 시간요소가 기억에 남는다. Date 타입의 timeSinceLastFlip 변수를 생성하여 마지막으로 카드를 뒤집은 시간을 저장한 뒤 max(10 - (카드 쌍을 확인하는 시간 - 마지막으로 카드를 뒤집은 시간), 1)을 보너스 점수로 계산한 뒤 틀렸다면 점수 차감, 쌍이 맞았다면 점수 획득을 통해 게임을 구성하였다.

view를 담당하는 ContentView에는 지난번 assignment 1에서 작성했던 widthThatBestFits() 함수를 재사용하였다. 카드의 수에 맞게 너비를 자동으로 조절해 준다. 

추가된 요소인 점수, 제목, 색상은 ViewModel 역할을 하는 EmojiMemoryGame 객체에서 가져오게 되며, New Game 버튼 또한 ViewModel의 CreateMemoryGame() 함수를 작동시켜 새로운 게임을 생성하게 된다.

result

https://www.acmicpc.net/problem/23743

기본적인 MST 문제다. 

풀이

두 가지 방법으로 풀었다. 첫 번째로 접근했던 방법은 시간이 조금 빠르지만 코드가 조금 더 길어진다. 

간선의 가중치가 작은 순서로 두 정점 U, V를 연결할 때, 조건을 추가했다. 

두 정점에 워프를 설치하는 비용 > 두 정점을 연결하는 간선 비용 + min( U정점에 워프 설치 비용, V정점에 워프 설치 비용)

두 정점에 탈출구 워프를 설치하는 비용이 더 저렴하다면 두 정점은 연결하지 않는다. 반대로 두 정점에 탈출구 워프 설치 비용이 더 비싸다면 간선을 연결하고 워프를 설치비용이 더 저렴한 쪽이 루트가 되어 연결하면 된다.

이후 각 컴포넌트의 루트 정점에 워프설치 비용을 더해주면 가장 작은( 간선 + 워프 설치 ) 비용이 나오는데, 마지막으로 한번 더 모든 정점에 워프 설치비용과 비교하여 더 작은 쪽을 출력하였다.

두 번째 방법은 탈출구를 0번 정점으로 취급하여 간선정보를 정렬한 뒤 MST를 수행하면 간단하게 구할 수 있다.

정답 코드-1

정답 코드 - 2

https://www.acmicpc.net/problem/1833

MST 알고리즘의 기본문제다. 크루스칼 알고리즘을 통해 해결했다.

유니온 함수의 구현에서 사소한 실수를 해서 WA를 받아 당황했지만 실수를 금방 발견했다.

풀이

주어지는 간선은 양방향 간선이므로 u (0 ..< N), v (u+1 ..< N) 탐색을 통해 중복되는 정보는 배제하고 탐색하였다.

간선이 음수면 이미 연결된 고속도로 이므로 절댓값을 totalCost에 더한 뒤, 두 정점을 연결한다. 주의할 점은 이미 부모가 같은 정점끼리의 간선이 음수로 주어질 수도 있으므로 있으므로 예외처리를 해주어야 한다.

나머지의 경우는 edges 배열에 담아낸 뒤 비용이 적은 간선부터 유니온 함수를 수행한다. 이때 연결된 간선은 배열에 따로 정보를 담아주었다가 출력해 주면 된다.

정답 코드

mutating

구조체는 클래스와 마찬자기로 메서드를 가질 수 있는데, 자기 자신(self)의 변경이 일어나는 메서드 작성 시 mutating 키워드를 명시해주어야 한다.

Lectrue 3에서 구조체의 대표적인 특징인 copy on write이 있다고 했다. 구조체는 값타입(value type)으로 객체의 할당 혹은 인자로 넘겨줄 경우 값 복사가 일어나지만, 정확히는 사본과 원본의 차이점이 발생할 때 복사가 이루어진다고 했다. 여기서 사본생성의 시점 혹은 이후에 사본 생성 여부를 가늠하게 해주는 장치가 바로 mutating 키워드이다.

ObservableObject

swiftUI의 핵심기능 중 하나이다. 해당 프로토콜이 적용된 객체에 변경이 감지되면 구독하고 있는 Subscriber에게 변경을 알린다.

가장 많이 사용되는 부분이 MVVM구조의 ViewModel에 해당된다. View에서 ObservableObject를 구독(Subscribe) 하고 ViewModel에서 알리는 변경점을 통해 View의 body의 필요한 부분의 재빌드를 통해 데이터 바인딩이 일어난다.

ObjectWillChange

ObservableObject를 채택하게 되면 우리는 ObjectWillChange라고 불리는 Publisher를 얻게 된다. 해당 속성을 통해 변경점을 알릴 수 있다.

send()

ObservableObject가 가지고 있는 속성 중 변경이 일어나면, ObjectWillChange.send()를 호출하여 변경사항을 subscriber에게 알리게 된다.

@Published

ObservableObject의 Publisher를 통해 변경점을 알리는 일을 자동으로 해주는 키워드이다. ObservableObject 내에 속성 중에서 변경점을 알리고 싶은 속성에 해당 키워드를 적용하게 되면 변경점이 일어날 경우 자동으로 ObjectWillChange.send()가 호출된다. 주로 ViewModel에 생성된 Model 객체에 사용하게 된다. 따라서 Model의 변경을 자동으로 감지할 수 있고, 이를 통해 Model과 View의 바인딩 작업을 손쉽게 할 수 있다.

@ObservedObject

ObservableObject를 구독(subscribe) 받기 위해 사용하는 키워드이다. 생성된 객체에 해당 키워드를 적용하면 된다. 주로 View에서 ObservableObject를 채택한 ViewModel을 구독하기 위해 사용하게 된다. 이를 통해 ViewModel은 Model과 View의 바인딩이 가능해진다.

참고영상

https://www.youtube.com/watch?v=oWZOFSYS5GE&list=PLpGHT1n4-mAsxuRxVPv7kj4-dQYoC3VVu&index=5&t=4804s