Angievelopment

✨ 문제풀이 양방향 연결 리스트 (Doubly Linked List) 를 이용해서 해결하는 문제이다. 정확성 테스트 뿐만 아니라 효율성 테스트가 있기 때문에 연결 리스트로 해결이 가능하다. 연결 리스트의 작동 원리를 잘 이해하면 구현이 어렵지 않은 문제였다. 그러나 나는 연결 리스트 생각해내는 데 도움을 받아야 했다..😭 표가 0 부터 n-1 까지 n개의 행이 있으므로 n개의 노드 배열을 초기화 하고, 각각의 노드에 0 ~ n-1 의 값을 저장한다. 표이기 때문에 처음과 끝은 연결이 되지 않으므로, 맨 처음과 맨 마지막 노드를 제외하고 노드들을 순서대로 양방향으로 연결한다. 그리고 나머지는 연결 리스트의 작동 원리를 이용하면 된다. curr이라는 현재 노드를 가리키는 노드를 만들어서 이동하고, 삭제한다면..

#include #include #include #include using namespace std; int number = 6; int INF = 1000000000; vector a[7]; int d[7]; void init() { for (int i = 1; i nextDistance) { d[next] = nextDistance; pq.push({next, nextDistance}); } } } } void printDistance() { for (int i = 0; i < number; i++) printf("%d ", d[i]); } int main(void) { init(); dijkstra(1); printDistance(); return 0; } 코드 참고 : https://blog.na..

✨ 문제 풀이 노드 i에서 노드 j까지 갈 수 있는 경로가 존재하는지 알아내는 문제이다. 즉 그 사이에 j, l, m ... 등 여러 개의 노드를 통해서 연결되어도 된다는 것이다. BFS를 통해서 연결되어 있는 노드들을 큐에 저장해서 탐색하면서 연결되어 있는지 저장해간다. 약간 다익스트라 알고리즘의 느낌도 난다. 여기서 중요한 것은 양방향 간선이 아니라 단방향 간선이라는 점! 따라서 사이클을 만들면서 자신으로 돌아오면 1이지만 사이클이 없으면 0이라는 것이다!! 나는 route라는 일차원 배열을 만들어서 한 노드가 다른 노드들과 연결 되어있는지 저장했다. route 배열을 0으로 초기화해주고, 방문하면 1을 저장한다. 이미 방문한 노드는 연결이 되어있다는 뜻이니 굳이 안 봐도 되고, 큐를 통해 방문하게 ..

✨ 문제 풀이 그래프와, 각 노드를 지나가는 간선의 비용이 있고, 비용의 합에 제한이 있을 때, 어떤 노드에서부터 순회를 시작하면 가장 많은 아이템(노드의 값)을 모을 수 있는지 물어보는 문제로 다익스트라를 이용해서 문제를 해결했다. 내가 해결한 방법은 아래와 같다. 한 노드에 대해서 다익스트라 순회를 한다. 다른 노드까지의 최소 거리를 d 배열에 저장한다. d 배열에 저장된 간선 비용의 합 중에서, m보다 작은 노드들의 아이템 값을 합친다. 모든 노드에 대해서 반복한다. 가장 아이템값이 높은 값을 반환한다. 모든 노드에 대해서 순회하면서 거리의 비용을 계산해야 하므로 매번 다익스트라 순회를 해주기 전, d 배열의 값을 아주 큰 값(1억)으로 초기화해주는 작업을 했다. (최소 거리를 구하는 것이기 때문)..

다 풀고 나니까 쉬운 문제였는데.. 말도 안 되게 계속 헤매가지고 오래 걸렸다 😕 ✨ 문제 풀이 내가 생각했을 때 이 문제를 풀기 위해서 가장 중요한 부분은 다음과 같았다. 1. 맨해튼 거리 2 이하 내에 두 사람이 위치해 있으면 X 2. 두 사람 사이에 파티션이 존재하면 괜찮음 먼저 맨해튼 거리 2 이하라는 조건을 생각해보았다. 일직선 상에 2칸 이내와 대각선으로 한 칸 이내는 모두 맨해튼 거리 2 이하이다. 그리고 두 번째 조건에 대해 생각해보았다. 일직선 상에 있을 때는 두 사람 사이에 파티션이 존재하는 걸 쉽게 생각할 수 있지만, 대각선 상에 있을 때는 어떻게 파티션이 존재해야 하는지 생각해야 한다. 한 칸 대각선 위에 있는 사람과 거리두기를 만족하려면 두 사람을 이을 수 있는 동서남북 방향이 모..

✨ 문제 풀이 나는 문자열에서 한 글자씩 비교해가면서, 만약 숫자라면 그대로 숫자를 반환하고 zero~nine 의 문자열 중에 하나와 일치하면 그 숫자 (=인덱스)를 반환해주는 식으로 문제를 해결했다. 그래서 중요하게 생각한 부분이 문자열의 몇 번째 인덱스부터 확인할 건지 매개변수로 보내주는 것과, 숫자 또는 영단어에 해당하는 숫자뿐만 아니라 offset을 함께 반환해주는 것이었다. 그래서 두 개의 int를 반환해주어야 하기 때문에 vector를 이용해서 0번째에 저장된 데이터는 일치하는 숫자, 1번째에 저장된 데이터는 offset으로 반환했다. 🗓 코드 #include #include using namespace std; bool isIntegerNumber(char c) { if (c - '0' >=..

https://www.acmicpc.net/problem/13022 13022번: 늑대와 올바른 단어 첫째 줄에 단어가 주어진다. 단어는 w, o, l, f로만 이루어져 있으며, 길이는 50을 넘지 않는다. www.acmicpc.net ✨ 문제풀이 문자열 구현 문제입니다. 저는 다음과 같이 문제를 해결했습니다. 문자열에서 현재 가리키는 문자가 w라면 w가 연속으로 몇 번 나오는지 센다 (count에 저장) wolf가 총 네 글자이므로 4 * count 개의 문자만큼의 문자열이 올바른지 확인한다 count번씩 w, o, l, f 문자가 차례대로 나오는지 확인한다 4*count개의 문자 다음으로 나오는 문자가 w인지 확인한다 (아니면 잘못된 문장) 1. 문자열에서 현재 가리키는 문자가 w라면 w가 연속으로 ..

https://www.acmicpc.net/problem/17609 17609번: 회문 각 문자열이 회문인지, 유사 회문인지, 둘 모두 해당되지 않는지를 판단하여 회문이면 0, 유사 회문이면 1, 둘 모두 아니면 2를 순서대로 한 줄에 하나씩 출력한다. www.acmicpc.net ✨ 문제 풀이 문장의 앞에서 부터 문자를 짚어나가는 포인터와, 맨 뒤에서부터 문자를 짚어나가는 포인터 두 개를 이용하는 문제입니다. 앞에서부터 보는 포인터를 x, 뒤에서부터 보는 포인터를 y라고 정의합니다. 문장의 길이가 홀수일 때 가운데 문자는 무엇이든 상관없고 짝수일 때는 x=y-1일 때까지 비교하므로 x

Heap 개념 완전 이진 트리의 일종으로 우선순위 큐를 위하여 만들어진 자료구조 여러 개의 값들 중에서 최댓값이나 최솟값을 빠르게 찾아내도록 만들어진 자료구조 우선순위 큐를 구현하기 위하여 만들어진 자료구조 우선순위 큐 우선순위의 개념을 큐에 도입한 자료구조. 데이터들이 우선순위를 가지고 있고 우선순위가 높은 데이터가 먼저 나간다. 이용사례 시뮬레이션 시스템 네트워크 트래픽 제어 운영 체제에서의 작업 스케쥴링 수치 해석적인 계산 반정렬 상태(느슨한 정렬 상태) 를 유지한다. 큰 값이 상위 레벨에 있고 작은 값이 하위 레벨에 있다는 정도 - 간단히 말하면 부모 노드의 키 값이 자식 노드의 키 값보다 항상 큰(작은) 이진 트리를 말한다. 힙 트리에서는 중복된 값을 허용한다. (이진 탐색 트리에서는 중복된 값..

해시 정의 데이터를 저장할 위치 = 인덱스를 간단한 연산으로 구하는 것 내부적으로 배열을 사용해 표를 저장함 다양한 길이를 가진 데이터를 고정된 길이의 데이터로 매핑하는 것 원소의 검색, 추가/삭제도 효율적으로 수행할 수 있음 개념 원소의 개수가 13개인 배열이 있다고 하자 |인덱스|0|1|2|3|4|5|6|7|8|9|10|11|12| |---|-|-|-|-|-|-|-|-|-|-|-|-|-| |키|5|6|14|20|29|34|37|51|69|75|-|-|-| 이 배열에 원소 35를 정렬에 맞게 추가한다고 하자 키 5 6 14 20 29 34 37 51 69 75 해시값(13으로 나눈 나머지) 5 6 1 7 3 8 11 12 4 10 해시값 (hash value) : 데이터에 접근할 때 기준이 되는 값 해..