Coding Test (42) 썸네일형 리스트형 [백준] 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. 핵심 문제 풀이 도출(문제 의도 파악)해당 문제는 인접행렬에서 조건에 맞는 경로를 모두 탐색하는.. [Programmers] 43163번 - 단어 변환 1. 문제 파악문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/43163문제 정의: 주어진 시작지점부터 문자를 하나만 변경해서 단어 집합의 단어가 되는 최단 경로를 구해라.문제의 제약 파악 (입력값 크기, 상수 조건)3 2. 문제 풀이1. 핵심 문제 풀이 도출(문제 의도 파악): 어떻게 하면 시간 복잡도 내로 줄일수 있을까?일단, 이문제는 탐색해서 최단 경로를 구하는 문제이다.무가중치 그래프이므로 원하는 답이 나왔을때 깊이를 반환하면 되므로 BFS를 사용하는 것이 적합하다고 생각했다.시작점인 begin부터 주어진 words에서 target을 찾을때까지 탐색하면된다. BFS 탐색시 현재 높이를 탐색을 마치면 카운팅을 하고 답을 찾으면 높이.. [Programmers] 43165번 - 타켓 넘버 1. 문제 파악문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/43165문제 정의: 주어진 숫자의 +/- 수의 합으로 타켓 넘버를 만족하는 경우의 수를 구해라.문제의 제약 파악 (입력값 크기, 상수 조건)주어지는 숫자의 개수는 2개 이상 20개 이하입니다.각 숫자는 1 이상 50 이하인 자연수입니다.2. 문제 풀이1. 브루트 포스와 입력 크기에 따른 시간 복잡도 계산완전 탐색시 경우의 수는 2^(주어진 숫자의 개수)이다. 따라서 numbers.length = 20이므로 최대 2^20 = 1024^2 ≃ (10^3)^2 = 10^6 각 수는 +/-로 분기해서 그래보면 다음과 같다. 이는 그래프의 한 형태의 이진 트리로 표현할수있다. 깊이^.. 이전 1 2 3 4 ··· 6 다음