본문 바로가기

알고리즘98

백준 g3 11779 최소비용 구하기 2 c++ (다익스트라 경로 복원) https://www.acmicpc.net/problem/11779 11779번: 최소비용 구하기 2 첫째 줄에 도시의 개수 n(1≤n≤1,000)이 주어지고 둘째 줄에는 버스의 개수 m(1≤m≤100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스 www.acmicpc.net 문제 다익스트라인데 경로 복원하기 풀이 pre[노드] 배열을 둬서 경로가 업데이트 될 때마다 이전의 노드가 무엇이었는지 추가하고, 마지막에 pre[end] -> pre[start]로 따라가면 경로가 나온다. 다익스트라는 노드를 하나씩 확정시켜나가면서 확정된 노드의 인접한 노드들을 업데이트하므로, pre[확정된 노드의 인접한 노드] = 확정된 노드로 경로 복원을 할 .. 2024. 4. 21.
백준 g4 1753 최단경로 c++ (다익스트라) https://www.acmicpc.net/problem/1753 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가 www.acmicpc.net 다익스트라 매 단계마다 도달할 수 있는 정점 중에서, 시작점으로부터 거리가 가장 가까운 점을 구해서 그 거리를 확정 짓는 방법이다. 1. 노드 선택(시작점으로부터의 거리가 가장 가까운 노드) 2. 그 노드에서 뻗어나가는 간선들을 베이스로 인접한 노드들을 모두 업데이트 원래 기록된 거리 vs. 1번에서 선택한 노드를 거쳤을 때의 거리 중 더 짧은 것으로 업데이트.. 2024. 4. 21.
백준 g1 23290 마법사 상어와 복제 c++ https://www.acmicpc.net/problem/23290 23290번: 마법사 상어와 복제 첫째 줄에 물고기의 수 M, 상어가 마법을 연습한 횟수 S가 주어진다. 둘째 줄부터 M개의 줄에는 물고기의 정보 fx, fy, d가 주어진다. (fx, fy)는 물고기의 위치를 의미하고, d는 방향을 의미한다. 방향 www.acmicpc.net 문제 설명 4*4 격자에서 상어가 마법을 연습한다. 격자에는 물고기 M마리가 들어있고, 각각은 이동 방향(8개)를 가진다. 상어도 격자 하나에 들어가 있다. 둘 이상의 물고기가 같은 칸에 있을 수 있고, 마법사 상어와 물고기도 같은 칸에 있을 수 있다. 상어가 모든 물고기에게 복제 마법을 시전한다. 복제 마법은 이 시점을 저장했다가 5번에서 이루어진다. 모든 물고.. 2024. 4. 13.
백준 g1 21611 마법사 상어와 블리자드 c++ https://www.acmicpc.net/problem/21611 21611번: 마법사 상어와 블리자드 마법사 상어는 파이어볼, 토네이도, 파이어스톰, 물복사버그, 비바라기 마법을 할 수 있다. 오늘 새로 배운 마법은 블리자드이고, 크기가 N×N인 격자에서 연습하려고 한다. N은 항상 홀수이고, ( www.acmicpc.net 문제 설명 N*N의 보드가 주어지고, 나선형으로 길이 뚫려있다. 마법사 상어는 보드의 정중앙에 위치한다. { (N+1)/2, (N+1)/2 } 각 칸에는 1, 2, 3이 적혀있는 구슬이 하나씩 들어있다. 1) 마법사 상어는 M번 블리자드 마법을 si칸만큼, di 방향으로 쏜다. 블리자드 마법을 맞는 칸의 구슬은 없어진다. 1-1) 구슬이 비어있으면, 그 뒤의 구슬이 나선형 길을 .. 2024. 4. 12.
백준 g2 19238 스타트 택시 c++ https://www.acmicpc.net/problem/19238 19238번: 스타트 택시 첫 줄에 N, M, 그리고 초기 연료의 양이 주어진다. (2 ≤ N ≤ 20, 1 ≤ M ≤ N2, 1 ≤ 초기 연료 ≤ 500,000) 연료는 무한히 많이 담을 수 있기 때문에, 초기 연료의 양을 넘어서 충전될 수도 있다. 다 www.acmicpc.net 문제 설명 N*N 보드에 각각 현재 택시의 위치, M명의 승객들의 출발점과 도착점이 주어진다. 택시는 가장 가까운 손님부터 태우고, 그 손님의 도착점에 내려준다. 그 이후로 다시 가장 가까운 손님부터 태우기를 반복한다. 택시는 1칸 갈 때마다 연료를 소모한다. 승객을 도착점에 내려주면, 택시는 승객을 태우고 소모한 연료의 2배를 다시 획득한다. 택시가 달리다.. 2024. 4. 11.
프로그래머스 Lv.3 대장균들의 자식의 수 구하기 https://school.programmers.co.kr/learn/courses/30/lessons/299305 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr SELECT A.ID, IF(B.PARENT_ID IS NULL, 0, COUNT(A.ID)) AS CHILD_COUNT FROM ECOLI_DATA AS A LEFT JOIN ECOLI_DATA AS B ON A.ID = B.PARENT_ID GROUP BY A.ID ORDER BY A.ID ASC 기억해둘 것 자식이 없는 ID를 0으로 표시하고 싶으면 1. LEFT JOIN으로 일단 A.ID.. 2024. 3. 30.
백준 g4 2580 스도쿠 c++ https://www.acmicpc.net/problem/2580 2580번: 스도쿠 스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루 www.acmicpc.net 풀이는 여기로 https://kyj0032.tistory.com/107 백준 g4 2239 스도쿠 c++ https://www.acmicpc.net/problem/2239 2239번: 스도쿠 스도쿠는 매우 간단한 숫자 퍼즐이다. 9×9 크기의 보드가 있을 때, 각 행과 각 열, 그리고 9개의 3×3 크기의 보드에 1부터 9까지의 숫자가 중복 없이 나타 kyj0032.tistory.com 전체 코드.. 2024. 3. 22.
백준 g4 2239 스도쿠 c++ https://www.acmicpc.net/problem/2239 2239번: 스도쿠 스도쿠는 매우 간단한 숫자 퍼즐이다. 9×9 크기의 보드가 있을 때, 각 행과 각 열, 그리고 9개의 3×3 크기의 보드에 1부터 9까지의 숫자가 중복 없이 나타나도록 보드를 채우면 된다. 예를 들어 다 www.acmicpc.net 문제 9*9의 배열이 주어진다. 0은 빈칸을 의미한다. 이때, 스도쿠를 채울 수 있게 답을 채워 출력한다. 답이 여러 개면, 81자리의 숫자가 제일 작은 것부터 출력한다. 문제는 항상 가능한 경우의 수만 주어진다. 풀이 빈칸이 있으면 1~9부터 넣어보면서 만약 해당 경우의 수가 불가능하면 backtracking으로 되돌리고, 다시 채우고 ... 반복하면 된다. 만약 빈칸이 모두 채워졌다면, .. 2024. 3. 22.
백준 g4 4803 트리 c++ https://www.acmicpc.net/problem/4803 4803번: 트리 입력으로 주어진 그래프에 트리가 없다면 "No trees."를, 한 개라면 "There is one tree."를, T개(T > 1)라면 "A forest of T trees."를 테스트 케이스 번호와 함께 출력한다. www.acmicpc.net 문제 입력으로 주어진 그래프에 트리의 개수대로 No trees. / There is one tree. / A forest of 개수 trees. 를 출력하기 풀이 그래프가 트리가 되려면 모두 연결되어있어야 하고, 사이클이 없어야 한다. 그래프의 시작점에서 연결된 노드를 모두 탐색한다. 이때, 이미 탐색된 노드가 있다면 그것은 사이클이 있다는 뜻이므로 트리가 아니다. 전체 코드 /.. 2024. 3. 21.

티스토리툴바