이것도 알아야 하네?

> 문제 https://www.acmicpc.net/problem/11996 11996번: Circular Barn (Silver) Being a fan of contemporary architecture, Farmer John has built a new barn in the shape of a perfect circle. Inside, the barn consists of a ring of \(n\) rooms, numbered clockwise from \(1 \ldots n\) around the perimeter of the barn (\(3 \leq n \leq 1000\) www.acmicpc.net 간단하게, n 개의 공간과 n 마리의 소가 있을 때 각 방에 1마리의 소를 넣는 문제이다. ..

> 문제 https://www.acmicpc.net/problem/11967 11967번: 불켜기 (1, 1)방에 있는 스위치로 (1, 2)방과 (1, 3)방의 불을 켤 수 있다. 그리고 (1, 3)으로 걸어가서 (2, 1)방의 불을 켤 수 있다. (2, 1)방에서는 다시 (2, 2)방의 불을 켤 수 있다. (2, 3)방은 어두워서 갈 수 없으 www.acmicpc.net 농부 존은 최근에 N × N개의 방이 있는 거대한 헛간을 새로 지었다. 각 방은 (1, 1)부터 (N,N)까지 번호가 매겨져있다(2 ≤ N ≤ 100). 어둠을 무서워하는 암소 베시는 최대한 많은 방에 불을 밝히고 싶어한다. 베시는 유일하게 불이 켜져있는 방인 (1, 1)방에서 출발한다. 어떤 방에는 다른 방의 불을 끄고 켤 수 있는 ..

https://programmers.co.kr/learn/courses/30/lessons/92343 코딩테스트 연습 - 양과 늑대 [0,0,1,1,1,0,1,0,1,0,1,1] [[0,1],[1,2],[1,4],[0,8],[8,7],[9,10],[9,11],[4,3],[6,5],[4,6],[8,9]] 5 [0,1,0,1,1,0,1,0,0,1,0] [[0,1],[0,2],[1,3],[1,4],[2,5],[2,6],[3,7],[4,8],[6,9],[9,10]] 5 programmers.co.kr 신박하게 풀 여러가지 방법을 떠올려봤지만, 모두 완전탐색 방식보다 코드가 지저분해지길래 포기했다. #include #include #include #include using namespace std; vector ..

https://programmers.co.kr/learn/courses/30/lessons/17685 코딩테스트 연습 - [3차] 자동완성 자동완성 포털 다음에서 검색어 자동완성 기능을 넣고 싶은 라이언은 한 번 입력된 문자열을 학습해서 다음 입력 때 활용하고 싶어 졌다. 예를 들어, go 가 한 번 입력되었다면, 다음 사용자는 g programmers.co.kr 해당 문제는 문제 자체가 어려웠다기 보다는 c++에서의 String처리가 낯설었다. String은 C언어로 보면 literal이기 때문에 변경이 불가능한 문자열이다. char[] 처럼 포인트 접근을 하기 위해서는 형변환이 필요했고, 이 때 형변환은 단순히 char가 아니라 변경이 불가능한 const char로 변경해야한다. #include #i..

https://programmers.co.kr/learn/courses/30/lessons/64062 코딩테스트 연습 - 징검다리 건너기 [2, 4, 5, 3, 2, 1, 4, 2, 5, 1] 3 3 programmers.co.kr 징검다리는 숫자가 적혀있는 디딤돌로 구성되어있고, 사람이 디딤돌을 지나가면 적힌 숫자가 줄어든다고 할 때 징검다리를 건널 수 있는 최대 인원을 구하는 문제이다. 사람이 건널 때 징검다리에 있는 디딤돌을 딛고 건너야하되, 숫자가 0이 된 디딤돌이 있으면 점프를 해서 가야한다. 점프로 넘을 수 있는 디딤돌 개수 또한 주어진다. 풀이 (시도 1) 효율성을 보는 문제라서 안될 것은 알았지만 누구나 생각할 수 있는 naive한 접근 방식을 도전해보았다. 징검다리 길이 x 징검다리에 있..

풀이 이번 문제에서 고려했어야했던 포인트는 두 가지로, 첫 번째는 후보 조합을 구하는 것과 두 번째는 조합 중 중복을 제외해야하는 것이다. 이렇게 복잡하게 풀 문제는 아니었는데, 깔끔한 알고리즘을 떠오르지 않았다. 후보 조합을 찾는 것은 2 step으로 구성되어있다. '*'로 치환되어있는 banned_id 들이 될 수 있는 후보를 먼저 dict형식으로 찾아놓은 후, DFS를 통해서 생성할 수 있는 모든 조합을 찾는다. 첫 번째 step에서 중요한 점은 banned_id의 후보를 dict 형식으로 저장할 때 id를 저장하는 것이 아닌 user_id의 위치를 저장한다. 이는 이후 중복체크할 때 사용된다. 조합을 찾을 때는 이미 선택한 id는 중복되서 들어갈 수 없으니 이미 앞에서 다를 banned_id로 선..