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의 경우 탐색된..

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/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 /* 왼쪽 아래점에 있고, 집은 오른쪽 위 한..

https://school.programmers.co.kr/learn/courses/30/lessons/155652 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 새로운 Lv1 문제가 나왔다. 이런 건 다 풀어줘야지~~ 문자열 유형이었는데, 알파벳을 배열(alph)에 넣고 진행해 줬다. 문자열 배열 s를 순회하면서 시작위치를 idx에 넣어줬는데 여기서 UnicodeScalar를 사용해서 "a"를 기준으로 상대적인 위치값을 구했다. 그리고 문제를 잘 읽어보면 skip에 포함된 알파벳을 무시하고 넘어가야 되기 때문에 if 조건문을 달아줬다. skip에 포함되..

https://www.acmicpc.net/problem/11052 11052번: 카드 구매하기 첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000) www.acmicpc.net 일반적인 dp 유형 문제인 것 같은데 굉장히 헷갈렸다. 이렇게 구상했다. 가장 헷갈렸던 것이 바로 dp의 정의였다. 여기서 dp는 i장 카드를 살 때의 최대 비용을 저장하는 배열로 사용한다. dp가 그렇듯 앞에 작은 문제들의 답으로 큰 문제의 답을 해결할 수 있도록 해야 하는데, 여기서는 카드 N장을 구매할 때의 최대 비용을 구해야 하므로, 1장~N-1장을 구매했을 때의 최대 비용부터 차례대로 구하면서 ..

https://www.acmicpc.net/problem/16928 16928번: 뱀과 사다리 게임 첫째 줄에 게임판에 있는 사다리의 수 N(1 ≤ N ≤ 15)과 뱀의 수 M(1 ≤ M ≤ 15)이 주어진다. 둘째 줄부터 N개의 줄에는 사다리의 정보를 의미하는 x, y (x < y)가 주어진다. x번 칸에 도착하면, y번 칸으 www.acmicpc.net 보드판은 함정. 좌표를 사용할 일이 없다. 어떤 칸 i에서 이동할 수 있는 곳 → i+1, i+2, i+3, i+4, i+5, i+6, 뱀, 사다리로 이동 사다리와 뱀의 반대로 이동은 불가 100번 칸에 도착하기 위해 굴려야 할 주사위의 최소 횟수 구하기 BFS, 좌표칸을 vertex로. ✅ 사다리나 뱀의 시작점을 만나면 무조건 타고 이동해야 됨. ✅..

https://www.acmicpc.net/problem/18429 18429번: 근손실 웨이트 트레이닝을 좋아하는 어떤 대학원생은, 현재 3대 운동 중량 500의 괴력을 소유하고 있다. 다만, 하루가 지날 때마다 중량이 K만큼 감소한다. 예를 들어 K=4일 때, 3일이 지나면 중량이 488로 www.acmicpc.net 백트래킹은 DFS와 달리 불필요한 탐색은 하지 않는다. 그래서 앞의 키트에서 중량 500을 넘기지 못하면 뒷부분 키트도 사용해보지 않고 패스하도록 했다. (cnt == n 조건까지 들어가지 않고 패스하기) 500을 넘는 애들만 재귀호출 진행. import Foundation //input let nk = readLine()!.split(separator: " ").map{ Int(Str..

https://www.acmicpc.net/problem/16922 16922번: 로마 숫자 만들기 2, 6, 10, 11, 15, 20, 51, 55, 60, 100을 만들 수 있다. www.acmicpc.net 이 문제에서 주의할 점은 IX와 XI는 같은 수라는 것이다. 이 부분을 체크하지 않아서 시간초과가 발생했다...ㅠ 이를 피하기 위해 start라는 매개변수를 추가해서 뒤에서 앞 원소를 선택하는 경우를 없앴다. 사실 처음 문제를 풀 땐, set으로 중복되는 수는 제외해 주도록 했었다. 해보니까 시간 차이는 딱히 없는 것 같다. [Set] import Foundation let n = Int(readLine()!)! let num = [1, 5, 10, 50] var set = Set() func..