안 쓰던 블로그

트리 개념, 이진 트리, C로 트리 구현: https://foxtrotin.tistory.com/184 이진 트리 순회 모든 원소를 빠뜨리거나 중복하지 않고 처리하는 연산 이진 트리의 순회를 위한 세부 작업 1. 현재 노드를 방문하여 처리 2. 현재 노드의 왼쪽 서브 트리로 이동 3. 현재 노드의 오른쪽 서브 트리로 이동 순회 종류 1. 전위 순회 2. 중위 순회 3. 후위 순회 1. 전위 순회 작업 순서: 현재 노드->왼쪽->오른쪽 이런 트리가 있다면 순회 경로는 A-B-D-H-E-I-J-C-F-G-K 수식에 대한 전위 순회 A*B-C/D 라는 수식을 전위 순회로 트리를 만들면 위와 같다 순회 경로: -*AB/CD -를 킵해두고 A*B 계산, C/D 계산. 두 값으로 -계산 2. 중위 순회 작업 순서:..

트리 원소들 간에 1:n 관계를 가지는 비선형 자료구조 원소들 간에 계층 관계를 가지는 계층형 자료구조 상위 원소에서 하위 원소로 내려가면서 확장되는 트리 모양 구조 노드: 트리의 원소 -트리 A의 노드: A,B,C,D,E,F,G,H,I,J,K,L 루트 노드: 트리의 시작 노드, 레벨0 -트리 A의 루트 노드: A 간선: 노드를 연결하는 선, 부모-자식 노드 연결 형제 노드: 같은 부모 노드의 자식 노드들 -B,C,D는 형제 노드 조상 노드: 간선을 따라 루트 노드까지 경로에 있는 모든 노드들 -K의 조상 노드: F, B, A 서브 트리: 부모 노드와 연결된 간선을 끊었을 때 생성되는 트리 -각 노드는 자식 노드의 개수 만큼 서브 트리를 가짐 -D를 부모로 가지는 H,I,J는 D라는 서브 트리 자손 노드..

https://www.acmicpc.net/problem/1699 어떤 수 n을 제곱수들의 합으로 표현할 때에 그 항의 최소개수를 구하는 문제 처음 접근 방식 1. 무식하게 접근 n=11이라고 했을 때 for문 하나를 돌면서 n보다 작으면서 가장 큰 제곱수 k를 찾는다 3^2=9니까 k=3 while문을 n>0이고 k!=0일 때까지 돌면서 n에서 k^2을 뺄 수 있을 때까지 뺀다 뺄 수 없다면 k--로 넘어간다 이 방법을 재귀로 바꾼다 2. 재귀로 완전 탐색 이런 식으로 돌면서 cnt로 항을 세면 됐다 이 재귀를 DP로 바꾼다 3. DP로 변환 근데 여기서 막혔다 로직은 k가 1부터 올라가면서, m에 합을 저장하고 dp[k][m]은 합이 m일 때의 항의 최소 개수로 뒀다 (그림에서는 a가 있지만 잘못씀)..

1. 다음 프로그램의 실행결과를 예측해 보시오 # include void fun(int x) { x = 30; } int main() { int y = 20; fun(y); printf("%d", y); return 0; } 더보기 답: 20 값에 의한 호출로 main안의 y변수 값은 바뀌지 않는다 2. 다음 프로그램의 실행결과를 예측해 보시오 # include void fun(int* ptr) { *ptr = 30; } int main() { int y = 20; fun(&y); printf("%d", y); return 0; } 더보기 답: 30 주소에 의한 호출로 main안의 y변수 값이 바뀐다 3. 다음 프로그램의 실행결과를 예측해 보시오 #include int main() { int* ptr; ..

스택이란 ‘쌓아올린 더미’를 말합니다. 책을 쌓아서 탑을 만들면 스택이고, 편의점 냉장고에 캔음료수가 일렬로 줄 서 있는 것도 스택입니다. 이렇듯 스택은 마지막으로 들어온 것부터 나가는 특징을 가지고 있습니다. 책 탑에서 맨 아래 책을 빼면 무너지고, 편의점에서 음료수를 앞에서부터 빼지 못 하는 점을 생각하면 됩니다. 그런 현실의 개념을 추상화한 것이 바로 스택입니다. 스택을 가지고 주로 삽입, 삭제, 검색 작업을 하는데, 스택의 특징에 따라 가장 최근에 들어온 데이터를 빼고, 아니면 그 뒤에 새로운 데이터를 넣게 됩니다. 스택의 특징을 영어로는 LIFO(Last In First Out), 한자로는 후입선출이라 합니다. 여기서 중요한 건, 편의점의 캔음료를 중간에 있는 것부터 뺄 수 없듯 이 스택에서도 ..

교내대회에서 멘탈공격맞고 K.O 브론즈~실버나 돌아야겠다 17362 수학은 체육과목입니다2 1 2 3 4 5 6 7 8까지 하면 한 사이클을 도니까 8로 나눌 건데 수를 직접 써보면 알겠지만 14 15 16같이 오른쪽에서 왼쪽으로 넘어가는 수는 나머지가 1~5로 나오지 않음 그 경우만 예외로 해주면 된다 6이 나오면 4 출력, 7이면 3출력, 8이면 8로 나누고 있어서 나머지가 0이니까 나머지가 0일때는 2출력 10757 큰 수 A+B 파이썬으로 하면 그냥 출력하면 된다 갓-언어 C++로 보면 처음 딱 봤을 때는 string으로 a b를 받고 한 자리씩 int형으로 변환해서 더해주는데 만약 올림이 있다면 carry변수에 저장 해서 다음 자리의 sum을 구할 때 1을 더 더한다 라고 생각했음 근데 더 간단..

https://www.acmicpc.net/problem/7578 7578번: 공장 어떤 공장에는 2N개의 기계가 2열에 걸쳐 N개씩 배치되어 있다. 이 2개의 열을 각각 A열과 B 열이라고 부른다. A열에 있는 N개의 기계는 각각이 B열에 있는 N개의 기계와 하나씩 짝을 이루어 케이블� www.acmicpc.net 예제 그림을 보면 교차하는 부분은 3곳 교차하는 지점의 특징: 똑같은 132가 있어도 A에서의 위치와 B에서의 위치가 다르다 A[i]를 A에서 i의 위치, B[i]를 B에서 i의 위치라고 치면, A[i]B[j] 조건이 성립하면 접점 1개가 생긴다고 할 수 있다 그냥 반복문으로 단순 구현하면 A를 i로 돌면서 j로 조건에 맞는 수가 있는지 찾는 2중for문이 되고 O(n^2)의 시간복잡도로 5..