문제 https://www.acmicpc.net/problem/15686 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net 개요 문제를 처음 봤을 때 백트래킹 문제임을 바로 파악하지는 못했다. 이차원 배열이 주어져서 당연하게 DFS 혹은 BFS로 접근해야겠다고 생각했다. 백트래킹을 고려하지 않고 있었기 때문에, 여러 개의 치킨집 중에서 M개를 어떻게 선택해야 할지 고민하는 데에 시간을 굉장히 많이 썼다. 이 문제 또한 결국 구글링의 힘을 빌렸다...! (언제쯤 혼자 풀어낼 거냐..나 자신아...
분류 전체보기
문제 https://www.acmicpc.net/problem/14889 14889번: 스타트와 링크 예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다. www.acmicpc.net 개요 문제를 읽자마자 백트래킹을 이용해겠다고 생각했다. 바로 이전에 백트래킹 문제를 한 번 풀어봤기 때문에 감을 살려서 도전했다. 그러나, 백트래킹 함수를 구현할수록 코드가 너무 과하게 복잡해지는 느낌이 들었고, 테스트케이스 실행 시 자꾸 다른 답이 도출되었다. 결구 이 문제 또한 구글링을 시도했다...! 구글링한 후 코드를 참고하고 이해한 후에, 다시 내 식대로 코드를 작성했는데 테스트케이스 3가지는 모두 통과..
문제 https://www.acmicpc.net/problem/14888 14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, 곱 www.acmicpc.net 개요 문제를 읽자마자 백트래킹을 사용해야하겠다고 생각했다. 그러나, 백트래킹 문제를 안 풀어본지 너무 오래 되어서 함수를 어떻게 짜야 할지 뇌정지가 왔다. 그래서 결국 뇌정지를 이겨내지 못하고 구글링을 했다. (이 때 좀 현타가 세게 왔다.) 문제 풀이 전형적인 백트래킹 문제이다. 먼저, 수열과 연산자를 각각 배열에 저장한다. 그리고..
문제 https://www.acmicpc.net/problem/14501 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net 개요 문제를 다 읽자마자 DP로 접근해야겠다는 생각이 들었다. 그래서 dp[i]를 'i번째 날까지의 최대 금액'으로 정한 후에, 점화식을 계속 생각해보았는데, 20분 넘게 떠올리지 못했다. 이차원 dp 배열을 이용한 접근도 시도했는데, 파고들수록 더 복잡해질 것 같았다. 그래서 결국 구글링한 후에 블로그 글을 참고하여 풀었다. 문제 풀이 이 문제의 핵심은 앞에서부터 생각하는 것이 아니라, 뒤에서부터 생각하는 것이다. 1일 2일 3일 4일 5일 6일 7일 t[i] 3 5 1 1 2 4 2 p[i] 10 20 10 20 15 40 ..
문제 https://www.acmicpc.net/problem/1183 1183번: 약속 마법사 N명이 머글 문화를 이해하기 위해 머글과 약속을 잡았다. 각 마법사는 한 명의 머글을 만날 예정이다. 하지만, 마법사는 약속 시간보다 빨리 또는 늦게 도착할 수 있기 때문에 고민에 빠 www.acmicpc.net 개요 실버 랜덤 디펜스를 처음 시작했다. PS가 습관이 되지 않아 뭔가 새로운 자극이 필요했고, DP, 그리디 등의 알고리즘 분류를 모르는 채로 문제를 맞닥뜨린 채로 문제를 풀 수 있는 랜덤 디펜스를 습관 들이기로 했다. 실버 랜덤 디펜스가 정상적으로 습관화되고, 실버 문제를 빠른 시간 내에 정확히 푸는 실력이 갖추어지면 그 때 골드 랜덤 디펜스로 넘어가야겠다고 생각했다. 실랜디를 시작하고 맞이한 첫..
문제 https://www.acmicpc.net/problem/16928 16928번: 뱀과 사다리 게임 첫째 줄에 게임판에 있는 사다리의 수 N(1 ≤ N ≤ 15)과 뱀의 수 M(1 ≤ M ≤ 15)이 주어진다. 둘째 줄부터 N개의 줄에는 사다리의 정보를 의미하는 x, y (x < y)가 주어진다. x번 칸에 도착하면, y번 칸으 www.acmicpc.net 개요 처음 문제를 봤을 때 어떻게 구현해야 할지 감이 바로 오지 않았다. 10 x 10 크기의 100칸짜리 보드판이 주어졌기 때문에, 10 x 10 의 2차원 배열을 만들어야 하는 것인가 생각했다. 왜냐하면, 이 문제가 그래프 카테고리에 있었기 때문에 DFS 또는 BFS를 사용하는 문제일텐데, 궁극적으로 목적지까지의 최소 거리를 구하는 문제이므로..
문제 https://school.programmers.co.kr/learn/courses/30/lessons/17680 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 개요 문제 조건에 '캐시 교체 알고리즘은 LRU (Least Recently Used)를 사용한다.'라고만 명시되어 있고, LRU 알고리즘에 대한 설명은 없어서 약간은 당황했다. 물론, 학교 수업에서 LRU 교체 알고리즘에 대해 배운 적이 있어서 알고는 있었지만, 이렇게 PS에 등장하니까 약간 벙쪘었다. LRU 교체 알고리즘은 가장 덜 최근에 사용된 것, 즉 가장 오랫동안 사용(혹은 참조)되..
문제 https://school.programmers.co.kr/learn/courses/30/lessons/131127 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 개요 문제 내용 자체는 이해하기 크게 어렵지 않았다. 처음에는 투포인터 방식으로 코드를 작성했다. 처음 구현했던 방식은 12개의 테스트 중 단 1개만 통과하고, 나머지는 다 틀렸다. 다른 방식을 고민하다가, want 길이와 number의 길이가 최대 10이고, discount의 길이는 최대 10만이기 때문에 부담 없이 중첩 for문을 사용해도 되겠다는 생각이 들었다. 그래서 굳이 복잡하게 ..
