BangBang's Devlogs

https://programmers.co.kr/learn/courses/30/lessons/42897 코딩테스트 연습 - 도둑질 도둑이 어느 마을을 털 계획을 하고 있습니다. 이 마을의 모든 집들은 아래 그림과 같이 동그랗게 배치되어 있습니다. 각 집들은 서로 인접한 집들과 방범장치가 연결되어 있기 때문에 인접한 �� programmers.co.kr [LEVEL 4] 처음에 문제를 이해할 때, 인접한 집이 아니면 된다는 생각에 홀수 또는 짝수 인덱스로 되어있는 집끼리 money 값을 더해서 구했었으나 반례를 찾아냄 money = {1, 1, 1, 8, 1, 1, 7, 1, 1} 이런 경우 두 칸이 띄어져있더라도 8,7을 훔치는게 더 나음으로.. 해결 방안 1. 처음 집을 훔치고 마지막 집을 안 훔칠때와 ..

https://programmers.co.kr/learn/courses/30/lessons/43163# 코딩테스트 연습 - 단어 변환 두 개의 단어 begin, target과 단어의 집합 words가 있습니다. 아래와 같은 규칙을 이용하여 begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾으려고 합니다. 1. 한 번에 한 개의 알파벳만 바꿀 수 programmers.co.kr dfs를 이용하여 구현함 해결 방안 1. begin이 target과 같을 때의 depth와 minDepth를 비교하여 최소값을 minDepth에 저장함. 그리고 변환 과정이 words 배열의 크기보다 크면 변환할 수 없는 경우이므로 0을 저장함 2. words 전체를 돌면서 dfs를 통해 가장 짧은 변환 과정을 찾아줌..

https://programmers.co.kr/learn/courses/30/lessons/43105?language=java 코딩테스트 연습 - 정수 삼각형 [[7], [3, 8], [8, 1, 0], [2, 7, 4, 4], [4, 5, 2, 6, 5]] 30 programmers.co.kr 동적계획법 문제를 풀기위해서는 큰 문제를 작은 문제로 나누는 과정이 필요함 이 과정을 통해 점화식을 세우는게 중요함 그리고 메모제이션을 해서 시간을 줄이는게 중요함 =>값을 저장해놓음으로써 함수 호출의 시간을 단축시킬수 있으므로 메모제이션 방법으로는 아래와 같은 방법이 있음 1. 반복문을 이용하여 미리 값들에 대한 계산을 다 해서 저장하는 방법 (BOTTOM-UP) 2. 그 순간 필요하면 계산해서 저장하는 방법(..

https://programmers.co.kr/learn/courses/30/lessons/42898#qna 코딩테스트 연습 - 등굣길 계속되는 폭우로 일부 지역이 물에 잠겼습니다. 물에 잠기지 않은 지역을 통해 학교를 가려고 합니다. 집에서 학교까지 가는 길은 m x n 크기의 격자모양으로 나타낼 수 있습니다. 아래 그림은 m = programmers.co.kr 동적계획법 문제를 풀기위해서는 큰 문제를 작은 문제로 나누는 과정이 필요함 이 과정을 통해 점화식을 세우는게 중요함 그리고 메모제이션을 해서 시간을 줄이는게 중요함 =>값을 저장해놓음으로써 함수 호출의 시간을 단축시킬수 있으므로 메모제이션 방법으로는 아래와 같은 방법이 있음 1. 반복문을 이용하여 미리 값들에 대한 계산을 다 해서 저장하는 방법..

https://programmers.co.kr/learn/courses/30/lessons/43104#qna 코딩테스트 연습 - 타일 장식물 대구 달성공원에 놀러 온 지수는 최근에 새로 만든 타일 장식물을 보게 되었다. 타일 장식물은 정사각형 타일을 붙여 만든 형태였는데, 한 변이 1인 정사각형 타일부터 시작하여 마치 앵무조개�� programmers.co.kr 동적계획법 문제를 풀기위해서는 큰 문제를 작은 문제로 나누는 과정이 필요함 이 과정을 통해 점화식을 세우는게 중요함 그리고 메모제이션을 해서 시간을 줄이는게 중요함 =>값을 저장해놓음으로써 함수 호출의 시간을 단축시킬수 있으므로 메모제이션 방법으로는 아래와 같은 방법이 있음 1. 반복문을 이용하여 미리 값들에 대한 계산을 다 해서 저장하는 방법 ..

https://programmers.co.kr/learn/courses/30/lessons/42839 코딩테스트 연습 - 소수 찾기 한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다. 각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이 � programmers.co.kr 재귀호출을 이용하여 완전탐색하였음 해결 방안 1. 주어진 Numbers를 이용하여 만들 수 있는 전체 숫자의 경우를 구함 이 때, 만들어지는 숫자는 순열로 1~N자리의 숫자를 생성할 수 있으므로 nP1 ~ nPn 까지의 전체 숫자를 구해줌 2. 전체의 숫자를 구하면서 nPr의 r만큼의 숫자가 누적되어 만들어지면 중복 판단 및 소수 판단을 하고 ..

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. DFS를 이용하여 전체 여행 경로의 경우를 구하며 한가지의 경로를 String형의 route에 누적한 뒤 한가지 경로가 다 누적되면 routes에 추가함 => 나중에 정렬을 쉽게 이용하기 위하여 String 값으로 저장 2. 목적지가 2가지 이상일 경우 알파벳 순이 되어야하므로 sort 정렬을 이용하여 routes를 정렬함 3. 정렬된 routes.g..

https://programmers.co.kr/learn/courses/30/lessons/43162?language=java 코딩테스트 연습 - 네트워크 네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 A와 컴퓨터 B가 직접적으로 연결되어있고, 컴퓨터 B와 컴퓨터 C가 직접적으로 연결되어 있�� programmers.co.kr 문제 이해 문제의 예시를 보면 왼쪽의 그림은 네트워크가 2개인 경우이고 오른쪽의 그림은 네트워크가 1개인 경우임 즉, n개의 컴퓨터들이 있고 연결되어있는 컴퓨터들이 각각의 네트워크임 따라서 DFS를 통해 연결되어있는 컴퓨터들끼리 네트워크를 구성하므로 네트워크의 갯수를 구해주는 문제임 해결 방안 1. solution() 에서 전체..

https://programmers.co.kr/learn/courses/30/lessons/43165?language=java 코딩테스트 연습 - 타겟 넘버 n개의 음이 아닌 정수가 있습니다. 이 수를 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다. -1+1+1+1+1 = 3 +1-1+1+1+ programmers.co.kr 해결 방안 1. number 배열의 숫자를 계속 빼거나 더하는 두 가지 경우로 나눠져서 DFS를 이용하여 풀었음 2. DFS index가 numbers.length 까지 오게 되면 numbers에 쌓인 값들을 다 더해 sum을 구하고 그 sum이 target과 같으면 answer를 +..

https://programmers.co.kr/learn/courses/30/lessons/43238?language=java 코딩테스트 연습 - 입국심사 n명이 입국심사를 위해 줄을 서서 기다리고 있습니다. 각 입국심사대에 있는 심사관마다 심사하는데 걸리는 시간은 다릅니다. 처음에 모든 심사대는 비어있습니다. 한 심사대에서는 동시에 한 � programmers.co.kr 이분탐색을 응용하여 문제를 구현하였음 이분탐색 알고리즘 코드 int BinarySearch(int arr[], int target) { int start = 0; int end = arr.length - 1; int mid; while(start target) end = mid - 1; else start = mid + 1; } ret..