요약 : c++로 이진 트리, 트리 순회 구현하기(재귀 구조 활용) 알고리즘 설계 수업에서 이진트리 순회(전위 순회, 중위 순회, 후위 순회)를 구현하는 실습문제가 주어졌다! 근데 못풀었다! (ㅜ.ㅜ) 제출은 못했지만 공부는 할 수 있으니까! 백준에 같은 문제가 있어서 풀어보려한다~ 목차 ( 클릭하면 이동! 👈🏻)0. 문제 1. 문제풀이 핵심 2. 문제풀이에 사용된 개념 3. 문제풀이 코드 3-1. 코드 로직 설명 4. 마무리0. 문제https://www.acmicpc.net/problem/1991 1991번: 트리 순회첫째 줄에는 이진 트리의 노드의 개수 N(1 ≤ N ≤ 26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A..

dfs - 그래프 풀듯이 벡터로 만든 리스트 형식 사용 (정석풀이는 아니라고 함. 정석은 유니온 파인드? 아직 모르는 알고리즘이라 공부해야겠다!) 1. 진실을 아는 사람들 번호 -> knowMem 스택에 담고, 방문처리(vis[번호] =1;) 2. [멤버별 속해있는 파티] 와 [파티별 속해있는 사람들] 을 리스트형식 벡터 배열로 선언 3. [멤버별 속해있는 파티]배열을 돌면서 [파티별 속해있는 사람들] 배열을 돌아(이중for문) 3-1) vis[멤버번호] ==0 -> 스택에 담아, vis =1; 4. 진실 아는 사람이 속한 파티 번호들을 set에 저장하여 최종으로 m-set배열사이즈 로 답 구함 stack knowMem;//처음에 진실 알고있던사람 번호, 그로인해 진실 새로 알게된 사람 번호 저장 vec..

재귀 - 시간초과 #include #include using namespace std; int t; long long val[1000002];//날별 주가 int valNum; long long profit; void func(int str){ if(str>=valNum-1) return; int maxIDX= max_element(val+str,val+valNum)-val; //맥스값의 인덱스 받음 if(maxIDX==str) { func(maxIDX+1); return; } long long maxNum = val[maxIDX]; for(int i =str;i 그날 이전 기준으로 그것보다 벨류가 낮은날에는 다 사고 아닌날에는 가만히. 가장 높은 고점날 팔기// //현재+1부터 마지막까지 가장 높은 고..

1번 테케 실패한 코드 (엉망징창) 직접 추가한 테스트 케이스 (모두 성공) 1) [["ICN", "JFK"], ["JFK", "IAD"], ["IAD", "JFK"], ["JFK", "HND"]] & ["ICN", "JFK", "IAD", "JFK", "HND"] 2) [["ICN", "JFK"], ["JFK", "IDD"], ["IDD", "JFK"], ["JFK", "ICN"]] & ["ICN", "JFK", "IDD", "JFK", "ICN"] 3) [["ICN", "JFK"], ["JFK", "IAD"], ["IAD", "JFK"], ["JFK", "IAD"]] & ["ICN", "JFK", "IAD", "JFK", "IAD"] 4) [["ICN", "BOO"], ["ICN", "COO"], [..

분할정복 문제 재귀 연습 문제 실수한 부분 - 문자열로 주어지는 걸 int 이중배열로 받으려고 해서 헤맴 #include #include #include using namespace std; // 0 = 흰색, 1= 검정 int n; char board[65][65]; vector ans; void func(int row, int col, int size){ char cur = board[row][col]; bool devide = false; for(int i =row;i

그리디 - 조건을 따져가며, 특정 번호의 학생에게서 체육복을 빌릴 수있는지확인해가며 품 0. 따로 빌려줄 수 있는 학생번호 저장할 배열 생성 -> reserve에 속한 학생을 인덱스로 표시하고 값을 1로 만들어줌 1. lost중에 reserve에도 속해있는 학생을 erase함. 2. lost, reserve 오름차순 정렬(이거 안해서 테케 13,14인가를 틀리던..) 3. lost 개수만큼 반복돌며 reserve[lost[i]-1]==1인지, reserve[lost[i]+1]==1인지 확인. 빌리고 나서는 해당 reserve 인덱스 값을 0으로 변경.(이제 얘한테는 빌릴 수 없다.) 오름차순 정렬한 이유도 3번처럼 무조건 왼쪽부터 확인해서 체육복 빌렸을때, 서로 겹치는 경우가 없게 하려구. 레벨 1에서 ..

완탐인데 조건따져보며 경우의 수 따져봐야함 & 인덱스 중복X(배열자체에 같은 수가 들어오는건 따로 처리해줘야함), 수열만들기 -> 1. 백트래킹 & 재귀 이용 #include #include #include #include #include using namespace std; int arr[8]; //기본 배열 int mine[8]; //모인 카드 저장할거임 int check[8]; //들어간 수인지 확인 int isExist[7777777]; //같은 숫자 대칭 처리 //ex."011"이 주어졌을때 나오는 101과 같은 조합은 1이 2번주어져있어서 각각의 1이 다른 값으로 처리됨. -> 중복카운트발생 //이를 방지하기 위해 한번 처리한 소수를 인덱스로 표현하여 저장 int n; int answer; v..

bfs - 효율성 실패 집이 우측 하단 맨 끝에 존재함, 오른쪽 또는 아래로만 이동함. -> 막힌 길을 빙 둘러서 가는 경우는 존재 X => bfs로 돌려도 답은 정확히 나옴 #include #include #include using namespace std; #define X first #define Y second //최단 경로가 아니라, 최단 경로의 개수 ? //경우의 수 -> 오른쪽으로 이동, 아래로 이동 int dx[2]= {1,0}; int dy[2]= {0,1}; queue Q; int vis[103][103]; int board[103][103]; int solution(int m, int n, vector puddles) { int answer = 0; //m= 열 개수,n= 행 개수 f..

문제 : https://www.acmicpc.net/problem/1012 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net 문제풀이 핵심 실수 포인트 1. 행 열 입력이 반대였는데 (열 행 순으로 입력받음) 빨리풀다가 발견 못하고..쓸데없이 오래 해멘.. 문제를 잘 읽자 ! 예시의 입력값을 잘 보자, 가로길이 세로길이 그림으로 그려두자 2. 배추밭 담는 배열이랑 방문 여부 담을 배열을 테스트 케이스마다 초기화 해줘야되는 것을 간과함 - > 전역번수로 선언함 문제풀이 코드 #include #include #include u..

bfs 연습 문제! 문제 : https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 문제풀이 핵심 bfs 는 먼저 도달한 값이 가장 최단거리 값이므로 같은 목적지에 두번 이상 방문할 것이라는 예외처리 필요없음. 이라는 부분을 인지하지 못해서 헷갈렸었다. bfs를 잘 쓸 수 있는지가 관건! 그리고 사소한 거지만 #define X first #define Y second 여기에서는 땀흘리면 안되는데 땀흘려서 X와 Y를 사용한 53-54번째 줄에서 expression result unus..