본문 바로가기

분류 전체보기142

A* 알고리즘 A* 알고리즘은 컴퓨터 게임뿐만 아니라 자동차 네비게이션 자연어 파싱 등에도 사용된다. A*알고리즘의 수식은 다음과 같다. f (n) = g(n) + h(n) 최종값 = 경로값 + 휴리스틱 예측값 휴리스틱 예측값 - 현위치에서 목적지까지의 최단 거리로 설정 - 상황에 따라 다른 함수로 만들어서 사용해도 무관하다. -> 다양한 상황에서 사용 가능. 최단 경로를 나타내는 다익스트라 알고리즘의 식은 다음과 같다. f(n) = g(n) 즉 A*는 다익스트라 알고리즘에서 h(n) (휴리스틱 예측값)이라는 값을 더해서 사용하는 것이다. 그래프 예시입니다. A* 알고리즘 순서를 나타내보겠습니다. A부터 B까지 A*값 = 5.5 , C까지 A*값 = 6.5 -> B가 더 작으므로 B에서 진행 B와 이어져있는 D까지 A.. 2024. 3. 10.
백준 3197 C++ https://www.acmicpc.net/problem/3197 3197번: 백조의 호수입력의 첫째 줄에는 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1500. 다음 R개의 줄에는 각각 길이 C의 문자열이 하나씩 주어진다. '.'은 물 공간, 'X'는 빙판 공간, 'L'은 백조가 있는 공간으로 나타낸다.www.acmicpc.net 처음으로 플레를 혼자서 풀어서 성공했다. 처음에 그냥 일반적으로 빙판이 녹는걸 생각해서 시간초과가 나타났다.치즈와 같은 문제에서는 이렇게하면 풀렸기 때문이다.#include #include using namespace std;const int MAX = 1500;bool meet = false;int r, c;int dy[] = { -1, 0, 1, 0 };int dx[].. 2024. 3. 6.
백준 2529 C++ https://www.acmicpc.net/status?user_id=jjune0461&problem_id=2529&from_mine=1 채점 현황 www.acmicpc.net solved.ac 기준으로 실버인데 틀려서 자존심 상해서 다신 안틀리기 위해 복습... 일단 여기서 틀린 이유 to_string()의 존재를 생각 못함. char끼리 비교하면 되는데 char를 int로 바꿔서 하려다가 방법이 생각이 안나서 복잡하게 만듦. 제일 어이없는 건데 계속 다시 풀다가 전역변수와 main 함수 안에 변수를 동일한 걸 써서 찾지 못해 시간을 오래 잡아먹음. 일단 로직에 대해서 방문한건 방문처리하고 check함수는 잘 만들었다. 그저 비교하는 방식을 너무 꼬아서 생각해서 이렇게 실패했다. #include #in.. 2024. 3. 6.
백준 4179 C++ https://www.acmicpc.net/problem/4179 4179번: 불! 입력의 첫째 줄에는 공백으로 구분된 두 정수 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1000 이다. R은 미로 행의 개수, C는 열의 개수이다. 다음 입력으로 R줄동안 각각의 미로 행이 주어진다. 각각의 문자 www.acmicpc.net 이거 생각보다 어려웠습니다... 처음에 조금이라도 메모리를 절약해보겠다고 visited를 사용하지 않고 if문을 엄청 꼬아서 하니까 어디서 반례가 나타나는지 모르겠어서 그냥 visited를 만들어서 했습니다. 최단 거리니까 BFS를 사용했고 다양한 반례에 대해서는 한번 직접 생각하시면서 해보시는게 나을거 같습니다. #include #include using namespace std.. 2024. 2. 20.

티스토리툴바