N-Queen 문제를 해결하는 아주 효율적인 풀이이다 #include #define MAX 15 using namespace std; int col[MAX]; int N, total = 0; bool check(int level) // level을 받는 이유: 매번 0~N까지 다 검사할 수도 있지만, 어차피 현재까지 채워진 부분만 검사하면 되므로 level까지만 검사한다. { for (int i = 0; i i이기 때문) return..
주의할 점: 경로 생성이 불가능할 떄 -1을 반환하게 만드는 과정(solve() 함수)이 생각보다 까다롭다. dist와 cost를 혼동하지 말자 - dist는 start에서 해당 노드까지의 거리로, 시작지점이 변하면 변하는 값이고, cost는 어떤 두 노드 사이의 거리로 프로그램 실행부터 종료까지 변하지 않는다. #include #include #include using namespace std; const int INF = 987654321; struct compNode { bool operator() (pair a, pair b) { return a.second > b.second; } }; int N, E; int n1, n2; // 지나야 하는 두 노드 int result = INF; vector..
BFS를 사용하되, 매 루프마다 한 칸씩 이동하는 대신, 갈 수 있는 만큼 최대한 한 방향으로 이동한다. 또 visited 칸을 저장하는 대신, 한 번 지나간 칸에 대해 해당 칸으로 가기 까지 필요한 거울의 갯수(count)를 기록한다. 즉 count != 0 이라면 한 번 이상 방문한 칸인 셈이다. BFS를 사용하기 때문에, 어느 칸에 처음 방문했을때 그 칸까지 가는 최단거리(여기서는 최소한으로 사용되는 거울 갯수)를 바로 알 수 있으며, 이러한 성질을 활용해 거울의 갯수를 축적시켜 최종적으로 목적지에 도달할때까지 길을 찾는 방식이다. (굉장히 다양한 풀이가 존재하지만 이 풀이가 가장 깔끔하고 직관적인 풀이법이라고 생각한다.) #include #include using namespace std; cha..
문제에서 찾아내기 어려운 부분들: 1. 매일매일 마다 백조를 시작지점부터 BFS를 돌려 길을 찾는 것은 낭비이다. 백조가 충돌한 얼음은 다음 날 녹는다. 때문에 이를 기록해두었다가 다음날 시작지점으로 사용하면 된다. 2. 얼음을 녹일 때는 "얼음을 기준으로 주변을 살피기" 가 아니라 "물을 기준으로 주변을 살피기"가 훨씬 효율적이다. 어차피 물과 닿아있어야 녹기 때문이다. 때문에 얼음의 위치를 기록하기보다는 물의 위치를 기록하는 편이 더 좋다. 참고: 인풋을 텍스트 형태로 받기 때문에 2d 그리드를 제작할 때 2d 벡터 대신 벡터 내에 string객체를 저장하는 방식을 사용한다. #include #include #include #include #include using namespace std; int ..
백준 12865 #include #include using namespace std; int arr[101][100001] = { 0 }; int weights[101]; int values[101]; int main() { int n, k; cin >> n >> k; for (int i = 1; i > weights[i] >> values[i]; // 맨 윗줄은 0으로 채워두고 시작. } for (int i = 1; i = weights[i]) { arr[i][j] = values[i] + arr[i - 1][j - weights..
문제1 문자열이 주어질 때, 해당 문자열 내에서 같은 문자가 두 번 연속해서 반복될 경우 이를 제거하고 남은 문자열을 반환하시오. 이 때 pop하는 것으로 인해 또다른 Adjacent Duplicates가 생겨났다면 그 문자들도 pop해서 반환하시오. ex. abbaca aaca ca 문제2 *문제2는 문제1의 상위호환이다 문자열이 주어지고, 자연수 k가 주어질 때, 문자열에서 k번 연달아 겹치는 문자들을 pop하고 남은 문자열을 반환하시오. 이 때 pop하는 것으로 인해 또다른 Adjacent Duplicates가 생겨났다면 그 문자들도 pop해서 반환하시오. ex. k = 3일때 abbbaacda가 주어졌다면 abbbaacda aaacda cda 풀이 문제1, 2 모두 stack 하나만을 사용해서 풀..
문제 닫힌 괄호와 열린 괄호, 그리고 알파벳들이 나열되어있는 문자열이 주어졌을 때, 괄호가 반드시 열리고 닫히도록 문자열을 수정하시오. ex. "({a)(b})" -> "(a)(b)" ")))(((" -> "" "h(e(l)l)o)" -> "h(e(l)l)o" 풀이 Stack을 이용한다. "h(e(l)l)o)(()" -> "h(e(l)l)o()" 의 경우 ( 와 같은 열린 괄호: stack에 추가 )와 같은 닫힌 괄호: stack에서 pop 위 예시의 경우 h(e(l)l)까지 진행했을때 "(" "( (" "(" " " 의 순서를 거치며 스택에서 정상적으로 아이템이 추가되고 pop됨. 하지만 그다음 o)에서 스택에서 pop을 할 수 가 없는데, 이럴 경우 문자열에서 해당 괄호 h(e(l)l)o)(() 를 ..
본 게시글에서는 이 문제에 대한 두 가지 접근을 다룹니다. 첫 번째 접근은 제가 생각해낸 방식이고, 두 번째 접근은 풀이에서 제시된 방식입니다. 문제 문자열을 같은 알파벳이 겹치지 않도록 재배열하시오. ex) aabbcc -> abcabc / acbcba 등... 만약 주어진 조건을 만족하도록 재배열할 수 없다면 empty string을 반환하시오. 내가 생각해낸 방식 1. 두 포인터 변수 ptr1과 ptr2를 정의한다. 각 포인터를 문자열의 0번, 1번 인덱스를 가리키는 상태로 초기화한다. (포인터 변수 대신 인덱스의 값을 저장하는 int형 변수도 가능하다) 2. A. ptr1과 ptr2가 가리키는 알파벳의 종류가 같다면 ptr2가 가리키는 알파벳을 문자열의 가장 뒤로 보내고 ptr2를 ptr1이 가리..
