분류 전체보기

취준 및 신입 백엔드 개발자를 꿈꾸는 학생개발자에게 | Naver D2 [배민스토어] 신입 개발자 배민스토어 6개월 생존기 | 우아한형제들 기술블로그 {{item.name}} 어떤글인가요? 안녕하세요. 작년 겨울, 우아한테크코스를 수료하고 올해 1월에 배민스토어서비스개발팀으로 입사한 유현호입니다. 이제 막 6개월간의 수습 기간을 마치고 배민스토어 techblog.woowahan.com 신입 백엔드 개발자 혼돈의 파일럿 프로젝트 돌아보기 (feat.정산플랫폼팀) | 우아한형제들 기술 {{item.name}} 안녕하세요. 이제 막 파일럿을 끝내고 정산플랫폼팀에 합류한 신입 개발자 김윤정입니다. 길고 고되지만 재밌었던 우아한테크코스 교육을 끝내고 마침내 우아한형제들에 입사 techblog.woowahan.co..

문제 접근 방식 생긴 거만 봐도 DFS 문제인 것을 알 수 있지만 DFS만으로 풀고 제출하면 시간초과가 발생한다. DFS에 DP까지 활용해야 하는데 아래의 경우를 생각해 보자 이 사진에서 오른쪽 경우는 왼쪽이 이미 방문한 20부터의 순서를 그대로 반복하는데 이미 갔던 길을 다시 가는 거라면 굳이 또 갈 필요가 없이 해당 구간으로 가는 길에 계산된 값을 그대로 사용하면 된다. 즉, 처음 가는 구간이라면 계속해서 도착 지점에 방문할 때까지 탐색하고 탐색 중에 이미 방문한 곳이라면 그 구간에 저장되어 있는 값을 더 해준다. 방문 여부를 기록할 불리언 배열은 필요 없고 2차원의 DP 테이블에 값이 채워져 있으면 기존에 방문한 것을 알 수 있기 때문에 이를 활용해서 탐색을 진행해 주면 된다. 이번 문제가 아니더라..

문제 접근 방식 1차원 배열의 구간합 원리를 2차원 배열에 적용하면 풀 수 있는 문제다. 1 2 3 4 2 3 4 5 3 4 5 6 4 5 6 7 위와 같은 배열이 주어졌을 때 2,2 부터 3,4까지의 구간합을 구하려면 2,2 ~ 2,4의 구간합 + 3,2 ~ 3,4의 구간합을 더해주면 된다. 1 3 6 10 2 5 9 14 3 7 12 18 4 9 15 22 위처럼 각 행마다의 누적합을 구해둔 후에 이 누적합을 이용해 각 행의 특정 부분의 구간합을 구해주면 된다. 예를 들어 2,2 ~ 2,4까지의 구간합은 2,4까지의 누적합에서 2,1의 누적합을 뺀 것이고 3,2 ~ 3,4까지의 구간합은 3,4까지의 누적합에서 3,1의 누적합을 뺀 것이다. 결국 x축을 기준으로 시작 x축부터 끝나는 x축까지 반복하며 ..

문제 접근 방식 각 자리의 수마다 경우의 수를 이전 자리의 수들을 활용해가며 DP 테이블을 채워주면 되는 간단한거 같은 문제지만 예외 케이스가 머리를 아프게 한다. 우선 11111111과 같은 일반적인 경우를 살펴보겠다. 1 1 1 1 1 1 1 1 1 2 3 5 8 13 21 34 위의 표는 첫 자리부터 각 자리수마다 만들 수 있는 경우의 수로 3번째 자리의 수에 올 수 있는 경우의 수는 3번째 자리를 독립적으로 사용한 경우나 2번째 자리와 합쳐서 두 자리 수를 만든 경우를 합친 것으로 규칙을 찾아보면 피보나치의 점화식과 같은 dp[i] = dp[i-2] + dp[i-1] 인 것을 알 수 있다. 하지만 이건 모든 수들이 일반적일 때의 경우로 다음과 같이 조심해야 할 부분이 있다. 0으로 시작하는 경우 ..

문제 접근 방식 배열에서 특정 부분만 확인 했을 때 팰린드롬인지 판별하는 문제다. DP 문제이긴 하지만 이전 값을 사용해 테이블을 채워나가는 방식은 아니고 길이별로 팰린드롬인지 직접 확인해서 테이블에 저장해 s와 e를 입력 받을 때마다 매번 계산하지 않고 저장된 값을 읽는 방식이다. 1, 2, 1, 3, 1, 2, 1 위와 같은 배열의 경우에는 다음과 같은 테이블이 만들어진다. 1 2 1 3 1 2 1 1 T F T F F F T 2 T F F F T F 1 T F T F F 3 T F F F 1 T F T 2 T F 1 T 숫자가 하나인 경우는 무조건 팰린드롬이니 참으로 설정해두고 2개 이상인 경우만 판단하면 되고, 시작점이 끝점보다 큰 경우는 없기 때문에 자기 자신의 인덱스 이전은 신경 쓸 필요가 없..

문제 접근 방식 1인 부분으로만 이루어진 정사각형 중 가장 큰 정사각형을 찾아야 한다. 1 11 11 111 111 111 위와 같이 1로만 이루어진 곳을 찾아야 하는데 1인 곳을 발견할 때마다 주변을 한 칸씩 넓혀가며 모두 1인지 확인하는 것은 시간초과가 날 것이 확실하기 때문에 그렇게 무식하게 풀 수는 없다. 00 01 위의 경우를 생각해보면 1 주변은 모두 0이기 때문에 정사각형이 될 수 없고 크기가 1인 정사각형 하나만 가능하다. 11 11 1 > 2 ... > n 순으로 길이를 늘려주기만 하면 된다. 풀이 public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new Buf..

문제 접근 방식 이전 동전 문제처럼 k원을 만드는 모든 경우의 수를 구하는 것이 아니라 가장 적은 수의 동전을 사용해 k원을 만들 수 있는 경우를 구해야 한다. 5원, 1원, 12원 총 3개의 동전으로 15원을 만들어야 할 때 5원으로 15원을 만들 수 있는 경우를 먼저 생각해 보자 1원을 만드는 경우 : X 2원을 만드는 경우 : X 3원을 만드는 경우 : X 4원을 만드는 경우 : X 5원을 만드는 경우 : 1 6원을 만드는 경우 : X 7원을 만드는 경우 : X 8원을 만드는 경우 : X 9원을 만드는 경우 : X 10원을 만드는 경우 : 2 11원을 만드는 경우 : X 12원을 만드는 경우 : X 13원을 만드는 경우 : X 14원을 만드는 경우 : X 15원을 만드는 경우 : 3 위와 같이 5원..

문제 접근 방식 [백준] 2293번 : 동전 1 문제 접근 방식 1원, 2원, 5원 총 3가지의 동전으로 1원부터 10원을 만드는 경우를 적어보면 다음과 같다. 11 211 2 3111 12 41111 112 22 511111 1112 122 5 6111111 11112 1122 15 222 71111111 111112 11122 115 1222 25 811111111 1 da9dac.tistory.com 위의 문제와 입출력만 좀 다를 뿐 사실상 풀이가 같은 문제라 설명은 생략하겠다. 풀이 class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new Input..