본문 바로가기

분류 전체보기101

[백준/C++] #1525 퍼즐 (BFS) 문제https://www.acmicpc.net/problem/1525 구상빈칸을 움직여서 배열의 상태가 원하는 상태로 나오게끔 하는데, 이때의 최소 이동 횟수를 구하는 문제였다. 최소 이동 횟수를 구하는 것이다 보니 bfs를 이용하는 문제라는 건 인지했지만, 원하는 상태로 바꾸는 데에 있어서 빈칸을 언제까지 움직여볼 것인가에 대한 고민이 들었다. 단순하게 방문했는지의 여부를 판단하기에는 빈칸을 움직이는 순서에 따라서 상황이 다양하게 바뀔 수 있었다. 그래서 그 이전에 해당 상황에 도달한 적이 없다면, 큐에 넣는 방식을 택했다. *map의 find(key) 결과값이 map.end()값과 같다면, 원소가 없다는 뜻이다. *만일 원소가 있다면, map::iterator 를 반환하고, iterator는 -> 연.. 2024. 9. 1.
[회고록] 백준 PLATINUM 달성 https://solved.ac/en/profile/moonlight0815 백준 플레티넘 달성한 겸 간단한 회고2022년 겨울방학 때 경영학과에서 소프트웨어학과로 전과하며 막막한 심정으로 알고리즘 공부를 시작했다. KOALA라는 항공대 알고리즘 학회에서 스터디를 하며 공부를 시작했는데, 막막하게 시작한 것 치고 적당히 재미있게 스터디에 임했었다..ㅋㅋㅋ (지금은 해당 학회의 운영진이라는게 참 신기하다 ㅎㅎ) 그리고 참 감사하게도 고등학생 때 1년간 파이썬이랑 자바를 공부했어서 나름 힘들이지 않고 알고리즘 뿐만이 아니라 소프트웨어쪽 공부에 적응할 수 있었다. 2학년 올라와서는 자료구조랑 AI랑 알고리즘이랑 UMC(연합동아리) 하면서 학과 지식도 쌓고 프로젝트 경험도 했다. UMC 덕분에 선배들과 스터디도.. 2024. 8. 28.
[백준/C++] #4195 친구 네트워크 (Union Find) 문제https://www.acmicpc.net/problem/4195 구상친구 관계가 주어지고, 친구 네트워크에 몇 명이 있는지 구해내는 문제였다. 그래서 서로 중복되지 않는 부분 집합들로 나눠진 원소들에 대한 정보를 저장하는 Disjoint Set 자료구조를 사용해야겠다 싶었고, Disjoint Set를 표현하기 위해서 Union Find 알고리즘을 사용해야했다. Union Find에서 집합(네트워크)을 구현할 때 벡터, 배열, 맵 등의 자료구조를 이용할 수 있는데, 나는 unordered map을 선택했다. 처음에 벡터를 이용하는 방식으로 구현했었는데, 불필요하게 벡터의 크기가 커졌다. 그래서 네트워크를 표현하는 딱 필요한 연결리스트만 표현하기 위해서는 map을 사용하면 좋겠다는 생각이 들었고, 데이.. 2024. 8. 28.
[백준/C++] #1696 중앙값 구하기 (자료구조) 문제https://www.acmicpc.net/problem/2696 구상정렬을 적용한 배열(벡터)이나 우선순위 큐를 사용하여 해당 상황에서의 중앙값 판별해야겠다 싶었다. 그런데, 새로운 원소가 들어올 때마다 벡터를 정렬시키는 방법이랑 우선순위 큐 하나를 이용하여 push, pop을 반복하는 방법은 시간복잡도가 너무 컸다.  우선순위 큐 하나를 사용하여 push, pop을 반복하며 중앙값을 구한다고 하면 최악의 경우 O(T * M * M logM)이 걸린다. *우선순위 큐에서 요소 하나 삽입하거나 삭제할 때 O(logN) 소요.*요소 M개라 가정하면 테케 하나에 전체 수열의 길이가 M이라면, 중앙값들 구할때 O(M *  M logM) 소요.(원소 하나 추가할 때마다 pop 반복하며 중앙값 구해야 함 * .. 2024. 8. 27.

티스토리툴바