본문 바로가기

Algorithm/알고리즘 문제

 (12)
백준 11729번 : 하노이 탑 이동 순서 with 재귀함수 잘 설계하는 법 재귀함수 잘 설계하는 법 1. 마인드 세팅 : 함수의 흐름을 생각하지 말고, 큰 그림에 집중하기 재귀 함수를 잘 설계하기 위한 제 1 원칙은 '재귀적으로 생각하지 말기'이다. ❗함수의 실행 흐름과 콜스택을 그대로 따라가려하지 말자.❗ => 특히 내가 많이 하는 실수 특정 단계에서 이전 단계와 조합되어 어떻게 작동하는지에만 집중하자. 함수를 호출할 때마다 베이스 조건에 가까워져야 한다. 그 전 단계에서 무조건 정답이 리턴되었다고 믿자. 그리고 그 이상은 생각하지 말자. 이걸 '재귀적 믿음의 점프'라고도 부른다. (이런 용어가 있을 정도로 하나의 단계에 대해서만 생각하고, 이전 단계는 이미 정답이라 믿는 것이 재귀함수를 풀이하는 일반적인 방법임) 위의 마인트를 탑재했다면, 아래 방법으로 재귀함수를 만들어주면..
백준 17609번 : 회문 문제 17609번: 회문 (acmicpc.net) 17609번: 회문 각 문자열이 회문인지, 유사 회문인지, 둘 모두 해당되지 않는지를 판단하여 회문이면 0, 유사 회문이면 1, 둘 모두 아니면 2를 순서대로 한 줄에 하나씩 출력한다. www.acmicpc.net 아이디어 우선 가장 간단한 아이디어는 StringBuilder의 reverse와 equals만을 이용하는 풀이이다. 1. reverse한게 원본과 같으면 0 출력 2. for문을 돌면서 하나씩 삭제한 다음, reverse한게 원본과 같으면 1 출력 3. for문을 다 돌 때까지 원본과 같지 않으면 2 출력 하지만, 이렇게 하면 reverse / delete / insert 와 같은 함수를 문자열의 길이만큼 반복해줘야 하므로 시간초과가 발생한다...
백준 2567번 : 색종이-2 문제 2567번: 색종이 - 2 (acmicpc.net) 2567번: 색종이 - 2 첫째 줄에 색종이의 수가 주어진다. 이어 둘째 줄부터 한 줄에 하나씩 색종이를 붙인 위치가 주어진다. 색종이를 붙인 위치는 두 개의 자연수로 주어지는데 첫 번째 자연수는 색종이의 왼쪽 변 www.acmicpc.net 색종이를 겹쳐서 붙였을 때, 전체 색종이의 둘레를 구하는 문제 아이디어 두가지 방법으로 풀이할 수 있는데 두 방법 모두 '우선 색종이를 붙인 다음' 시작한다. 색종이를 붙이는 방법은 이중 for 문 돌면서 0을 1로 바꿔주면 된다. 방법 1. 이중 for문으로 풀이 흰 도화지 전체를 돌면서 진행 색종이 부분(= 값이 1인)을 만나면, 4개의 방향에 있는 값을 조사 4변을 조사하는 방법은 {{0, 1}, {0,..
백준 10434번 : 행복한 소수 문제 10434번: 행복한 소수 (acmicpc.net) 10434번: 행복한 소수 각 테스트 케이스마다, 테스트 케이스의 번호, 입력받은 수, 만일 M이 행복한 소수라면 YES 아니라면 NO를 공백으로 각각 구분하여 출력한다. www.acmicpc.net 정수가 입력될 때 그 정수가 행복한 소수인지를 출력하는 문제. 행복한 소수란, 각 자리의 제곱의 합을 구하는 것을 반복했을 때 1이 나오는 소수 아이디어 ❗어떤 소수가 행복한 소수가 아닌 경우, 각 자리 제곱의 합은 어떤 패턴을 띄게 되어있다. 행복한 소수는 우선 소수여야 한다. -> 1과 소수가 아닌 수는 바로 NO 출력 입력된 수가 소수이면, 제곱의 합을 구한 다음 이미 나온 수인지를 반복문 안에서 확인한다. 이미 나온 수인지 확인하는 방법 : 합..
백준 2992번 : 크면서 작은 수 문제 2992번: 크면서 작은 수 (acmicpc.net) 2992번: 크면서 작은 수 정수 X가 주어졌을 때, X와 구성이 같으면서 X보다 큰 수 중 가장 작은 수를 출력한다. 수의 구성이 같다는 말은, 수를 이루고 있는 각 자리수가 같다는 뜻이다. 예를 들어, 123과 321은 수의 구성이 www.acmicpc.net 아이디어 1. case를 분류해서 조건식으로만 푸는 방법 각 자리수를 index 취급 숫자가 모두 내림차순으로 정렬되어있으면, 더 커질 수 없으므로 0출력 숫자 중에 오름차순으로 정렬된게 있는지 확인, 이는 숫자의 순서를 바꿈으로써 커질 수 있는 위치를 뜻함 오름차순이 발견된 idx 중에서 가장 뒤에 있는 idx를 찾기 = point로 저장 point 뒤에 있는 수 중에서 point 해..
백준 2304번 : 창고 다각형 문제 2304번: 창고 다각형 (acmicpc.net) 2304번: 창고 다각형 첫 줄에는 기둥의 개수를 나타내는 정수 N이 주어진다. N은 1 이상 1,000 이하이다. 그 다음 N 개의 줄에는 각 줄에 각 기둥의 왼쪽 면의 위치를 나타내는 정수 L과 높이를 나타내는 정수 H가 한 개의 www.acmicpc.net 아이디어 첫번째 trial : 극댓값을 기준으로 설계 (엄청 공들여서 설계했는데, 틀렸었음 ㅠ) 기둥들을 배열로 보면, 위 그림은 {4,0,6,3,0,0,10,0,0,4,0,6,0,8}이라 생각할 수 있다. 이때 기준이 되는 기둥들의 특징은 '기울기가 바뀌는 부분(=극댓값)'이라 생각함 따라서 극댓값에 해당하는 배열로 표시하고, 그 배열을 돌면서 너비를 구함 틀린 이유 : 극댓값으로 접근을 ..
백준 5397번 : 키로거 문제 5397번: 키로거 (acmicpc.net) 5397번: 키로거 첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스는 한줄로 이루어져 있고, 강산이가 입력한 순서대로 길이가 L인 문자열이 주어진다. (1 ≤ L ≤ 1,000,000) 강산이가 백스페이스를 입 www.acmicpc.net 아이디어 1406번과 동일한 로직으로 풀이했다. 1406번은 텍스트와 명령어가 따로 주어졌다면, 5397번은 인라인으로 주어졌다는 차이점 정도! 심지어 StringBuilder로 delete, insert하다가 시간 초과 떠서 데크 2개로 해결한 것조차 동일.. 커서가 나오는 문제는 커서 왼쪽 데크, 오른쪽 데크를 만들어서 풀어야 하나보다! 알게된 것 백준 문제는 무조건 시간 복잡도가 낮은 것으로 풀이해야..
백준 1406번 : 에디터 문제 1406번: 에디터 (acmicpc.net) 1406번: 에디터 첫째 줄에는 초기에 편집기에 입력되어 있는 문자열이 주어진다. 이 문자열은 길이가 N이고, 영어 소문자로만 이루어져 있으며, 길이는 100,000을 넘지 않는다. 둘째 줄에는 입력할 명령어의 개수 www.acmicpc.net 커서를 이용해서 문자열을 편집하는 문제 아이디어 🔸 첫번째 시도 : 커서와 문자열을 분리해서 해결. 문자열 편집에는 char[ ]을 이용. 결과 : 시간 초과 1. 하나의 명령어가 주어질 때 '커서를 계산하는 함수'와 '문자열을 계산하는 함수'를 호출하므로 함수 호출이 빈번 2. char 배열을 이용했으므로 문자열을 편집할 때마다 새로운 길이의 배열을 만들고, → 매번 공간 복잡도 O(n) 이전 배열을 복사하기 위..

티스토리툴바