본문 바로가기

전체 글86

[C++]백준(BOJ) - 30689 미로만들기(다익스트라) 난이도 : 골IV풀이 시간 : 20분알고리즘 유형 : BFS, 다익스트라풀이 방법 : 우선순위를 이용해 범위 기반 탐색(상하좌우)  문제 링크https://www.acmicpc.net/problem/2665  문제 예시n×n 바둑판 모양이고, 일부분은 검은 방이고 나머지는 모두 흰 방이다.검은 방은 들어갈 수 없고, 붙어 있는 두 개의 흰 방 사이에는 문이 있어서 지나다닐 수 있다.검은 방 몇 개를 흰 방으로 바꿀 수 있다.  -> n x n 격자 이며, 검은방은 흰색으로 바꿀 수 있다.(cost 증가)윗줄 맨 왼쪽 방은 시작방으로서 항상 흰 방이고,아랫줄 맨 오른쪽 방은 끝방으로서 역시 흰 방이다. -> 예외처리 할 필요 없음시작방에서 출발 -> 끝방으로 도착하는 것이 목적인데,부득이 검은 방 몇 개를.. 2024. 11. 11.
[C++] 프로그래머스(Lv.3) 미로 탈출 명령어(그리디) 난이도 :  Lv3 (중)알고리즘 유형 : 그리디, 휴리스틱풀이 방법 : 거리 기반으로 사전순으로 탐색  문제 링크https://school.programmers.co.kr/learn/courses/30/lessons/150365 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr  문제 설명n x m 격자 내에서 시작 위치 (x, y)에서 목표 위치 (r, c)로 이동해야 합니다.총 k번 이동해야 하며, 이동할 때 격자 바깥으로 나갈 수 없습니다.아래, 왼쪽, 오른쪽, 위쪽(d, l, r, u)으로 움직일 수 있고,목표 지점까지 정확히 k번의 이동으로 도달해야 합니다.이 문제에서 k번의 이동으로 목표 지점.. 2024. 11. 10.
[C++]백준(BOJ) - 30689 미로보수(그래프 탐색) 난이도 : 골III알고리즘 유형 : DFS, BFS풀이 방법 : 사이클 계산을 위한 DFS  문제 링크https://www.acmicpc.net/problem/30689 문제 예시각 칸에 '상', '하', '좌', '우' 중 하나가 표시되어 있고 세로로 N칸, 가로로 M칸인 N×M 크기의 미로가 있다.해당 칸으로 도착한 모든 사람은 미로에 표시된 방향으로 한 칸 이동한다.이를 반복해 미로 밖으로 벗어나면 미로에서 탈출할 수 있다.형진이는 미로에 원하는 만큼 점프대를 설치할 수 있다.점프대를 설치하면 해당 위치에 도착한 사람들은 점프를 통해 바로 미로 밖으로 빠져나올 수 있다.점프대를 설치하기 위해서는 해당 칸의 지리적 조건 등을 고려해야 하므로,어느 칸에 설치하냐에 따라 점프대의 비용이 달라진다.정확하게.. 2024. 11. 9.
[C++] 프로그래머스(Lv.2) 도넛과 막대 그래프 난이도 :  Lv2 (상)알고리즘 유형 : BFS, DFS풀이 방법 : BFS를 이용한 사이클 계산  문제 링크https://school.programmers.co.kr/learn/courses/30/lessons/258711 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 문제 예시  크기가 n인 도넛 모양 그래프는 n개의 정점과 n개의 간선이 있습니다. 도넛 모양 그래프의 아무 한 정점에서 출발해 이용한 적 없는 간선을 계속 따라가면 나머지 n-1개의 정점들을 한 번씩 방문한 뒤 원래 출발했던 정점으로 돌아오게 됩니다. 도넛 모양 그래프의 형태는 다음과 같습니다.  크기가 n인 막대 모양 그래프는 n.. 2024. 11. 8.
[C++]백준(BOJ) - 1461 도서관(그리디) 난이도 : 골IV알고리즘 유형 : 그리디, 정렬풀이 방법 : 투 포인터 문제 링크https://www.acmicpc.net/problem/1461 문제 예시이 문제는 세준이가 도서관에서 책을 원래 위치로 다시 가져다 놓는 최소 걸음 수를 구하는 문제입니다.주어진 조건을 바탕으로 어떻게 풀어야 할지 단계별로 풀어나가겠습니다.코드 로직 설명입력과 정렬:책의 위치를 입력받아 양수와 음수 좌표로 나눕니다. 음수는 양수로 변환하여 모두 양수로 처리합니다. 이는 코드 작성과 정렬에서 일관성을 유지해 줍니다.positive와 negative 배열은 멀리 있는 책부터 처리하기 위해 내림차순으로 정렬합니다.이동 거리 계산:한 번에 최대 M권의 책을 들 수 있으므로, 각 배열에서 M권씩 묶어 가장 멀리 떨어진 책의 위치로.. 2024. 11. 7.
[C++]백준(BOJ) - 1253 좋다(투 포인터) 난이도 : 골IV알고리즘 유형 : 투 포인터, 이분 탐색풀이 방법 : 투 포인터 문제 링크https://www.acmicpc.net/problem/1253 문제 예시N개의 수 중에서 어떤 수가 다른 수 두 개의 합으로 나타낼 수 있다면 그 수를 “좋다(GOOD)”고 한다.N개의 수가 주어지면 그 중에서 좋은 수의 개수는 몇 개인지 출력하라.수의 위치가 다르면 값이 같아도 다른 수이다.N(1 ≤ N ≤ 2,000), 수열 |Ai| ≤ 1,000,000,000, Ai는 정수 예시는 간단합니다.다른 수 두 개의 합(a[i]+ a[j]) == 어떤 수(K) && N -> O(n^2)이 가능하며, O(n^2) 로 풀어야함. 이분 탐색을 이용해 O(n^2logn) 풀이를 떠올려서 풀었지만 예외처리할 것이 많아 틀.. 2024. 11. 6.

티스토리툴바