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..

https://www.acmicpc.net/problem/2961 2961번: 도영이가 만든 맛있는 음식 첫째 줄에 재료의 개수 N(1 ≤ N ≤ 10)이 주어진다. 다음 N개 줄에는 그 재료의 신맛과 쓴맛이 공백으로 구분되어 주어진다. 모든 재료를 사용해서 요리를 만들었을 때, 그 요리의 신맛과 쓴맛은 www.acmicpc.net 백트래킹 문제가 계속 헷갈려서 이 유형 위주로 문제를 풀어보고 있다. N개의 재료 중 1~N개를 선택하는 것인데, 이 부분은 백트래킹을 사용하면 된다. 여기서 쓴맛인 S와 신맛인 B의 값만 제대로 넣어준다면 쉽게 해결할 수 있다. import Foundation /* 재료 N개 각 재료의 신맛S 쓴맛B 여러 재료를 이용해서 요리할 때, 음식의 신맛은 사용한 재료의 신맛의 곱,..

https://www.acmicpc.net/problem/16472 16472번: 고냥이 고양이는 너무 귀엽다. 사람들은 고양이를 너무 귀여워했고, 결국 고양이와 더욱 가까워지고 싶어 고양이와의 소통을 위한 고양이 말 번역기를 발명하기로 했다. 이 번역기는 사람의 언어를 고 www.acmicpc.net 알파벳 종류 최대 N개인 연속된 문자열을 선택하고 가장 긴 문자열의 길이를 구하는 문제로, 두 포인터를 사용하면 된다. sort: 지금까지의 알파벳 종류 count: 알파벳 카운팅 배열 (인덱스 => 알파벳 순서대로) 왼쪽 포인터 L을 고정하고, R을 뒤로 이동시킨다. 1. R을 뒤로 이동시키면서 해당 위치의 알파벳을 추가한다.(add(x:) 메서드) -> 이때 문자열을 따로 두지 않고 count 배열에 ..

https://www.acmicpc.net/problem/17142 17142번: 연구소 3 인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 바이러스는 활성 상태와 비활성 상태가 있다. 가장 처음에 모든 바이러스는 비활성 상태이고 www.acmicpc.net 구현 흐름 1. 바이러스 중 M개 활성화 → 조합 경우 구하기(중복 없이) → 바이러스 정보를 viruses 배열에 넣고 (튜플 형태) M개 고르기 (choice 배열에 따로 넣어줌) 2. 바이러스 퍼트리기 → BFS 탐색 후, max 값 구하기 코드 설명 1. 전처리 viruses 배열에 바이러스 정보(x, y) 넣기 벽은 “-”로 바꾸기 2. 모든 조합의 경우의 수마다 BFS 탐색 바이러스 중 M개 선..

https://www.acmicpc.net/problem/20058 20058번: 마법사 상어와 파이어스톰 마법사 상어는 파이어볼과 토네이도를 조합해 파이어스톰을 시전할 수 있다. 오늘은 파이어스톰을 크기가 2N × 2N인 격자로 나누어진 얼음판에서 연습하려고 한다. 위치 (r, c)는 격자의 r행 c www.acmicpc.net 정리 파이어스톰 시전 (Q회) 2^L X 2^L 크기의 부분 격자로 나누기 모든 부분 격자를 시계방향으로 90도 회전 인접한(상하좌우) 칸 중 얼음 있는 칸이 3개 미만인 칸은 얼음양 - 1 모두 끝난 후 남은 얼음의 합 출력 (완전탐색) 남은 얼음 중 가장 큰 덩어리의 얼음 칸 개수 출력 (BFS) 구현 하기 1. 파이어스톰 → 배열 회전. 회전할 부분 배열 구하기 for i..