문제 링크 https://programmers.co.kr/learn/courses/30/lessons/42895 코딩테스트 연습 - N으로 표현 programmers.co.kr Dynamic Programming(동적 계획법)을 이용하여 풀었다. 풀이 방식 개인적으로 로직을 짜기 제일 까다로웠던 문제중 하나였던 것 같다. 필자는 이 문제를 'N을 사용한 횟수'를 기준으로 나눠 풀이하였다. 즉 N이 5라면, 5를 1번, 2번, 3번...8번(문제 조건에 8보다 크면 -1리턴이기 떄문)사용해서 만들 수 있는 숫자들의 경우로 나눈 것이다. 박스가 8개 있다고 해보자. 1번 박스에는 N을 1번 사용해서 만들 수 있는 숫자들이 담겨있다. N = 5라고 한다면 1번 박스에는 5만 담겨있을 것이다. 2번 박스에서는 ..

문제 링크 https://programmers.co.kr/learn/courses/30/lessons/43164 코딩테스트 연습 - 여행경로 [["ICN", "SFO"], ["ICN", "ATL"], ["SFO", "ATL"], ["ATL", "ICN"], ["ATL","SFO"]] ["ICN", "ATL", "ICN", "SFO", "ATL", "SFO"] programmers.co.kr DFS(깊이 우선 탐색)방식에 착안하여 풀이하였다. 풀이 방식 1. boolean 배열을 선언하여 한번 산 티켓은 표시할 수 있도록 설정한다. 2. route 문자열을 선언하여 지나가는 공항 이름을 하나씩 붙여 경로를 설정할 수 있도록 한다. 3. ArrayList 리스트를 선언하여 모든 공항을 들르는 루트를 다 저장..

문제 링크 https://programmers.co.kr/learn/courses/30/lessons/43162 코딩테스트 연습 - 네트워크 네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 A와 컴퓨터 B가 직접적으로 연결되어있고, 컴퓨터 B와 컴퓨터 C가 직접적으로 연결되어 있 programmers.co.kr BFS(너비우선탐색) 방식으로 풀이하였다. 풀이 방식 1. ArrayList에 컴퓨터 0~N까지 모두 넣는다. 2. 반복문을 돌리며 ArrayList에 첫번째 원소를 꺼낸다. (0번 컴퓨터) 0 번째 컴퓨터부터 자신과 연결되어 있는 컴퓨터들을 queue에 넣는다. (ex. computers[0][1] == 1 이면, 0번째와 1번째 컴퓨터가 연결..

문제 링크 https://programmers.co.kr/learn/courses/30/lessons/43165 코딩테스트 연습 - 타겟 넘버 n개의 음이 아닌 정수들이 있습니다. 이 정수들을 순서를 바꾸지 않고 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 programmers.co.kr 흔한 dfs문제이다. 재귀를 사용하여 numbers의 숫자를 더하거나 빼는 모든 경우의 수를 다 거쳐본다. 마지막 numbers 원소까지 연산이 끝났을 때, 총 연산값이 target과 일치하면 answer + 1 class Solution { int answer = 0; public void dfs(int[] num, int t..

문제 링크 https://programmers.co.kr/learn/courses/30/lessons/42898 코딩테스트 연습 - 등굣길 계속되는 폭우로 일부 지역이 물에 잠겼습니다. 물에 잠기지 않은 지역을 통해 학교를 가려고 합니다. 집에서 학교까지 가는 길은 m x n 크기의 격자모양으로 나타낼 수 있습니다. 아래 그림은 m = programmers.co.kr 흡사 어렸을 적 수학 올림피아드(?)에서 볼 수 있을 법한 느낌의 문제다. (뭔가 낯이 익다..) 이 문제 역시 다이나믹 프로그래밍을 이용하여 쉽게 풀 수 있다. 문제의 제한사항처럼 움직일 수 있는 방향은 '오른쪽'과 '아래' 뿐이다. 따라서 해당 방향만 고려해서 풀이하면 된다. 그림과 함께 로직을 살펴보자. 풀이 방법 (0, 1)을 기준으..

문제 링크 https://programmers.co.kr/learn/courses/30/lessons/43105 코딩테스트 연습 - 정수 삼각형 [[7], [3, 8], [8, 1, 0], [2, 7, 4, 4], [4, 5, 2, 6, 5]] 30 programmers.co.kr 이 문제의 경우 효율성 검사가 들어가있다. 그 의미는 무엇이냐? 완전탐색이나 다중 for문과 같은 방식은 out이라는 뜻! 필자의 경우 다이나믹 프로그래밍(Dynamic Programming) 기법을 사용하였다. 다이나믹 프로그래밍이란? 다이나믹 프로그래밍이란 복잡한 문제를 간단한 여러개의 문제로 나눠 푸는 것을 의미한다. 한마디로 하나의 큰 문제를 여러개의 작은 단위로 쪼갠다는 뜻이다. 분할 정복 알고리즘(Divide and..