MZ 개발자

N개의 단어가 주어졌을 때 알파벳의 숫자(0~9)를 결정하고 단어를 숫자로 치환하여 수의 합을 최대로 만드는 문제이다. 처음에는 자릿수를 생각하지 않고 단순히 길이가 긴 단어의 첫번째 알파벳을 큰 값으로 설정하면 될것 같다고 생각하였다. 그래서 N개의 단어를 길이 기준으로 우선순위 큐에 넣고 하나씩 뽑으면서 subString을 구한 후 다시 큐에 넣어주는 방법으로 구현하였다. 예제는 모두 통과하였지만 1%에 틀렸다고 나왔다. 😂 그리고 질문 개시판을 확인해보다가 반례를 찾을 수 있었고 틀린 이유는 각 알파벳 마다 자릿수 가중치가 존재하고 이 가중치에 따라 결과가 달라질 수 있다는 것을 알게 되었다. 예를들어 N=10 ABB BC BC BC BC BC BC BC BC BC 다음과 같이 주어졌을 경우 길이를..

문자열 파싱을 연습해볼수 있는 괜찮은 문제이다. 풀이 방법은 여러가지 존재하는데 보통 풀이는 다음과 같다. 최솟값을 만들기 위해 가능한 가장 큰 숫자를 빼야 한다. 따라서 - 를 기준으로 문자를 나누고 다음 - 를 만나기 전까지 모두 더해서 한번에 빼주면 된다. 나는 조금 고전적이지만 스택을 사용하여 숫자와 - 기호를 쌓았다. 이후 하나씩 빼면서 - 를 만나기 전까지 결과를 모두 더하고 - 를 만나면 더한 값을 -1곱하여 누적 시켜주었다. #include #include #include #include #include using namespace std; int main() { ios_base::sync_with_stdio(false); cin.tie(0); string s; cin >> s; stack..

이 문제를 풀면서 아직 실력이 많이 부족하다는 것을 느꼈다. 처음 생각해낸 방법은 덱을 사용해서 문제마다 모든 조건을 처리해주는 정신 나간 짓을 하려고 하였다. 2번 3번 조건을 만족하기 위해 현재 내가 풀고있는 문제(now)가 있고 이 문제를 풀기 이전 풀어야할 문제(pre)를 설정하고 이상한 뻘짓을 많이 하였다... 문제를 보는 순간 어떤 알고리즘을 물어보는지 감이 오지 않아 어떻게든 내가 알고있는 알고리즘 내에서 최대한 풀어보려고 시도하였다. 또한 문제가 잘 이해되지 않았다. 처음에 답이 두개인가?? 생각도 하고 질문 답변을 확인한 결과 조금 이해가 되었다. 어느덧 3시간 고민 후... 각 N 마다 먼저 풀어야하는 문제를 우선순위 큐에 넣어 DFS 탐색까지 도달였다. 하지만 결과는 DFS로는 풀수 ..

문제를 보고 몇시간 정도 풀이를 생각해보다가 도저히 떠오르지 않아 다른 사람 풀이를 참고하여 아이디어를 얻었다. 문제에 간선의 가중치는 100보다 크지 않는 양의 정수라고 하여 특정 노드에서 가장 깊이 들어가야 최소한 최대 길이가 될것 같다는 생각을 하였다. DFS를 생각한것이다. 하지만 DFS 한번만으로 도저히 답을 찾아낼 수 없었다. 풀이를 보니 DFS를 두번 사용 해야 한다고 하였다. 왜 DFS를 두번 사용해야 하는지 이해가 안되다가 다음과 같은 특징을 이해한 다음에 문제를 해결할 수 있었다. 하나의 정점에서 가장 멀리 있는 정점은 원의 지름 부분에 해당하는 정점이다. 즉 어느 점에서 DFS를 통해 가장 긴 점을 찾으면 그 점은 가장 지름이 긴 원의 시작 점이 된다. 이후 그 시작점에서 또 가장 긴..

N개의 수 중에서 M 개의 수가 존재하는지 여부를 0,1로 출력하는 문제이다. 총 M 개의 수가 N에 존재 하는지 알기 위해서 브루트포스 알고리즘을 사용한다면 N*M 즉 10000000000으로 시간초과가 발생한다. 때문에 이분탐색으로 logN 의 시간복잡도를 활용하여 문제를 풀어야 한다. 입력 N은 정렬되어 들어오지 않기 때문에 이분탐색을 위해 정렬이 필요하다. 처음에 STL algorithm에 있는 sort를 활용하여 정렬하였는데 제출하고 나니 시간초과가 발생하였다. 원인이 뭔지 찾아보다가 어떤 사람은 qsort를 직접 구현하면 된다고 하는데, 실제 qsort는 STL에서 제공하는 sort보다 시간이 느리다. 한참 찾아보다가 발견한 원인은 재귀함수 파라미터에 vector를 call by referen..

물의 높이가 0~100 까지 변하는 동안 각 높이마다 잠기지 않는 안전한 영역이 존재한다. 문제 해결 방법은 각 높이에서 안전한 영역의 최대 갯수를 구하는 것이다. 안전한 영역 즉 섬의 갯수를 구하기 위해서 물의 높이보다 높은 영역을 기준으로 DFS를 적용하였다. 핵심은 방문한 영역을 표시 하고 한번 방문한 영역은 DFS에서 제외시켜야 한다. #include #include #include using namespace std; int n; int map[102][102]; bool visit[102][102]; int dx[4] = { 0,1,0,-1 }; int dy[4] = { 1,0,-1,0 }; void dfs(int x, int y, int height) { if(visit[x][y]) { re..

처음 떠오른 방법은 queue에다가 각 인접 노드를 {노드,가중치 합} 로 저장하고 큐를 순회하면서 해당 노드의 가중치 합을 최소로 만들어 주는 것이였다. 즉 BFS 방식을 떠올린 것이다. 하지만 이 문제를 BFS로 풀려면 큐에서 가중치가 0인 노드부터 방문해야 하는 조건이 붙는다. 위에 조건을 적용하지 않아 제출하면 자꾸 8%에서 틀렸다고 나왔다..... BFS로 해결되지 않아 다익스트라를 적용하였다. 다익스트라가 적용될 수 있는 이유는 "가중치가 모두 0 또는 양수이고, 특정 지점 a에서 b 지점까지의 최단 경로 가중치"를 구하는 것이므로 다익스트라 알고리즘을 적용할 수 있다. 하지만 기존 다익스트라와 조금 다른점은 인접노드에 대한 정의가 나와있지 않기 때문에 각 지점에서 인접한 노드를 X+1, X-..

문제에서 여행 계획에 속한 도시 M이 주어지고 총 N 개의 여행 계획이 주어진다. 이때 여행계획을 달성할 수 있는지 없는지 확인하는 문제이다. 문제를 해결하기 위해 생각해낸 아이디어는 다음과 같다. 1. 만약 a-b-d-a-c 순서로 여행한다고 가정하였을경우 a-b, b-d, d-a, a-c 가 연결 되어있다면 무조건 갈수 있지 않을까? 2. 그럼 서로 연결되어있다는 것은 어떻게 알수 있을까? -> union - find를 활용하자!! Union - Find에서 핵심은 각각의 i,j에 대해 각각 root parent를 확인하고 둘중에 더 큰 집합으로 parent를 업데이트 해준다. 이렇게 구한 그래프와 그의 parent 정보를 바탕으로 계획에 있는 도시들이 모두 같은 root parent를 가질경우 여행..

이 문제의 특징은 특정 도시에서 출발하여 최단거리가 정확히 k 인 모든 도시를 출력하는것이다. (단 k인 도시가 존재하지 않은면 -1을 출력한다.) 문제를 읽으면서 최단거리 키워드가 나와 BFS응용 이라는 것을 알게 되었다. 하지만 기존에 내가 풀던 BFS문제는 상,하,좌,우로 이동하는 문제를 주로 풀었다. 비슷한 로직으로 접근하여 각 노드의 간선을 인접리스트로 구현하였고, x노드를 시작으로 갈수 있는 경로를 인접리스트를 순회하면서 탐색하였다. 핵심은 인접리스트 순회시 visited 표시를 하는것이다!!! 순회시 visited를 표시하지 않고 queue에서 pop 할때 visited를 표시해준다면 최단경로를 구할수 없다. 위의 그래프를 인접리스트를 순회할때 queue에 들어가는 값은 다음과 같다 {nod..

행렬의 세로 길이(행 개수) rows, 가로 길이(열 개수) columns, 그리고 회전들의 목록 queries가 주어질 때, 각 회전들을 배열에 적용한 뒤, 그 회전에 의해 위치가 바뀐 숫자들 중 가장 작은 숫자들을 순서대로 배열에 담아 return 하도록 solution 함수를 완성하는 문제이다. 예시는 다음과 같다. 쿼리가 다음과 같이 주어졌을때 각각의 쿼리마다 최소가 되는 숫자는 아래 그림을 통해 알 수 있다. 이 문제는 따로 알고리즘이 들어가지 않는다. 각각의 테두리를 순회하면서 이전 숫자를 기억하고 다음 숫자에 업데이트 해주면 된다. 처음에는 복잡하게 queue에 넣어서 어쩌구 저쩌구 하려고 했는데 뻘짓이였다. #include #include #include #include using name..