백준 복습 - 집합과 맵

집합과 맵 - 10815번: 숫자 카드

https://jh4995.tistory.com/104

집합과 맵 - 10815번

---

집합과 맵 - 14425번: 문자열 집합

https://jh4995.tistory.com/105

집합과 맵 - 14425번

---

집합과 맵 - 1620번: 나는야 포켓몬 마스터 이다솜

1) 정렬함수에서 return 값 설정 관련 복습

https://jh4995.tistory.com/107

(*풀이진행중)집합과 맵 - 1620번

https://jh4995.tistory.com/109

집합과 맵 - 1620번

---

집합과 맵 - 10816번: 숫자 카드 2

1) 이진탐색트리, AVL트리 사용시에 시간초과 발생하는 이유 관련 추가공부

2) lower_bound, upper_bound 를 활용한 이진탐색풀이 추가공부

https://jh4995.tistory.com/116

(풀이진행중)집합과 맵 - 10816번

https://jh4995.tistory.com/124

집합과 맵 - 10816번

---

집합과 맵 - 1764번: 듣보잡

https://jh4995.tistory.com/120

집합과 맵 - 1764번

---

집합과 맵 - 1269번: 대칭 차집합

https://jh4995.tistory.com/122

집합과 맵 - 1269번

---

집합과 맵 - 11478번: 서로 다른 부분 문자열의 개수

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

11478번: 서로 다른 부분 문자열의 개수

-> c를 이용해서는 아직 내가 아는 범위에서 원소의 중복을 제외시키는 set 을 구현하는 것이 너무나도 복잡하다

-> 해당 문제는 set 이 보다 쉽게 구현가능한 다른 언어 / 혹은 슬라이싱을 활용할 수 있는 파이썬

    과 대비해서 c를 활용할시에는 너무 복잡해지기 때문에 추후 풀이로 남겨둘 예정

 

-> 자바를 활용해서 풀이완료 (23.03.30 추가)

https://jh4995.tistory.com/219

[Java] 백준 - 11478번: 서로 다른 부분 문자열의 개수

-> 아직 자바를 활용하는 것이 완전히 익숙하지 않기에, set이나 string 관련 여러 메서드가 익숙치않다

---

집합과 맵 문제들에서는 공통적으로 풀이를 진행하는 방식이 존재했다

(scanf 로 입력받음 -> 입력값들을 정렬 -> 정렬된 형태에서 탐색 -> 조건에 걸리는 값들만을 출력)

 

입력과정에서는 과거에 배웠던 기초적인 부분들을 다시 복습할 수 있었다

1) scanf("%s", ) -> &생략 / scanf(" %c", ) -> %앞 한 칸 필수

2) 1차원 및 2차원 배열 관련

-> 여러개의 문자열이 입력되는 경우 2차원 배열을 활용해야하고, 이에 따라서 배열과 malloc / calloc 을 활용하는 법

 

정렬부분에서는 퀵정렬을 대부분 사용했다

정렬을 하는 대상이 숫자라서 오름/내림차순 정렬되는 경우와 대상이 문자라서 사전식으로 정렬되는 경우가 있다

오름/내림차순의 변경이나, 사전식/사전반대식으로의 정렬은 정렬 관련 함수에서 쥬로 부등호를 통해 변경한다

정렬대상에 따라서 포인터나 strcmp 를 활용하여 return 값들을 슬기롭게 1, -1, 0 으로 나누는 과정이 중요하다

또한, 입력받은 배열을 그대로 정렬할 것 인지 / 혹은 tmp 배열에 복사해놓은 뒤 정렬할 것 인지도 판단해야한다

 

탐색부분에서는 주로 이진탐색을 사용했다

14425번처럼 이진탐색을 진행하는 함수로 넘어간 size 에서 1을 제외하면서 탐색 사이즈를 정의해야한다

또한 경우에 따라서 (탐색의 대상이되는 배열, 사이즈, key 값)만을 함수로 넘기지 않고 (left 값, right 값) 등으로의 변경도 유연하게 진행해야한다

하지만 이진탐색은 탐색의 대상에서 중복값이 존재하지 않는 경우에만 효과적이고,

10816번처럼 탐색대상에 중복값이 존재하는 경우에는 활용하기가 힘들어지는 단점이 존재한다

이를 위한 해결책으로는 10816번에서와 같이 lower_bound 와 upper_bound 를 활용하는 이진탐색 풀이가 존재한다

 

+) 자료구조 강의에서 추상적으로만 강조되던 정렬과 탐색을 동시에 실제로 경험해볼 수 있었던 주제였다

주로 활용한 퀵정렬과 이진탐색 이외에도 다양한 방식의 정렬과 탐색을 이용한 풀이가 가능한지를 추후 살펴보아야한다

특히 이진탐색트리(더 나아가서는 AVL트리)를 활용하는 탐색도 실제로 작성해보아야할 것 같다