QQ의 다이어리

문제 https://www.acmicpc.net/problem/8979 8979번: 올림픽 입력의 첫 줄은 국가의 수 N(1 ≤ N ≤ 1,000)과 등수를 알고 싶은 국가 K(1 ≤ K ≤ N)가 빈칸을 사이에 두고 주어진다. 각 국가는 1부터 N 사이의 정수로 표현된다. 이후 N개의 각 줄에는 차례대로 각 www.acmicpc.net 풀이 벡터의 배열을 만들어서 각 나라별로 메달 수를 저장했다. 처음에는 각 메달에 가중치를 곱해서 구하려고 했는데 그렇게 되면 금메달을 하나도 못 받아도 동메달을 많이 받으면 등수가 높아지므로 문제에 맞지 않다. 따라서 금은동 순서대로 벡터에 저장하고, 미리 k번째 나라의 금은동 개수를 배열에 저장해 둔다. 이 배열과 모든 벡터를 비교하면 된다. 금메달 개수부터 확인해가..

map은 검색, 삽입, 삭제가 O(logn)인 레드블랙트리로 구현되어 있다. key 값과 value 값을 가지며, 중복된 값은 제거되고 오름차순으로 정렬된다. c++에서 사용시, #include 을 해줘야 하며, map 헤더파일을 추가하면 중복이 허용되는 mulitmap도 사용할 수 있다. - 선언 map m; //key 값의 자료형은 string, value 값의 자료형은 int 기본적으로 key 값인 string 데이터가 오름차순으로 정렬되어 값이 들어가지만, 내림차순으로 정렬하고 싶다면 map m; (하지만 greater라고 한다고 해서 key 값이 아닌 value 값으로 정렬할 수는 없다.) - 데이터 삽입 m.insert({"abc",1}); - find map에 특정 값이 존재하는지 확인 후,..

문제 https://www.acmicpc.net/problem/1244 1244번: 스위치 켜고 끄기 첫째 줄에는 스위치 개수가 주어진다. 스위치 개수는 100 이하인 양의 정수이다. 둘째 줄에는 각 스위치의 상태가 주어진다. 켜져 있으면 1, 꺼져있으면 0이라고 표시하고 사이에 빈칸이 하나씩 www.acmicpc.net 풀이 정답 비율이 낮아서 지레 겁먹었는데 그냥 차근차근 풀면 되는 문제이다. 정답 비율이 낮은 것은 출력 조건까지 읽지 않은 사람이 많아서 인 것 같다.. 한 줄에 20개만 출력해야 한다는 조건이 있어서 그 조건도 출력할 때 고려해줘야 한다. 대단한 알고리즘이 필요한 문제는 아니고 그냥 1이 입력되면(남학생이면) 뒤에 입력받은 수의 배수들을 돌면서 값을 바꿔주고, 2가 입력되면(여학생이..

문제 https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 풀이 최단 거리를 구해야 하므로 BFS를 이용한다. BFS는 시작 노드에서 가까운 노드를 먼저 방문하기 때문에 BFS로 탐색하다가 먼저 찾아지는 답이 최단거리가 되기 때문이다. 코드 #include #include using namespace std; int n,m; bool visited[100][100]; //방문여부 int map[100][100]; //미로 int cnt[100][100]; //경로 세기 int dx..

문제 https://www.acmicpc.net/problem/4963 백준에서 그래프 탐색 알고리즘 문제를 찾아보면 같은 방법으로 풀 수 있는 유사한 문제가 많다.(2667, 1012..) 풀이 DFS를 이용하여 풀 수 있는 문제이다. 유의할 점은 상하좌우뿐만 아니라 대각선으로 연결된 것까지 인접했다고 보므로, 상하좌우, 4방향의 대각선까지 8방향을 전부 탐색해야 한다. 따라서 배열 dx 와 dy를 선언하여 각 좌표에 더해줌으로써 8방향을 전부 확인할 수 있다. 이때 탐색하려는 좌표가 map의 범위를 넘어가지 않는지를 확인해줘야 한다. 배열을 돌다가 방문하지 않았고, map의 값이 1인 좌표를 만나면 dfs를 수행한다. 이 좌표에서부터 DFS를 수행하고 함수가 종료되면 인접한 좌표를 다 탐색했다는 것이..

문제 https://programmers.co.kr/learn/courses/30/lessons/42577 코딩테스트 연습 - 전화번호 목록 전화번호부에 적힌 전화번호 중, 한 번호가 다른 번호의 접두어인 경우가 있는지 확인하려 합니다. 전화번호가 다음과 같을 경우, 구조대 전화번호는 영석이의 전화번호의 접두사입니다. 구조 programmers.co.kr 풀이 A = 119, B = 11914332인 경우와 같이 A 전화번호가 B 전화번호의 앞부분과 같다면 A는 B의 접두어이다. 전화번호 목록이 주어졌을 때, 접두어가 있다면 false, 없다면 true를 리턴하면 된다. 먼저 입력된 전화번호 목록을 정렬한다. 이렇게 하면 인접한 전화번호만 확인하면 접두어가 사용되었는지를 확인할 수 있다. for문을 돌면..

개념 우선순위 큐란 우선순위가 높은 데이터를 먼저 꺼내는 자료구조이다. 우선순위 큐는 보통 힙으로 구현한다. 힙은 Max heap, Min heap이 있는데, Max heap은 부모노드가 자식노드보다 큰 힙이고, Min heap은 부모노드가 자식노드보다 작은 힙이다. 따라서 오름차순으로 정렬할 경우에는 Min heap을, 내림차순으로 정렬할 경우에는 Max heap을 사용한다. c++에서는 헤더파일을 이용하여 우선순위 큐를 간단하게 구현할 수 있다. 구현 (queue 헤더파일 사용 x) - heap에 데이터 추가 void addToHeap(int v, int last) { int cur = last +1; int parent = cur/2; arr[cur] = v; while(1) { if(arr[par..

코드 - 노드 생성 typedef struct node { int i; struct node *left; struct node* right; }node; - BST에 삽입 void add(int n) { node* newnode = (node*)malloc(sizeof(node)); //노드 생성 newnode->i=n; newnode->left=newnode->right=0; if(root = 0) //BST가 비어있는 경우 { root= newnode; return; } node*cur = root; while(1) //BST가 비어있지 않은 경우 { if(newnode->ii) //넣으려고 하는 노드가 현재 가리키는 노드의 값보다 작다면 { if(cur->left==0) //왼쪽에 들어가야 하므로 ..

개념 First in First Out의 특성을 갖는 자료구조로, 먼저 들어온 값이 제일 먼저 나간다. 큐에 값을 집어 넣는 enqueue는 큐의 rear 인덱스를 이용하여 이뤄지고, 큐에서 값을 빼내는 dequeue는 큐의 front 인덱스를 이용하여 이루어진다. 따라서 front와 rear라는 인덱스를 이용하여 큐의 삭제와 삽입 연산을 수행한다. 구현 #include #define Queue_size 5 using namespace std; int queue[Queue_size]; int front=0,rear=0; int isqempty() //front와 rear가 같은 곳을 가리킨다면 큐가 비었다는 의미 { return (front==rear) ? 1:0; } int isqfull() //fro..

개념 Last in Frist Out의 특징을 갖는 자료구조로, 먼저 들어간 값이 제일 마지막에 나오게 된다. 스택에서 값을 빼는 pop과, 스택에 값을 집어 넣는 push는 스택의 같은 방향에서 이루어진다. 구현 (C++) #include using namespace std; #define SZ 10 int stack[SZ]; int top = -1; int isempty() // top이 -1이면 스택이 비어있다는 의미 { return (top==-1); } int isfull() // top이 스택의 크기와 같다면 스택이 가득 차있다는 의미 { return (top==SZ); } void push(int n) { if(isfull()==1) return; top++; stack[top] = n; r..