https://www.acmicpc.net/problem/11057 11057번: 오르막 수 오르막 수는 수의 자리가 오름차순을 이루는 수를 말한다. 이때, 인접한 수가 같아도 오름차순으로 친다. 예를 들어, 2234와 3678, 11119는 오르막 수이지만, 2232, 3676, 91111은 오르막 수가 아니다. 수 www.acmicpc.net 길이가 N인 오르막수의 개수를 구하는 문제 -> 길이가 1~N인 오르막수의 개수를 모두 구해보자. 표를 만들어서 해보면 큼큼 굉장히 지저분하지만, 딱 알 수 있다. dp의 행 i는 1~N까지의 길이, 열은 j로 끝나는 수를 말한다. 즉, dp[i][j]는 i길이의 오르막 수 중에서 j로 끝나는 수의 개수 여기서 관건은 사실 i, j를 선언하는 것이다. j를 개념..

https://www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net DP는 그 안에서도 굉장히 많은 유형이 있다고 생각한다. 이 문제는 DP 기본 문제 중 하나라고 생각하는데, 조건이 추가된 것도 그렇고, 작은 문제에서 큰 문제로 가는 방식도 그렇고. 정말.. 어렵다~ DP 우선 문제를 정리해 보자면, N번째 계단에 최댓값으로 올라가야 한다. 이동 방법은 1) 1칸 이동 2) 2칸 이동 중요한 게 바로 조건! 연속 3칸을 밟으면 안 된다. DP는 N보다 작은 애들의 결과로 N..

https://www.acmicpc.net/problem/15686 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net 백트래킹 문제인데, 실수가 잦아서 헤맸다. 격자가 나오길래 처음엔 BFS인가 했지만 다 읽어보니 격자는 뭐 사용도 안 한다. 치킨집(chickens)과 집(houses) 배열에 각각 좌표를 넣고 (tuple) chickens의 조합을 구하면 된다. 여기서 실수한 게 바로, 순열을 구했다는 것..!! 시간초과 발생... [1,2,4] = [2,4,1] = [4,1,2] = ....

https://www.acmicpc.net/problem/2636 2636번: 치즈 아래 과 같이 정사각형 칸들로 이루어진 사각형 모양의 판이 있고, 그 위에 얇은 치즈(회색으로 표시된 부분)가 놓여 있다. 판의 가장자리(에서 네모 칸에 X친 부분)에는 치즈가 놓 www.acmicpc.net 나름 쉽고 간단한 BFS 문제 헷갈렸던 부분은 치즈 칸 개수 카운팅 → 처음엔 1을 모두 세야 하는 줄 알았는데, 결국 모두 녹기 전에 치즈는 선분으로만 이루어지기 때문에 겉만 카운팅 해도 된다! WoW import Foundation /* 회색 == 치즈. 가장자리에는 치즈가 없고, 치즈에는 하나 이상의 구멍있을 수 있다 치즈를 공기 중에 놓으면 녹게 되는데 공기와 접촉된 칸은 한 시간이 지나면 녹아 없어짐. 치즈..

https://www.acmicpc.net/problem/2992 2992번: 크면서 작은 수 정수 X가 주어졌을 때, X와 구성이 같으면서 X보다 큰 수 중 가장 작은 수를 출력한다. 수의 구성이 같다는 말은, 수를 이루고 있는 각 자리수가 같다는 뜻이다. 예를 들어, 123과 321은 수의 구성이 www.acmicpc.net x를 구성하는 수로 모든 경우의 수를 진행하면 된다. 경우의 수 중에서 x보다 큰 수 중 가장 작은 수를 찾아야 하므로, answer에 값을 경신하면서 진행 x보다 작은 수는 패스하는 부분을 추가 하지 않았는데, 이 부분을 추가하면 시간이 더 줄어들 것이다. 예를 들어 321라는 수에서 1xx, 2xx는 이미 x보다 크지 않기 때문에 깊게 들어가면 안 된다. 516의 경우 탐색된..

AutoLayout을 통해 상대적인 값을 설정함으로써 다양한 디바이스의 해상도에 동일한 화면을 표현할 수 있다. 최고의 도구! 최고의 선배! 호우우우 🎉 AutoLayout을 구성하는 여러 기본 요소가 있는데, 그중에서도 constraints에 대해 알아보자. Index Constraint Add New Contraints Add New Alignment Constraints Mutilplier Priority Content Hugging Priority Content Compression Resistance Priority Constraints Priority Margin Constraint Add New Constraints 오브젝트의 Width, Height 설정 절대값 해당 오브젝트와 다른 오브젝..

https://www.acmicpc.net/problem/12101 12101번: 1, 2, 3 더하기 2 n을 1, 2, 3의 합으로 나타내는 방법 중에서 사전 순으로 k번째에 오는 것을 출력한다. k번째 오는 식이 없는 경우에는 -1을 출력한다. www.acmicpc.net 전형적인 백트래킹 문제. 최대한 모든 경우의 수를 보지 않게 하기 위해서 조건들을 넣어줬다. n을 만들 수 있는 k번째에 오는 경우의 수를 찾아야 하기 때문에 n을 만들 수 있는지 체크 k번째에 오는 경우의 수인지 체크 flag의 역할은 k번째 값이 없을 경우 -1을 출력하기 위함 && 경우의 수 줄이기 k번째 경우의 수를 출력한 뒤로는 다음 경우의 수에서 더 깊게 들어갈 필요가 없음 → if문으로 return 해버려서 깊게 들어..

https://www.acmicpc.net/problem/2529 2529번: 부등호 여러분은 제시된 부등호 관계를 만족하는 k+1 자리의 최대, 최소 정수를 첫째 줄과 둘째 줄에 각각 출력해야 한다. 단 아래 예(1)과 같이 첫 자리가 0인 경우도 정수에 포함되어야 한다. 모든 입력 www.acmicpc.net 처음에 틀렸던 이유(시간초과)는, 모든 경우의 수를 탐색했기 때문(DFS) 그러나, 모든 경우의 수를 볼 필요가 없다! 조건에 맞지 않는 애는 가지치기 (BackTracking) 이 문제에서는 주어진 부등호에 맞게 숫자를 나열해야 하기 때문에 주어진 부등호를 사이에 넣었을 경우 해당 숫자들이 맞지 않다면 이제 그 경우는 바로 끝이다. 끝까지 갈 필요가 없다! 그러므로, 우선 BT의 종료 조건을 ..

https://www.acmicpc.net/problem/1189 1189번: 컴백홈 첫 줄에 정수 R(1 ≤ R ≤ 5), C(1 ≤ C ≤ 5), K(1 ≤ K ≤ R×C)가 공백으로 구분되어 주어진다. 두 번째부터 R+1번째 줄까지는 R×C 맵의 정보를 나타내는 '.'과 'T'로 구성된 길이가 C인 문자열이 주어진다 www.acmicpc.net 생각한 구현 방법 집으로 갈 수 있는 방법은 BFS가 아니라 DFS 깊이 우선 탐색으로 진행해야 한다. 깊게 들어가니까 그런데, 여기서 중복도 없고 거리가 k개 이어야 하므로 BT로 거를 애들은 걸러줘야 한다. 1트 실패(80%) → 시작점의 visited 체크 안 해줌 → 성공! import Foundation /* 왼쪽 아래점에 있고, 집은 오른쪽 위 한..