my devlog;

큐 -> 먼저 들어온 항목이 먼저 나가는 특수한 선형 리스트, 선입선출(FIFO) 구조. ○ 큐 ADT enqueue(q, item) :: = 새로운 원소 item을 큐 q에 삽입 dequeue(q) :: = 큐가 비어있지 않으면 큐 q에서 원소 삭제 후 반환 peek(q) :: = 큐가 비어있지 않으면 큐 q에서 원소 삭제하지 않고 원소 값만 반환 is_empty(q) :: = 큐가 비어있으면 true, 아니면 false를 반환 is_full(q) :: = 큐가 가득 차 있으면 true, 아니면 false를 반환 size(q) :: = 큐에 있는 원소의 개수를 반환 (length(q)) visit(q) :: = 큐에 있는 모든 원소 출력 (display(q), print(q)) ○ 배열을 이용한 큐 ·..

주의할 점 : DNA s1,s2....sn 중 Hamming Distance의 합이 가장 작은 DNA si를 찾는 것이 아니라, 가장 작은 DNA s를 구하는 것이다. 처음에 문제를 잘못 이해해서 잘못 풀었다. #include #include #include using namespace std; int n, m; string s[1001]; char result[1001]; int ncount[4]; int main(void) { cin >> n >> m; for (int i = 0; i > s[i]; } int hammingD = 0; for (int i = 0; i < m; i++) { fill(ncount, ncount + 4, 0); for (int j = 0; j ..

마이너스가 한 개라도 나온 이후에는 무조건 빼줘야 한다는 점을 파악하면 쉽게 풀 수 있다. 디버깅 기록 : 필요했던 것 1. 문자열에 포함되어 있는 상수를 어떻게 변형시킬 것인지. stoi함수를 이용하는 방법도 있고, char에서 '0'을 뺀 후 일일이 10배씩 해주는 방법도 있다. 2. 마지막 처리. for문에서 마지막 시행을 제외시키는 방법도 있고, '\0'문자를 이용해 for문 안에서 따로 처리하는 방법도 있다. 3. boolean 변수 사용. boolean 변수같은 경우는 해당 변수가 true일 때 어떤 상태를 의미하는지까지 잘 전달해야 한다. 다음에는 더욱 유의할 것.

그리디 문제는 대부분 문제를 있는 그대로 받아들이기보다는, 문제에서 요구하는 바를 제대로 한 번에 구할 수 있는 방법을 간파해야 해서 까다롭다. 그게 한 번에 보이면 바로 풀리는데, 그렇지 않으면 이 문제처럼 계속 틀리게 된다. 디버깅 기록 : 작은 수부터 위치를 찾는다면, 아직 비어있는 위치는 자신보다 큰 수가 올 예정이라는 것을 알 수 있다. 따라서 맨 앞부터 훑으면서 아직 원소가 들어가 있지 않은 자리의 개수를 세어서 입력받은 수와 일치된 후에 원소를 삽입하면 된다. 작은 수부터 위치를 찾아야 한다는 점, 입력 위치를 찾는 수의 입장에서 아직 비어있는 자리는 내가 들어가지 않는 이상 나보다 큰 수가 위치할 자리라는 점을 파악해야 풀 수 있다.

위상 정렬을 구현해볼 수 있는 기본 문제 주의할 점이 딱히 없다. #include #include #include #define MAX 32010 using namespace std; int N, M; int inDegree[MAX]; vector a[MAX]; void input() { cin >> N >> M; for (int i = 0; i > A >> B; a[A].push_back(B); inDegree[B]++; } } void topologySort() { int result[MAX]; queue q; for (int i = 1; i

필수로 지나야 하는 정점이 두 개 주어지는 최단 경로 문제. 주의할 점: 필수 정점의 순서는 주어지지 않는다. v1을 먼저 가도 되고, v2를 먼저 가도 된다. #include #include #include #include #define MAX 805 #define INF 98765432 using namespace std; int N, E, v1, v2; vector graph[MAX]; int d[MAX]; void init() { for (int i = 1; i > N >> E; for (int i = 0; i > a >> b >> c; graph[a].push_back(make_pair(b, c)); graph[b].push_back(make..

Dijkstra 알고리즘을 활용해볼 수 있는 간단한 문제 주의할 점: 1. 가중치가 가장 작은 간선을 구할 때, 직접 비교하면 시간이 초과하므로 우선순위큐를 활용한다. 2. cin,cout은 scanf,printf보다 오래 걸린다. #include #include #include #define MAX 20010 #define INF 987654321 using namespace std; int V, E, start; vector a[MAX]; int d[MAX]; void dijkstra() { priority_queue pq; d[start] = 0; pq.push(make_pair(0, start)); while (pq.empty() == 0) { int current = pq.top().second..

스택 -> 삽입과 제거가 한쪽 끝에서만 이루어지는 특수한 선형 리스트. 후입선출(LIFO) 구조. ○ 스택 ADT create(s) :: = 스택 s를 생성한다. is_empty(s) :: = 스택 s가 비어있는지를 검사한다. is_full(s) :: = 스택 s가 가득 찼는가를 검사한다. push(s,e) :: = 스택 s에 원소 e를 삽입한다. pop(s) :: = 스택 s에서 가장 최근에 삽입된 원소(top 위치에 있는 원소)를 삭제하면서 그 값을 반환한다. peek(s) :: = 스택 s에서 가장 최근에 삽입된 원소(top 위치에 있는 원소)의 값을 반환한다. ○ 스택의 구현 · 배열을 이용한 스택의 구현 : 1차원 배열 stack[], 가장 최근에 입력되었던 자료를 가리키는 변수 top. 공백상..

○ 리스트 ADT add_last(list,item) :: = 리스트의 맨끝에 원소를 삽입한다. (insert()) add_first(list,item) :: = 리스트의 처음에 원소를 삽입한다. add(list,pos,item) :: = pos 위치에 원소를 삽입한다. delete(list, pos) :: = pos 위치의 원소를 제거한다. delete(list,item) :: = 리스트에서 원소 item을 제거한다. clear(list) :: = 리스트의 모든 원소를 제거한다. (erase()) is_in_list(list,item) :: = item이 리스트 안에 있는지 검사한다. (member()) get_entry(list,pos) :: = pos 위치의 원소를 반환한다. (return()) g..

연결 리스트 : 여러 노드들의 연결로 이루어진 리스트. 각 노드는 데이터 값을 저장하는 데이터 필드와 다른 노드의 주소값을 저장하는 링크 필드로 이루어져 있다. 노드의 삽입과 삭제가 용이하며 연속된 메모리 공간이 필요하지 않고 배열에 비해 크기 제한이 없다는 장점과 다소 구현이 어렵다는 단점이 있다. ▷ 연결 리스트의 종류 - 단순 연결리스트 : 하나의 링크 필드를 이용해 연결. 마지막 노드의 링크 값은 NULL. · 단순 연결 리스트 생성 : ListNode 구조체 생성, 동적 메모리를 할당 받아 연결 리스트 생성 //단순 연결 리스트 구현 typedef int element; typedef struct ListNode{ element data; struct ListNode *link; } ListNo..