https://www.acmicpc.net/problem/1212 1212번: 8진수 2진수 첫째 줄에 8진수가 주어진다. 주어지는 수의 길이는 333,334을 넘지 않는다. www.acmicpc.net 8진수를 2진수로 변환하기 수가 0인 경우를 제외하고 1로 시작해야 한다. 💡 8진수 한 자리당 2진수 3자리로 표현해야 한다. 문자열을 사용해서 하면 되는데 여기서 2진수로 바뀔 때 꼭 뒤집어야 한다는 것을 잊으면 안 된다! #include #include #include using namespace std; string changeTo2(char ch){ int x = ch - '0'; string two = ""; if(x == 0) return "0"; while(x != 0){ two += to..

https://www.acmicpc.net/problem/5639 5639번: 이진 검색 트리 트리를 전위 순회한 결과가 주어진다. 노드에 들어있는 키의 값은 106보다 작은 양의 정수이다. 모든 값은 한 줄에 하나씩 주어지며, 노드의 수는 10,000개 이하이다. 같은 키를 가지는 노드는 없다 www.acmicpc.net 어떻게 하면 좋을지 모르겠어서 다른 사람의 코드를 확인했다.🥲 아쉽지만 어떻게 하면 좋을지 익히는 게 더 좋을 것이라고 생각했다. 사실문제를 처음 읽었을 때, 전위 순회로 받아들였기 때문에 전위 순회로 트리를 구성하고, 후위 순회로 탐색해서 출력하면 된다고 생각했다. 그렇게 하기보다는 이진 검색 트리의 특성을 반영해서 바로 후위 순회로 출력할 수 있다!! 일단 입력받은 원소들을 차례대..

https://www.acmicpc.net/problem/1068 1068번: 트리 첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다. 만약 부모가 없다면 (루트) -1이 주어진다 www.acmicpc.net 노드 하나를 지울 것이다. 남은 트리에서 리프 노드의 개수를 구하자. 노드를 지우면 그 노드와 노드의 모든 자손이 트리에서 제거된다. 루트 노드를 구하고 (m==-1 라면 root node) DFS를 root부터 시작해준다. DFS를 사용하면 서브 노드 끝까지 내려가게 되는데, child를 0으로 초기화하고 해당 노드의 서브 트리를 돌고, 만약 자식 노드가 하나도 없다면 1을 리턴하도록 한다..

https://www.acmicpc.net/problem/9934 9934번: 완전 이진 트리 상근이는 슬로베니아의 도시 Donji Andrijevci를 여행하고 있다. 이 도시의 도로는 깊이가 K인 완전 이진 트리를 이루고 있다. 깊이가 K인 완전 이진 트리는 총 2K-1개의 노드로 이루어져 있다. (아래 www.acmicpc.net 각 노드에 빌딩 번호. 가장 마지막 레벨을 제외한 모든 집에는 왼/오 자식 있음 빌딩에 들어간 순서대로 번호를 종이에 적어놓았다. 1. 가장 먼저 루트 빌딩 2. 빌딩 왼쪽 - 현재 - 오른쪽 3. 모두 방문했으면 부모 노드로 이동. 이 문제를 풀어보면 어떻게 트리를 구성하면 될지 감이 잡히게 된다. 강의를 듣거나 문제들을 풀어보면 대체로 이미 구성된 트리로부터 순회를 하..

https://www.acmicpc.net/problem/2346 2346번: 풍선 터뜨리기 1번부터 N번까지 N개의 풍선이 원형으로 놓여 있고. i번 풍선의 오른쪽에는 i+1번 풍선이 있고, 왼쪽에는 i-1번 풍선이 있다. 단, 1번 풍선의 왼쪽에 N번 풍선이 있고, N번 풍선의 오른쪽에 1번 풍선 www.acmicpc.net 1~N번까지 원형으로 풍선이 놓여있다. 풍선 안에는 종이가 들어있다. 1번 풍선 터트리고 안에 있는 종이에 적혀있는 만큼 이동해서 다음 풍선 터트림. 양수면 오른쪽으로, 음수면 왼쪽으로 이동 풍선의 index를 꼭 저장해줘야 쉽게 풀 수 있다. deque 자료구조에 pair를 사용해서 index와 풍선 종이 value를 넣어주고 pop, push 하면 쉽게 풀린다. 원형 dequ..

https://www.acmicpc.net/problem/1966 1966번: 프린터 큐 여러분도 알다시피 여러분의 프린터 기기는 여러분이 인쇄하고자 하는 문서를 인쇄 명령을 받은 ‘순서대로’, 즉 먼저 요청된 것을 먼저 인쇄한다. 여러 개의 문서가 쌓인다면 Queue 자료구조에 www.acmicpc.net 우선순위 큐를 사용해야 하는 문제! 우선순위가 가장 크다는 것을 확인해야 하므로 priority_queue를 사용한다. - 가장 앞에 있는 문서의 중요도를 확인한다. - 나머지 문서 중 현재 문서보다 중요도가 높은 문서가 하나라도 있다면, 이 문서를 queue의 가장 뒤에 재배치. 아니면 바로 인쇄 queue에 문서의 Index와 priority value를 넣어준다. 그리고 이제 맨 앞에 있는 문서..

https://www.acmicpc.net/problem/2164 2164번: 카드2 N장의 카드가 있다. 각각의 카드는 차례로 1부터 N까지의 번호가 붙어 있으며, 1번 카드가 제일 위에, N번 카드가 제일 아래인 상태로 순서대로 카드가 놓여 있다. 이제 다음과 같은 동작을 카드가 www.acmicpc.net queue를 안다면 쉽게 풀 수 있는 문제! #include #include using namespace std; int main(){ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n; queue card; cin >> n; for(int i=1; i

https://www.acmicpc.net/problem/1158 1158번: 요세푸스 문제 첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 5,000) www.acmicpc.net 큐를 사용해서 푸는 문제. 우선 큐는 front에서 pop 되는데 k번째 원소가 빠져야 하므로 어떻게 하면 좋을지 고민했다. 그런데 생각보다 쉽게 그냥 1번째 원소부터 k-1번째 원소를 pop 해서 뒤에 넣어주면 된다. 그러면 내가 제거하고 싶은 k번째 원소를 출력하고 pop 해서 제거해주면 된다! #include #include using namespace std; int main(){ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n,..

https://www.acmicpc.net/problem/2493 2493번: 탑 첫째 줄에 탑의 수를 나타내는 정수 N이 주어진다. N은 1 이상 500,000 이하이다. 둘째 줄에는 N개의 탑들의 높이가 직선상에 놓인 순서대로 하나의 빈칸을 사이에 두고 주어진다. 탑들의 높이는 1 www.acmicpc.net N개의 높이가 다른 탑을 수평 직선의 왼->오 방향으로 세우고 레이저 송신기 서릴 한 탑에서 발사된 레이저 신호는 가장 먼저 만나는 하나의 탑에서만 수신 가능 6 9 5 7 4 왼쪽 방향으로 동시에 레이저 신호 발사 각 탑에서 발사한 레이저 신호를 어느 탑에서 수신하는지 알아내자 생각하는 게 좀 어려웠음.. 뭔가 히스토그램 같은 문제 같은데,, 어떻게 하면 좋을지.. 일단 스택에 모든 원소를 넣..