전체 글 (129) 썸네일형 리스트형 [백준] 16928 - 뱀과 사디리 게임 1. 문제 파악문제 링크: https://www.acmicpc.net/problem/16928문제 정의: 주사위를 던져서 나온 눈만큼 이동하거나, 사다리를 만나면 올라가거나, 뱀을 만나면 내려가는 모든 탐색 경로에서 최단거리를 구해라.문제의 제약 파악 (입력값 크기, 상수 조건)N(1 ≤ N ≤ 15)과 뱀의 수 M(1 ≤ M ≤ 15)2. 문제 풀이1. 핵심 문제 풀이 도출(문제 의도 파악): 어떻게 하면 시간 복잡도 내로 줄일수 있을까?주사위를 던져서 나온 눈만큼 이동하거나, 사다리를 만나면 올라가거나, 뱀을 만나면 내려간다. 1번재 칸부터 시작해서 이동한 지점이 100번 칸이 될때까지 이동한 경로중 최단거리를 찾는 것이다. 이 문제는 2차원 좌표로도 표현할수있지만, 100만큼 이동하면되므로 좌표를 .. [백준] 2206번 - 벽 부수고 이동하기 1. 문제 파악문제 링크: https://www.acmicpc.net/problem/2206문제 정의: N×M의 행렬에서 0 값만 이동가능하고 1값은 딱 한번만 이동이 가능하다. (1, 1)에서 (N, M)의 위치까지 걸리는 최단거리를 구해라.문제의 제약 파악 (입력값 크기, 상수 조건)점 N(0 ≤ N ≤ 1000), K(0 ≤ K ≤ 1000)2. 문제 풀이1. 핵심 문제 풀이 도출(문제 의도 파악): 어떻게 하면 시간 복잡도 내로 줄일수 있을까?일반적인 문제풀이와 같이 벽을 안부수을때의 최단거리는 12이다.0 1 1 0 0 00 1 0 0 1 00 0 0 0 1 0 다만, 하나의 벽을 부수는 경로는 4가지이다.벽 좌표 (1, 1): 최단거리 10벽 좌표 (0, 2): 최단거리 12벽 좌표 (2, .. [백준] 7576번 - 토마토 1. 문제 파악문제 링크: https://www.acmicpc.net/problem/7576문제 정의: 2차원 배열에서 모든 지점으로 부터 모든 토마토가 익는 최단 일수를 구해라.문제의 제약 파악 (입력값 크기, 상수 조건)2 ≤ M,N ≤ 1,000: 최대 각 요소를 한번씩만 탐색할 정도의 입력크기가 주어짐2. 문제 풀이1. 핵심 문제 풀이 도출(문제 의도 파악)일반적인 문제는 탐색 시작점이 1개인 경우가 많았다. 하지만 이 문제는 시작 지점이 여러개인 상태에서 동시에 최단 경로탐색을 수행해야한다. 그러나 사실 탐색을 시작할 지점을 모두 지정하고 방문한 지점의 중복 탐색만 피하면된다. 이 문제는 가중치가 모두 동일한 1이므로 BFS 최단거리 탐색이 적합하다. 즉, 탐색 시작전에 배열 요소를 조회하면서 .. [백준] 1697번 - 숨바꼭질 1. 문제 파악문제 링크: https://www.acmicpc.net/problem/1697문제 정의: 시작 점 N에서 현재 위치 - 1, 현재 위치 + 1, 현재 위치 x 2 이동에 따라 도착 점 K까지 걸리는 최단 시간을 구해라.문제의 제약 파악 (입력값 크기, 상수 조건)점 N(0 ≤ N ≤ 100,000), K(0 ≤ K ≤ 100,000): 총 정점의 개수인 10^5 개 내로 중복없이 탐색을 마치면된다.2. 문제 풀이1. 핵심 문제 풀이 도출(문제 의도 파악): 어떻게 하면 시간 복잡도 내로 줄일수 있을까?]현재 위치를 X번 정점으로 두면, 시작 정점부터 각 세방향 (X - 1, X + 1, X x 2)으로 인접 정점이 확장된 그래프를 형상화 시킬수있다. 그려면 시작 정점 N부터 현재 위치 -.. [Programmers] 49191번 - 순위 1. 문제 파악문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/49191문제 정의: 방향이 있는 주어진 배열 값으로 순위를 매길수 있는 정점의 개수를 구해라.문제의 제약 파악 (입력값 크기, 상수 조건)선수의 수는 1명 이상 100명 이하입니다.경기 결과는 1개 이상 4,500개 이하입니다.results 배열 각 행 [A, B]는 A 선수가 B 선수를 이겼다는 의미입니다.모든 경기 결과에는 모순이 없습니다.2. 문제 풀이1. 입출력 케이스 도출 및 문제 풀이 도출 확인정점인 선수의 수가 100명이고 간선의 개수인 경기 결과는 4500개 이하이므로, 인접리스트(V + E)로 구현한 그래프를 DFS 탐색시에 시간복잡도 제한은 없다. 2. 핵.. [Programmers] 49189번 - 가장 먼 노드 1. 문제 파악문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/49189문제 정의: 주어진 간선 정보로 최단경로로 이동했을때 가장 간선의 개수가 많은 노드의 개수를 반환해라.문제의 제약 파악 (입력값 크기, 상수 조건): 인접 행렬은 O(V^2) = 20000 x 20000이므로 10^8을 초과해서 시간 내에 풀지 못한다. 그래서 인접 리스트O(V+E) = 20000 + 50000으로 풀수있다.노드의 개수 n은 2 이상 20,000 이하간선은 양방향이며 총 1개 이상 50,000개 이하의 간선2. 문제 풀이1. 핵심 문제 풀이 도출(문제 의도 파악): 어떻게 하면 시간 복잡도 내로 줄일수 있을까?최단 경로로 탐색했을때 간선의 개수가 가장.. [Programmers] 87694번 - 아이템 줍기 1. 문제 파악문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/87694문제 정의: 겹치지 않는 직사각형 테두리 좌표애서 시작점부터 도착지점까지 최단거리 탐색을 해서 측정해라.문제의 제약 파악 (입력값 크기, 상수 조건)rectangle의 세로(행) 길이는 1 이상 4 이하: 하나의 직사각형은 존재rectangle의 원소는 각 직사각형의 [좌측 하단 x, 좌측 하단 y, 우측 상단 x, 우측 상단 y] 좌표 형태직사각형을 나타내는 모든 좌표값은 1 이상 50 이하인 자연수: 인접행렬에 좌표를 저장하므로 가로 세로 크기를 51이어야함서로 다른 두 직사각형의 x 축 좌표, 혹은 y축 좌표가 같은 경우는 없음1 캐릭터와 아이템의 처음 위치가 .. [Programmers] 43162번 - 네트워크 1. 문제 파악문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/43162문제 정의: 주어진 인접 행렬에서 경로(네트워크)의 개수를 구해라.문제의 제약 파악 (입력값 크기, 상수 조건)컴퓨터의 개수 n은 1 이상 200 이하각 컴퓨터는 0부터 n-1인 정수로 표현i번 컴퓨터와 j번 컴퓨터가 연결되어 있으면 computers[i][j]를 1로 표현computer[i][i]는 항상 1입니다.2. 문제 풀이1. 입출력 케이스 도출 및 문제 풀이 도출 확인정점인 컴퓨터의 개수가 200개 이하이므로 주어진 인접행렬로 그래프 탐색을 하여도 40000 2. 핵심 문제 풀이 도출(문제 의도 파악)해당 문제는 인접행렬에서 조건에 맞는 경로를 모두 탐색하는.. 이전 1 2 3 4 ··· 17 다음