문제https://www.acmicpc.net/problem/1068 풀이트리에서 한 개의 노드를 삭제했을 때, 리프노드의 수를 구하는 문제이다. 어떻게 하면 삭제처리를 하면서, 리프노드를 구할 수 있을까? 문제의 그림을 보면 삭제 노드의 자식 노드들을 모두 삭제처리를 해야하는 것을 보면 dfs를 사용해야겠다는 것을 자연스럽게 떠올릴 수 있다. 삭제 노드의 부모 노드가 삭제 노드만 자식으로 가지고 있었다면, 부모노드도 리프노드가 되어야한다.(이게 제일 중요하다)즉 둘 사이을 끊어주는 것이 필요하다. 그래서 이 문제에서는 자식에서 부모를 가리키는 배열 + 부모에서 자식을 가리키는 배열 2가지가 필요하다. 1. 부모 자식간 연결 정보를 담는다. 2. 삭제 노드가 루트 노드일 경우, 모두 지워지므로 0을 출력..
Problem Solving/Baekjoon
문제https://www.acmicpc.net/problem/9466 풀이학생들의 선택에 사이클이 되는 경우 팀이 결성되는데, 결성 되지 않은 팀원들을 구하는 문제이다. 이 문제에서는 2가지 체크하는 배열이 필요하다.1. 노드를 방문 체크 배열2. 팀이 꾸려졌는지 체크 배열(팀이 결성된 학생을 세지 않기 위함이다.) 다음 노드가 무조건 1개이므로, dfs를 사용하는 것이 적절하다고 판단했다.dfs를 수행하면서 현재 정점에서 다음 정점에 대한 방문 여부를 생각했을 때현재 정점은 방문되지 않았지만 다음 정점이 방문되었다면 무조건 사이클이 도는 것이라고 할 수 있다. 그러면 팀 결성 여부를 확인하고팀이 결성되지 않았었다면, 사이클이 도는 학생들의 수를 센다. 이 풀이는 팀이 결성되지 않았으면서 + 사이클이 ..
문제https://www.acmicpc.net/problem/9465 풀이2행 n열로 배치된 스티커를 떼서 얻을 수 있는 점수의 최댓값을 구하는 문제이다. 일단 2문제에서 떼고 안떼보고 전체적인 완탐을 수행하면 2^100000이기 때문에 무조건 시간초과가 난다. 그러면 이 문제를 어떻게 해결할 수 있을까? 결국 10만개의 데이터가 있다는 것은 선형적인 시간복잡도를 가지는 것으로 해결해야한다. 다이나믹 프로그래밍을 이용한다.이전 열까지 스티커를 떼고 최댓값을 누적시키면서 갱신해보는 것이다. 만약에 이런 형태가 있다고 하자.(O: 뗀 스티커, X: 떼지 않은 스티커)XXOXXX 그러면 하단의 2가지가 된다. (?는 스티커가 붙여있는지 안붙여있는지 모른다는 의미이다.)?XOOXX ?XOXOX 즉 밑에 있는 ..
문제https://www.acmicpc.net/problem/9252 풀이점화식을 도출하고 구하는 것은 이전 포스팅 글을 살펴보면 된다. [Baekjoon] LCS - Java문제https://www.acmicpc.net/problem/9251 풀이두 문자열이 주어졌을 때, 두 문자열의 공통 부분 수열의 최대 길이를 구하는 문제이다. ACAKCBAK위 두 문자열이 있다고 하자. 그러면 부분 수열은 CAK가 부분gretea5.tistory.com 최장 공통 부분 수열을 구하는 방법 중에 제일 쉬운 방법은 문자열도 함께 저장해서 문자를 붙이는 형태로 구현하는 것이다.근데 메모리 초과가 발생한다. 왜일까?문자를 저장하는데 1byte라고하자.1 * 1000(문자열의 길이) * 1000 * 1000 = 약 1G..
문제https://www.acmicpc.net/problem/9251 풀이두 문자열이 주어졌을 때, 두 문자열의 공통 부분 수열의 최대 길이를 구하는 문제이다. ACAKCBAK위 두 문자열이 있다고 하자. 그러면 부분 수열은 CAK가 부분 수열이 될 것이다. 이 문제를 잘보면,ACAK와 C의 공통 부분 수열의 길이를 구한다.ACAK와 CB의 공통 부분 수열의 길이를 구한다.ACAK와 CBA의 공통 부분 수열의 길이를 구한다.ACAK와 CBAK의 공통 부분 수열의 길이를 구한다.(목표 == 우리가 원하는 것) 문자열을 하나씩 붙이면서 큰 문제 즉, 우리가 원하는 문제를 만들고 있다.작은 문제에서 큰 문제를 구할 때 사용하는 알고리즘은 다이나믹 프로그래밍을 이용하면 된다. 1. 테이블을 정의한다.dp[i][..
문제https://www.acmicpc.net/problem/9019 풀이네자릿수를 저장하는 레지스터에서 D, S, L, R의 네가지 명령어를 수행하는데 주어진 숫자를 만들기 위한 최소한의 명령어를 구하는 문제이다. 이 문제를 명령을 수행해서 갈 수 있는 최소의 거리를 구하면 된다고 생각했고, 최소 거리를 구하면서 명령어도 같이 저장하면 될 것이라고 생각해 bfs를 사용해서 구현하면 된다고 생각했다. 1. 변환 전, 후 숫자를 입력받는다. 2. bfs를 사용해서 D, S, L, R과 같은 명령어를 수행했을 때, 방문 처리가 되지 않았으면 명령어를 같이 저장하면서 bfs를 수행한다. 3. 변환 후 숫자에 도달 했을 경우, 그에 대한 명령어를 출력한다. 소스코드import java.util.*;import ..
문제https://www.acmicpc.net/problem/1039 풀이서로 다른 인덱스 i, j 번째 있는 수들을 k번 교환해서 나오는 최댓값을 구하는 문제이다. 처음에 누구나 백트래킹을 해보고 싶다는 생각이 들 것이다.그런데, 서로 다른 인덱스 2개를 고르는 수의 최댓값은 49이다.그러면 49^10이 되는 것인데, 무조건 시간 초과가 날 것이다. 그러면 문제를 k번 바꿔서 만들 수 있는 수들을 어떻게 만들 수 있을까? 라는 것으로 다르게 생각해보면 된다.= k번째가 되었을 때 최댓값을 갱신을 해주면서, (현재 숫자,바꾼 횟수)를 가진 bfs를 수행해보는 것이다. 그러면 시간복잡도는 10 * 1,000,000 이므로 1000만 연산으로 문제를 해결할 수 있다. 1. n, k를 입력받고 입력받은 수의 ..
연속으로 틀린 문제를 풀다보니 "아 이래서 이런 코드가 나오는구나!!"라는 깨달음이 생겨서 다른 분들에게도 도움되었으면 해서 공유하고 싶었다. 고민?요즘 어떤 기업이든 신입 채용 공고를 보다보면 코딩테스트를 보는 경우가 많다.쉽고 편안한 문제만 풀다보니 실력이 잘 늘지 않는게 느껴져 고민이 많았다. 딱맞게 Youtube 알고리즘에 이 동영상이 떴다. 전략위 동영상에서 틀린문제 푸는 법에 대해 정말 친절하게 알려주신다.필자는 맥북을 사용하는데, 엑셀로 관리하기가 어려워서 노션으로 관리하면서 3일이 지났는지, 7일이 지났는지 체크하고 있다.백준이나 프로그래머스에서 못풀었거나 1번이라도 틀린적이 있는 문제들은 모조리 넣어서 약점을 보완하고 있다.
문제 https://www.acmicpc.net/problem/1038 풀이n번째로 높은 자리에서 낮은 자리로 감소하는 수를 구하는 문제이다. 모든 경우의 수를 따져보면, 총 1023개이다.{0, 1, 2, 3, 4, 5, 6, 7, 8, 9} 집합의 부분집합을 구하면 무조건 감소하는 수를 만들 수 있다.하지만 모두 다 안 고르는 경우공집합 경우가 있으므로, 총 경우의 수는 1023개이다. 1. 10번째 이하일 때는 n을 그대로 출력한다. 2. 0 ~ 9사이에서 1자리로 시작해서 10을 나머지 연산한 값보다 작은 값들을 계속 일의 자리로 붙여 리스트에 담는다.10을 나머지 연산하면 일의 자리가 나오고 그 수보다 작은 값을 붙이면 감소하는 수가 되기 때문이다.9876543210이 최대 자리이기 때문에, 자..
문제https://www.acmicpc.net/problem/30804 풀이탕후루에 꽂는 과일이 있는데 탕후루에 과일이 2개가 되는 종류 중에 가장 긴 길이를 구하는 문제이다. N이 20만이다. 즉 이중 for문을 돌면 시간초과가 난다. 투포인터로 순회하면 O(N)연산으로 수행할 수 있다. 1. 투포인터에서는 left, right 두가지 포인터가 존재하는데, right를 한개씩 이동하면서 종류의 개수를 센다. 2. right로 이동해서 종류가 3개가 넘어버리면 left로 종류가 2개 이하가 될때까지 left를 이동한다. 3. 최대 길이를 갱신한다. 소스코드import java.io.BufferedReader;import java.io.InputStreamReader;import java.io.IOExce..
