주뇽's 저장소

웅덩이가 있는 길을 피해, 마을에서 학교까지 갈 수 있는 모든 다른 길을 찾는 문제를 해결해 보자. 이 글에서는 마을에서 학교까지 도달할 수 있는 가능한 경로의 개수를 구하는 방법과 함께, 동적 프로그래밍(DP)을 활용한 경로 추적 알고리즘을 단계별로 설명한다.문제점: 웅덩이가 있는 경우 갈 수 있는 길이 제한된다 😓마을에서 출발하여 학교까지 가려면 특정한 경로를 따라야 하며, 이 경로에 웅덩이가 있으면 그곳을 지날 수 없다. 따라서 웅덩이를 피해 가능한 모든 경로의 개수를 구해야 한다. 단순히 오른쪽이나 아래쪽으로만 이동할 수 있는 경우, 웅덩이를 피하면서 학교까지 도달하는 모든 가능한 경로를 찾으려면 어떻게 해야 할까?해결책: 동적 프로그래밍을 사용한 경로 계산 🛠️지도 그리기 먼저, 마을에서 학..

네트워크 알고리즘 설명문제 설명주어진 컴퓨터 네트워크 정보로 연결된 네트워크의 수를 찾는 문제다. 각 컴퓨터가 네트워크 상에서 연결된 경우 하나의 네트워크로 간주한다. 이를 통해 네트워크의 개수를 계산한다.해결 방법기본 설정:visit 배열을 통해 각 노드의 방문 여부를 추적한다.모든 노드를 초기화하여 방문하지 않은 상태로 설정한다.static boolean[] visit;public int solution(int n, int[][] computers) { int answer = 0; visit = new boolean[n]; for(int i = 0; i 그래프 순회:각 노드를 순회하며 방문되지 않은 노드를 찾는다.방문되지 않은 노드가 발견되면 DFS를 수행하여 해당 노드와 연결된 모든..

https://school.programmers.co.kr/learn/courses/30/lessons/17680?language=java 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr[1차] 캐시 알고리즘 설명 문제 설명캐시 메모리에서의 작업 처리 시간 최적화를 위해, Least Recently Used (LRU) 알고리즘을 사용하여 캐시 히트와 캐시 미스를 관리하는 문제다. 캐시 크기와 도시 이름 배열이 주어졌을 때, 각 도시 이름이 주어질 때마다 캐시 히트인지 미스인지 판단하고 총 실행 시간을 계산한다. 해결 방법기본 설정:cacheSize가 0이면 모..

https://www.acmicpc.net/problem/11725 11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net 시간 제한메모리 제한제출정답맞힌 사람정답 비율 1 초 256 MB 82478 36840 25903 42.457% 문제 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 노드의 개수 N (2 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N-1개의 줄에 트리 상에서 연결된 두 정점이 주어진다. 출력 첫째 줄부터 N-1개의 줄에 각 노드의 부모 노드 번호를 2번 노드부터 순..

https://www.acmicpc.net/problem/9465 9465번: 스티커 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의 www.acmicpc.net 1 초 256 MB 73396 34595 24514 46.854% 문제 상근이의 여동생 상냥이는 문방구에서 스티커 2n개를 구매했다. 스티커는 그림 (a)와 같이 2행 n열로 배치되어 있다. 상냥이는 스티커를 이용해 책상을 꾸미려고 한다. 상냥이가 구매한 스티커의 품질은 매우 좋지 않다. 스티커 한 장을 떼면, 그 스티커와 변을 공유하는 스티커는 모두 찢어져서 사용할 수 없게 된다. 즉..

https://www.acmicpc.net/problem/15686 1 초 512 MB 88214 43370 26195 46.048% 문제 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸, 왼쪽에서부터 c번째 칸을 의미한다. r과 c는 1부터 시작한다. 이 도시에 사는 사람들은 치킨을 매우 좋아한다. 따라서, 사람들은 "치킨 거리"라는 말을 주로 사용한다. 치킨 거리는 집과 가장 가까운 치킨집 사이의 거리이다. 즉, 치킨 거리는 집을 기준으로 정해지며, 각각의 집은 치킨 거리를 가지고 있다. 도시의 치킨 거리는 모든 집의 치킨 거리의 합이다...

https://www.acmicpc.net/problem/2630 2630번: 색종이 만들기 첫째 줄에는 전체 종이의 한 변의 길이 N이 주어져 있다. N은 2, 4, 8, 16, 32, 64, 128 중 하나이다. 색종이의 각 가로줄의 정사각형칸들의 색이 윗줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진다. www.acmicpc.net 1 초 128 MB 46060 32135 24770 69.706% 문제 아래 과 같이 여러개의 정사각형칸들로 이루어진 정사각형 모양의 종이가 주어져 있고, 각 정사각형들은 하얀색으로 칠해져 있거나 파란색으로 칠해져 있다. 주어진 종이를 일정한 규칙에 따라 잘라서 다양한 크기를 가진 정사각형 모양의 하얀색 또는 파란색 색종이를 만들려고 한다. 전체 종이의 크기가 N×N(N..

https://www.codetree.ai/training-field/frequent-problems/problems/codetree-mon-bread/description?page=1&pageSize=20 코드트리 | 코딩테스트 준비를 위한 알고리즘 정석 국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요. www.codetree.ai 코드트리에서 제공해주는 삼성 2022 하반기 오후 1번 문제이다. 삼성의 전형적인 그래프탐색을 이용한 시물레이션 문제이다. 일단 문제를 대략적으로 설명하자면 인기있는 빵을 구하기 위해 자신이 목표로 하는 편의점을 최단거리로 돌아다니는 문제이다. 문제만 들으면 뭐 그냥 BFS돌리면 되겠네 싶지만 그렇게..