본문 바로가기

전체 글94

[KAUPC/C++] 캣타워 돌리기 (Simulation) 문제https://www.codetree.ai/problems/rotate-cat-tower/description 코드트리 | 코딩테스트 준비를 위한 알고리즘 정석국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요.www.codetree.ai 구상* 문제에서 주어지는 캣타워의 모습은 위에서 본 모습이 아닌 옆에서 본 모습이다!! 문제 자체만 보면 그냥 캣타워 돌리고 구조물이나 고양이 위로 고양이를 떨어뜨리면 되는, 그리 어려운 문제는 아닌데, 떨어뜨릴 때 다양한 경우의 수를 고려해야했다. 반시계방향이나 시계방향으로 돌리는 로직은 조금 까다로웠지만, 그래도 인덱스만 잘 고려하면 쉽게 구현할 수 있었다. if (dir == 1) { //.. 2024. 9. 5.
[백준/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.
[백준/C++] #24229 모두싸인 출근길 (Greedy) 문제https://www.acmicpc.net/problem/24229 구상문제를 읽고나서 DP나 greedy 종류의 문제인 것 같았다. 이전에 이동한 곳을 벡터든 변수든 큐든 저장을 해놓고 다음 위치로 이동할 수 있는지 없는지 확인 한 후 이동시키는 거였으니까. 문제는 한 장소에서 이동할 수 있는 유효 거리 안에 판자 여러개가 있을 수 있고, 무조건 가까운 판자를 고르거나 먼 판자를 고르는 것이 정답이 아니라는 점이었다. 그래서 우선순위 큐(max heap)를 사용하여 현재 위치(R)에서 이동할 수 있는 모든 판자를 구하면서 큐에 해당 판자의 R을 넣었다. 그렇게 큐에 원소가 없을 때까지 최종 도달 위치를 가장 먼 곳으로 갱신하다 보면 답이 도출된다.  문제 자체는 쉬웠는데 구현이 좀 빡셌다. 자잘자잘.. 2024. 8. 26.
[백준/C++] #2263 트리의 순회 (divide and conquer) 문제https://www.acmicpc.net/problem/2263 구상트리의 전위, 중위, 후위 순회와 관련한 문제였는데, 1년 전에 자료구조를 배웠던게 가물가물해서 다시 찾아서 공부해보았다. 아래 포스팅에 너무 잘 나와있어 풀이에 도움이 되었다. https://ldgeao99.tistory.com/402 챕터7-2. 트리 | 순회방법(전위, 중위, 후위)트리의 순회(Tree Traversal) - 트리도 그래프이기 때문에 DFS와 BFS 방식 모두 가능하다. - 그런데 트리에서만 가능한 아래의 3가지 방법이 있다.(각각의 차이는 루트 노드의 방문을 언제 하냐의 차이)ldgeao99.tistory.com 우선, 세가지 순회의 특성에 대해 간략히 말해보자면, 전위 순회는(Preorder) 루트 -> 왼.. 2024. 8. 24.
[백준/C++] #1074 Z (divide and conquer) 문제https://www.acmicpc.net/problem/1074 이전에 풀었던 문제인데, 분할정복 문제를 안푼지 하도 오래돼서 나름 분할정복의 클래식 문제라고 생각하는 'Z' 문제를 다시 풀었다. 2달 전에 왜 파이썬으로 풀었었는지는 모르겠지만..ㅋㅋ C++로 다시금 풀어보니까 감회도 새롭고 좋았다. 구상분할정복 유형이라는 걸 알아서 그랬는지 정말 쉽고 빨리 풀었다. 거의 로직 구상 3분에 구현 2분? 정도 걸렸던 것 같다. 나는 보통 입력값을 보고 로직을 구상하는 편인데, Z모양이 반복되는 횟수(?) N과 행과 열이 주어지니까 N의 크기만큼 반복해서 행과 열을 변화시켜가며 방문 순서를 업데이트하면 되겠다!는 생각을 했다. 우선 가장 큰 틀부터 가장 작은 틀까지 차례로 고려하며 행과 열을 통해 각각.. 2024. 8. 24.
[백준/C++] #14938 서강그라운드 (Dijkstra) 문제https://www.acmicpc.net/problem/14938구상수색 범위 때문에 낙하지점마다 갈 수 있는 지역들이 다르고, 각 지역들에서 얻을 수 있는 아이템 수가 다르다. 이때, 어떤 지점에 낙하를 해서, 얼마나의 아이템을 얻을 수 있는지 묻는 문제였다.  즉, 한 지점에서 출발을 하면, 최단거리가 수색 범위 이하인 곳들을 추출하고, 그렇게 갈 수 있는 지역들에서 얻을 수 있는 아이템들을 다 더하면 하나의 출발지에서 얻을 수 있는 아이템 수들을 구할 수 있다. 그래서 결국 이문제의 키 포인트는 최단거리가 수색 범위 이하인 곳들을 추출하는 것이고, 각 길마다 거리가 다르므로, 결국 가중치가 있는 그래프에서 시작 노드로부터 다른 모든 노드까지의 최단 경로를 찾는 데에 사용되는 Dijkstra 알.. 2024. 8. 21.
[백준/C++] #1005 ACM Craft (DP) 문제https://www.acmicpc.net/problem/1005구상문제를 보다가 문득 그래프는 없겠지..?라는 생각이 들었다. 만약 그래프에 사이클이 존재한다면, 사이클을 이루는 건물들 간에는 순환 의존 관계가 형성된다. 즉, 건물 A를 짓기 위해 건물 B가 필요하고, 건물 B를 짓기 위해 건물 C가 필요하며, 건물 C를 짓기 위해 다시 건물 A가 필요하게 되는 모순이 발생한다. 이러한 상황에서는 어떤 건물도 완성될 수 없으므로 건물 건설이 불가능하다. 문제에서 모든 건물이 완성될 수 있다고 나와있었기에 그래프에 사이클이 포함되지 않는다는 것을 확증할 수 있었다.!! 구한 이전 건물의 건설 소요시간을 구했다면 다음 건물의 소요시간을 구하는 로직만 짜면 되기에 dp 알고리즘을 사용하는 문제라는 생각이.. 2024. 8. 9.
[백준/C++] #1913 달팽이 (Simulation) 문제https://www.acmicpc.net/problem/1913  구상나는 보통 문제에 명시되어있는 조건들을 이용해서 풀이를 찾는 편이다. 입력 조건이 홀수인 자연수 N이라고 나와있었고, 도출해야 하는 최종 배열의 (0,0) 값이 항상 홀수인 자연수의 제곱이 되는 수였다. 그래서 아래 사진과 같이 한겹 한겹 따로 계산해주는 방식을 택했다. 그리고, 상단, 우측, 하단, 좌측 순서로 몇개씩 배열에 넣으면 될까 그림을 그려봤는데, 2 -> 4 -> 6 -> .. 이런식으로 규칙이 명확해서 더 쉽고 빠르게 풀어낼 수 있었다.  시뮬레이션에서는 다시금 첫값, 끝값이 중요하다는 것을 깨달았다.   풀이 + 코드#include#include#include#include#include#define MAX 101.. 2024. 8. 5.
[코드트리/C++] 배열 회전 (Simulation) 문제https://www.codetree.ai/training-field/search/problems/array-rotation/description?page=1&pageSize=20&name=%EB%B0%B0%EC%97%B4+%ED%9A%8C%EC%A0%84 코드트리 | 코딩테스트 준비를 위한 알고리즘 정석국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요.www.codetree.ai 사각형 자체를 돌리는게 아니라서, 껍질별로 각각 돌려야 한다.수학적으로 무슨 규칙이 있지 않을까해서 상신오빠랑 머리 좀 싸매다가 결국 그냥 가장 처음 생각해낸 방법으로 코드를 짰다 ㅋㅋㅋㅋ 역씌 원초적인게 답이다. 일단 시간복잡도 안에 들어올 수 있다.. 2024. 8. 5.

티스토리툴바