기록하는 습관 "기습"

백트래킹이란?백트래킹은 해를 찾는 과정에서 여러 가능성을 탐색하다가, 특정 경로가 잘못되었음을 알게 되면 되돌아가서 다른 경로를 시도하는 문제 해결 기법이다. 모든 가능한 경우의 수를 탐색하지만, 가지치기(pruning)를 통해 비효율적인 경로를 배제하여 효율성을 높인다. 다시 말해, 완전 탐색(브루트 포스)의 개선된 형태라 할 수 있다. 단순히 요약하자면, 백트래킹은 "이 길이 아닌 것 같을 때 원래 왔던 길로 되돌아가서 다른 길을 가보는 것"이다. 이는 특성으로 알 수 있듯이 대부분 DFS로 구현할 수 있다.  백트래킹의 예시이번 예시는 9663번 N-Queen 문제를 기준으로 하겠다. 먼저 구현 문제를 보자.  문제 자체는 백트래킹을 잘 활용해야 풀 수 있다. 나는 문제를 다 읽고 2차원 배열로 풀..

개요코테 준비를 시작했는데 너무 부족함을 느끼고 있다. 나오는 문제는 막힘없이 풀 수 있는 정도가 되고 싶다. 왜 이렇게 해야 하는가에 대한 이유는 다음 글을 읽어보길 바란다. 도움이 되는 내용도 많다! https://yozm.wishket.com/magazine/detail/2755/ 개발자를 위한 실전 ‘코딩테스트’ 준비 팁 | 요즘IT개발자라면 누구나 ‘코딩테스트’를 준비해 본 경험이 있을 겁니다. 코딩테스트는 여러분의 두뇌가 얼마나 비상한지, 복잡하게 꼬인 문제를 얼마나 천재적인 발상으로 해결할 수 있는지 시험yozm.wishket.com 그래서 나는 이전에 강의로 배웠던 내용을 다시 공부하거나 부족한 부분을 채우려고 한다. 처음은 DFS와 BFS로 스타트를 끊고자 한다. 설명은 백준의 1260번..

탐색 인공지능 시스템이 문제해결을 위해서 흔히 사용하는 기법이다. 만약 문재해결을 위해서 취해야 할 행동들이 무엇인지 알고 있지만 어떤 순서로 행동을 취해야 문제가 해결되는지 알지 못하면 가능한 모든 순서 조합을 다 시도해 보아야 한다. 탐색 탐색 방법에는 두 종류가 있다. 무 정보 탐색 : 모든 길(조합)을 다 찾아보는 방법 휴리스틱 탐색 : 가능성이 높은 곳만을 선별하여 찾아보는 방법 무 정보 탐색 무 정보 탐색 기법은 탐색공간(어떤 문제 공간에서 만들어질 수 있는 모든 상태들의 집합)에 대한 아무런 정보 없이 순서만 정해놓고 탐색을 수행한다. 무 정보 탐색에서 다시 2종류로 나뉘는데 깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS)이다. 깊이우선탐색 depth first search 하나의 트리 ..

그래프 Graph는 사물이나 현상을 정점 vertex이나 간선 edge으로 표현한 것이다. 정점은 대상, 간선은 대상 간의 관계를 나타낸다. 선형 자료구조나 트리 구조로는 표현할 수 없는 다 대 다 관계를 표현할 수 있다. 그래프의 종류 무방향 그래프 undirected graph 간선에 방향이 없는 그래프다. 정점 a와 정점 b를 동일하게 가르킨다. 즉, (a,b), (b,a)이다. 방향 그래프 directed graph digraph라고도 한다. 간선에 방향이 있는 그래프다. 무방향 그래프와 다르게 한쪽 방향만 가르킨다. 완전 그래프 complete graph 각 정점에서 다른 모든 정점으로 가는 간선이 존재하는 그래프를 뜻한다. 즉, 주어진 정점 수에 대해 간선수가 최대이다. 정점이 n개인 완전 그..