Programmers(Algorithm) (19) 썸네일형 리스트형 코딩테스트 고득점 Kit(동적계획법)_등굣길_Level3 https://school.programmers.co.kr/learn/courses/30/lessons/42898 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 명확한 dp의 개념을 알지 못하여 처음에는 dp + bfs로 풀었다가 시간초과가 나왔다. 단순 dp로 풀면 간단하게 풀 수 있었다. 이동 조건은 오른쪽과 아래쪽만 움직일 수 있다. 따라서 dp의 점화식은 dp[i][j] = dp[i-1][j] (이전의 위쪽 값) + dp[i][j-1] (이전의 왼쪽값)이며 물 웅덩이가 있는 부분은 제외해야한다. 소스코드 #include #include usi.. 코딩테스트 고득점 Kit깊이/너비 우선 탐색(DFS/BFS)_여행경로_Level3 https://school.programmers.co.kr/learn/courses/30/lessons/43164 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 DFS 1. 제한 사항 ("만일 가능한 경로가 2개 이상일 경우 알파벳 순서가 앞서는 경로를 return 합니다.")로 인해 출발 공항이 겹치게 되는 경우 항공권의 최우선 선택 순위는 알파벳이 빠른 항공권이다. => 해당 이유로 인해 dfs를 하기 이전에 알파벳 순서로 tickets를 정렬한다. (* 2차원 배열을 sort 함수를 사용해 정렬한다면 1차로는 행 기준으로, 2차로는 열 기준으로.. 코딩테스트 고득점 Kit깊이/너비 우선 탐색(DFS/BFS)_단어 변환_Level3 https://school.programmers.co.kr/learn/courses/30/lessons/43163 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr [문제 풀이] 변환이 가능한 단어는 하나의 알파벳을 제외하고 나머지 알파벳이 동일해야 한다. 다시말해, begin과 words 배열안에 문자열을 비교하여 단계별 변환을 거쳐 최종적으로 target 문자열이 나올 수 있는지 확인하는 문제이다. 해당 문제는 BFS로 접근하면 쉽게 풀 수 있는 문제이다. 1. 큐에는 begin 문자열과 비교하여 words 배열 내의 변환이 가능한 문자열의 인덱스와 변환.. 코딩테스트 고득점 Kit깊이/너비 우선 탐색(DFS/BFS)_게임 맵 최단거리_Level2 https://school.programmers.co.kr/learn/courses/30/lessons/1844 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr [문제 풀이] 전형적인 최단 거리 문제로 BFS로 풀 수 있다. 1. 새로운 이차원 배열을 하나를 선언(A)해주고 해당 배열에는 이동해온 누적 값을 저장해준다. 2. 게임맵 배열의 (0 , 0) 위치에서 시작하여 (n-1,m-1)까지 이동 가능한 좌표값을 방문해주며 A 배열에 이동 가능한 좌표 위치에는 이전 좌표에 저장된 A값에 1을 더해준다. 3. 상대팀 진영에 도착이 가능한 경우 A배열의 (n-.. 코딩테스트 고득점 Kit깊이/너비 우선 탐색(DFS/BFS)_네트워크_Level3 https://school.programmers.co.kr/learn/courses/30/lessons/43162 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr [문제 풀이] DFS로 자주 등장하는 전형적인 문제이다. 연결된 노드를 확인하고 분할된 그래프가 몇개인지를 확인하면 되는 문제이다. 1. 연결 그래프를 생성하여 0번째 컴퓨터부터 연결된 노드를 차례로 방문한다. 2. 0번째 컴퓨터와 연결된 모든 컴퓨터를 확인하고 나면 연결된 모든 컴퓨터 방문 배열은 true로 초기화 될 것이다. 3. 이후의 컴퓨터를 차례로 확인하여 방문한 적 없는 컴퓨터인 경우 .. 코딩테스트 고득점 Kit깊이/너비 우선 탐색(DFS/BFS)_타겟 넘버_Level2 https://school.programmers.co.kr/learn/courses/30/lessons/43165 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr [문제 풀이] 최근에 있던 코테 두 번째 문제와 거의 유사한 문제이다. 미리 풀어봤더라면 쉽게 풀었을텐데.... 기본적으로 재귀를 사용하여 문제를 풀 수 있습니다. 0번째 인덱스 원소 값 부터 마지막 인덱스 원소 값까지 +,- 를 해주면서 마지막 인덱스의 원소 값의 합이 target과 같다면 answer를 증가 아니면 종료를 해주어 모든 경우의 수를 확인하면 된다. [소스 코드] #include .. 코딩테스트 고득점 Kit(동적계획법)_정수 삼각형_Level3 https://school.programmers.co.kr/learn/courses/30/lessons/43105 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr [문제 풀이] 행을 하나씩 이동 시키면서 이전 행에서 이동할 수 있는 값 중 큰 값을 더해주는 방식으로 triangle 배열을 채워준다. 단, 0번째 인덱스의 위치 값과 마지막 인덱스의 위치 값은 이전 행의 동일한 값만을 받아올 수 있음에 유의해준다. 최종적으로 마지막 행의 값들이 꼭대기에서 바닥까지 이어지는 경로 중 가장 큰 값들의 집합으로 해당 행에서 가장 큰 값이 답이 된다. [소스 코드] .. 코딩테스트 고득점 Kit(동적계획법)_N으로 표현_Level3 https://school.programmers.co.kr/learn/courses/30/lessons/42895 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr [문제 풀이] https://velog.io/@euneun/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-N%EC%9C%BC%EB%A1%9C-%ED%91%9C%ED%98%84-DP-%EB%8F%99%EC%A0%81%EA%B3%84%ED%9A%8D%EB%B2%95-C [프로그래머스] N으로 표현 (DP, 동적계획법) / C++ ✅ 프로그래머스 N으.. 이전 1 2 3 다음