문제 링크 https://programmers.co.kr/learn/courses/30/lessons/43238 코딩테스트 연습 - 입국심사 n명이 입국심사를 위해 줄을 서서 기다리고 있습니다. 각 입국심사대에 있는 심사관마다 심사하는데 걸리는 시간은 다릅니다. 처음에 모든 심사대는 비어있습니다. 한 심사대에서는 동시에 한 programmers.co.kr 문제의 제한사항을 보면 1,000,000,000이라는 택도없이 큰 숫자가 등장한다. 보통 제한사항의 숫자가 큰 경우에는 완전탐색등의 방법을 쓰면 경우의 수가 어마무시하게 커지게 될 것이다. 이런 경우에는 효율적인 알고리즘을 채택해야 하는데, 필자는 이 문제에서 '이분 탐색'을 선택했다. 이분 탐색 이분 탐색은 일련의 데이터들 중에서 하나의 값을 찾을 때..

문제 링크 https://programmers.co.kr/learn/courses/30/lessons/42897 코딩테스트 연습 - 도둑질 도둑이 어느 마을을 털 계획을 하고 있습니다. 이 마을의 모든 집들은 아래 그림과 같이 동그랗게 배치되어 있습니다. 각 집들은 서로 인접한 집들과 방범장치가 연결되어 있기 때문에 인접한 programmers.co.kr 이 문제는 동적계획법으로 풀이하였다. 풀이 방법 이 문제의 분기점은 처음 도둑질을 할 때, 첫 번째 집을 고르냐, 두 번째 집을 고르냐에 따라 크게 두가지로 나뉜다. 인접한 집은 털 수 없다는 제한으로 두 경우로 나뉘어 집을 터는 루트가 정해지기 때문이다. 필자의 풀이 방법을 그림을 통해 자세히 보도록 하자. 왼쪽에 보이는대로, 처음 세 개의 집은 터는..

문제 링크 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..