nose딩

결과:

<프로그래머스 문제 풀기> 

*해시 - 완주하지 못한 선수

  이 문제는 전에 string 배열로 다음과 같이 풀었었다.

sort로 정렬시키고 반복문 돌려서 간단히(?) 해결했던 문제 ,,

하지만 이게 해시 문젠데 해시를 이용하지 않아서 해시로 다시 풀어보았다. 🔥

일단, 해시맵을 하나 만들어서 participant로 넣어준다.

동명이인도 존재하기 때문에, 같은 key가 있을 경우 +1 해주었다.

그리고 completion에 있는 애들은 1씩 감소!

이렇게 되면 완주한 애들은 (동명이인이든 아니든) 0이 될 것이다.

*해시 - 전화번호 목록

이 문제 또한 그냥 배열로 해결했었었다.

그래서 해시로 풀어보았다. 🔥

처음에 phone_book에 있는 애들을 HashMap에 다 넣어주었다.

그리고 이중for문을 이용하여서 키 값이 phone_book에 있는 원소와 다르고,

그거로 시작할 때 answer가 false가 되고 break 된다.

근데 ,, 이게 ,, 해시를 쓰긴했지만 이걸 원한걸까 하는 의문,, ? 🤔

후에 해시를 이용한 다른 사람의 풀이를 찾아봐야겠다 ,, 라는 생각,,(만 가짐)

배열로만 풀었던 문제들을, 해시맵을 사용하여서 다시 풀어보았는데,

해시맵이 삽입,삭제, 검색 에서 엄청 빠르다는 장점을 가지고 있어 해시로 풀어야 하는 것 같다. (내 뇌피셜,,)

회의 일자 : 

2021.01.13 20:00 ~ 23:00 

목표 : 

 - 5회차에 공부한 것을 가지고 알고리즘 문제 해결

결과 :  

<해시>

*HashMap

  -> 키와 값을 저장하는 자료 구조 !  

 : 삽입 -> put()

 : 검색 -> get()

  장점 : 삽입, 삭제 시간 매우 빠름, 검색 더 빠름

  단점 : 키로만 접근 할 수 있음 

  => 빠른 삽입, 검색이 필요한 응용에 적합 !

*HashSet

  -> 중복 x -> 값 추가 or 삭제할 때 그 값이 set내부에 있는 지 검색한뒤 작업을 수행 -> 속도가 list 구조보다 느림

  -> 정렬 x , TreeSet은 자동 정렬!

  ex) 방문 손님 총 숫자 -> 여러 번 방문한 손님 한번으로 체크해야함 ! 

 *삽입 : add()

 *삭제 : remove()

          clear() (초기화)

 *출력 -> Iterator 사용

            ex) Iterator iter = set.Iterator();

                 while(iter.hasNext()){

                    System.out.println(iter.next());

                 }

*contains() : 내부에 값이 있는지 check -> ex) set.contains(1) -> set 내부에 값 1이 있는지 !

<스택>

  : LIFO(Last In First Out) -> 먼저 들어간게 나중에 나옴 !

  : 시스템 해킹에서 버퍼오버플로우 취약점 이용한 공격 시 스택 메모리의 영역에서 함!

  : 인터럽트 처리, 수식 계산, 서브루틴의 복귀 번지 저장 등에 쓰임 !

  : 그래프의 깊이 우선 탐색(DFS)에서 사용 !

  : 재귀 함수를 호출할 때 사용 !

*삽입 : push()

*삭제 : pop() -> 가장 위쪽에 있는 원소 제거 ! , 모두 제거하고 싶으면 clear()

*출력(삭제x) : peek()

*사이즈 : size()

*비어있는지 : empty()

*해당 원소가 있는 지 : contatins()

  ex)stack.contains(1) -> stack에 1이 있는지 check

<큐>

  : 줄을 지어 순서대로 처리 되는 구조 ! 

    -> FIFO(First In First Out) -> 먼저 들어온 데이터가 가장 먼저 나감 !

  : 한쪽 끝은 front로 삭제 연산만 수행, 다른 한 쪽 끝은 rear로 삽입 연산만 수행 !

  : 그래프의 넓이 우선 탐색(BFS)에서 사용 !

: 컴퓨터 버퍼에서 주로 사용, 입력이 여러갠 데 처리 못할 때 버퍼(큐)를 만들어 대기시킴 !

*선언 : Java에서 큐는 LinkedList를 활용하여 생성 !

  Queue<Element> queue = new LinkedList<>();

*삽입(enqueue) : add(), offer()

*삭제(dequeue) : remove() -> queue 첫 번째 값 제거 ! 

        : poll() -> 첫 번째 값 반환하고 제거 

        : clear() -> 초기화

*출력(삭제x) : peek() -> 큐에 첫번째로 저장된 값 참조 !

다음시간에는 이를 토대로 프로그래머스 사이트에서 관련 문제를 해결하고자 한다. 🔥😄

회의 일자 : 

2021.01.11 20:00 ~ 23:00 

목표 : 

  - 해시, 스택/큐 공부

결과 : 

*프로그래머스 - 타겟 넘버

numbers의 숫자를 적절히 더하거나 빼서 target 값으로 만드는 방법의 수를 구하는 문제로,

모든 방법의 수를 구해야하기 때문에, 즉, 모든 노드를 방문하고자 하는 경우이므로 dfs 사용 !

 재귀로 구하는 ,, 비교적 (?) 간단한 문제,, target값을 계속 인자로 넘겨주지 않기 위해 전역변수로 t를 선언하여 사용하였다.

*프로그래머스 - 네트워크

dfs 문제로 해결 -> 연결 되어 있는 끝까지 가는 방식

일단 처음에 check가 false로 되어 있고, 처음 반복문을 돌릴 때, false이면 dfs 호출한다.( 이 경우에 answer 증가 )

dfs는 호출되어 반복문을 돌며 즉 끝까지 가게되는데,

com[i][j]가 1 , 즉 연결되어 있을 경우, 그리고 check가 false 인 경우에 dfs를 다시 호출하는방식으로 진행된다.

**다음에 다시 풀기

회의 일자 : 

2021.01.06 20:00 ~ 23:00 

목표 : 

- 3주차(깊이/너비 우선 탐색(DFS/BFS))에 공부한 것을 토대로 프로그래머스 문제 해결

결과:

*****경로 찾는 문제

*깊이 우선 탐색(DFS) - Depth-Frist Serach

- root 노드(or 임의의 노드)에서 다음 branch로 넘어가기 전에 해당 branch를 완벽하게 탐색하는 방법!

-> 한 방향으로 갈수 있을 때 까지 계속 가다가 더 이상 못가면 돌아와서 다른방향 !

-> 깊게 탐색 !

-> 모든 노드를 방문하고자 하는 경우 !

-> BFS보다 좀 더 간단

-> 속도는 BFS보다 느림

  *구현

  -> 스택

  -> 재귀함수 : 가장 보편적 ! -> 인접행렬 

      -> 어떤 노드 방문 했었는지 여부를 반드시 검사해야함 ! (검사하지 않으면 무한루프 위험!)

      -> 인접행렬 !

*너비 우선 탐색(BFS)

- root 노드(or 임의의 노드)에서 시작해서 인접 노드 먼저 탐색 !

-> 시작 정점으로부터 가까운 정점을 먼저 방문, 멀리 떨어져있는 정점 나중에 방문 !

-> 넓게 탐색 !

-> 두 노드 사이의 최단 경로(최소 비용 문제) or 임의의 경로 찾고 싶을 때 !

-> 재귀 x 

-> 어떤 노드 방문 했었는지 여부를 반드시 검사해야함 ! (검사하지 않으면 무한루프 위험!)

  *구현

    -> 큐(Queue) -> 선입선출(FIFO) -> 인접 리스트

-> 깊이가 1인 모든 노드 방문 -> 깊이가 2 .,. ~ 반복 -> 더 이상 방문할 곳 없으면 탐색 마침 !

* 인접행렬 : 정점 탐색 과정에서 무조건 1 ~ n 까지 루프 돔

* 인접리스트 : 각 리스트마다 존재하는 정점만큼 존재 ! -> i ~ n 까지 돌 필요 x -> 존재하는 만큼만 탐색 !

++ 다음 시간에는 이를 토대로 문제 해결을 하고자 한다. ! 💥

회의 일자 : 

2021.01.04 20:00 ~ 23:00 

목표 : 

- 깊이/너비 우선 탐색(DFS/BFS) 공부