![]()
문제 https://school.programmers.co.kr/learn/courses/30/lessons/43162 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 풀이 풀고 나서 Lv3가 맞나..? 싶은 문제였다. 인접행렬을 사용해서 풀면 쉽게 풀 수 있는 문제지만 Lv3라서 뭔가 복잡하게 풀어야 될 거 같아서 나름대로 복잡하게(?) 풀었다. 문제에서 요구하는 바는 연결할 수 있을 만큼 최대한으로 연결하고, 연결된 그룹의 수를 구하는 것이다. 여러 가지 방법이 있겠지만, 나는 노드를 구현해서 풀어보고 싶어서 해당 방식으로 풀었다. 우선 크게 노드..
![]()
문제 https://www.acmicpc.net/problem/1445 1445번: 일요일 아침의 데이트 첫째 줄에 숲의 세로 크기 N과 가로 크기 M이 주어진다. N과 M은 3보다 크거나 같고, 50보다 작거나 같은 자연수이다. 둘째 줄부터 숲의 지도가 주어진다. 숲의 지도는 S, F, g, . 만으로 이루어져 있 www.acmicpc.net 문제 풀이 나는 해당 문제를 전형적인 bfs 문제라고 생각한다. 하지만 bfs 문제에서도 조금 더 진화한 문제이다. 우선 문제 초기에는 DP를 사용해서 주변에 존재하는 쓰레기를 저장해서 방문 처리를 하려고 했지만, 결과적으로 도착지점에 도착한 경우에 최적의 도착을 해야하기 때문에, 도착한 시점에 우리는 가장 적은 쓰레기를 마주치고 밟아야 한다. 그렇기 때문에 DP..
![]()
문제 https://www.acmicpc.net/problem/16932 16932번: 모양 만들기 N×M인 배열에서 모양을 찾으려고 한다. 배열의 각 칸에는 0과 1 중의 하나가 들어있다. 두 칸이 서로 변을 공유할때, 두 칸을 인접하다고 한다. 1이 들어 있는 인접한 칸끼리 연결했을 때, 각각의 www.acmicpc.net 문제 풀이 항상 높은 난도의 BFS, DFS를 풀면 알 수 있듯이 최적화에 가장 신경을 써야 한다. 그렇지 않다면 무수히 많은 시간초과를 볼 수 있을 것이다... 문제의 핵심은 빈칸을 선택해서 사각형으로 바꾸고, 가장 길게 연결된 사각형의 크기를 구하는 것이다. 그렇다면 우리는 기존의 배열에서 사각형들을 라벨링 하는 것이 필요하다. 왜 라벨링을 해야하는가에 대해서 작업의 흐름을 판..
![]()
문제 https://www.acmicpc.net/problem/15659 15659번: 연산자 끼워넣기 (3) 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, www.acmicpc.net 문제 풀이 정말 까다로운 문제였다. 연산자들의 우선순위를 해결해줘야 했기에, 그 부분에서 사람들이 많이 어려움을 느꼈을 것이라고 생각한다. dfs를 이용해서 모든 경우의 수를 탐색하고, 해당 식의 최솟값과 최댓값을 구한다. 초기 풀이 방식에서는 숫자와 연산자들을 모두 포함하는 배열을 하나 생성했지만, 숫자들은 고정이고, 연산자들의..
![]()
문제 https://www.acmicpc.net/problem/1062 1062번: 가르침 첫째 줄에 단어의 개수 N과 K가 주어진다. N은 50보다 작거나 같은 자연수이고, K는 26보다 작거나 같은 자연수 또는 0이다. 둘째 줄부터 N개의 줄에 남극 언어의 단어가 주어진다. 단어는 영어 소문 www.acmicpc.net 문제 풀이 최적화에 신경 쓰지 않는다면 엄청난 시간초과를 맛볼 수 있는 문제이다. 최대한 경우의 수를 줄여서 최소한의 탐색으로 해결해야 한다. 학생들은 K개의 글자를 배우고, K개의 글자로 이루어진 단어만 읽을 수 있다. 즉 우리는 N개의 단어 중에서 K개의 글자를 골라서 주어진 N개의 단어들 중에서 최대한 많이 읽어야 한다. 문제에서는 친절하게 반드시 배워야 할 글자들을 제시해 준다..
![]()
문제 https://www.acmicpc.net/problem/15486 15486번: 퇴사 2 첫째 줄에 N (1 ≤ N ≤ 1,500,000)이 주어진다. 둘째 줄부터 N개의 줄에 Ti와 Pi가 공백으로 구분되어서 주어지며, 1일부터 N일까지 순서대로 주어진다. (1 ≤ Ti ≤ 50, 1 ≤ Pi ≤ 1,000) www.acmicpc.net 문제 풀이 DP의 대표적인 유형이다. DP는 항상 DP 배열이 무엇을 의미하는지 정하는 것이 가장 중요하다. 내가 정한 DP 배열은 다음과 같다. DP[i]는 i일에 벌 수 있는 최대 금액 1일 2일 3일 4일 5일 6일 7일 3 5 1 1 2 4 2 10 20 10 20 15 40 200 문제에서 주어진 예시는 다음과 같다. 우리는 N일까지의 상담을 바탕으로 ..
![]()
문제 https://www.acmicpc.net/problem/1106 1106번: 호텔 첫째 줄에 C와 형택이가 홍보할 수 있는 도시의 개수 N이 주어진다. C는 1,000보다 작거나 같은 자연수이고, N은 20보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 각 도시에서 홍보할 때 www.acmicpc.net 문제 풀이 처음에 그리디인 줄 알고 접근했다가, 도저히 그리디로 할 수가 없어서 DP로 접근방식을 수정했다. DP문제에서 가장 중요한 점은 DP 배열을 어떤 식으로 설계하느냐이다. 다양한 방법으로 설계할 수 있지만, 문제에서는 최소한의 비용으로 목표 인원수를 모을 수 있느냐에 초점을 맞추기 때문에 DP배열의 index를 비용으로 잡았다. 그 부분이 나중에 최소 비용을 찾기 편하다고 생각했..
![]()
문제 https://www.acmicpc.net/problem/17135 17135번: 캐슬 디펜스 첫째 줄에 격자판 행의 수 N, 열의 수 M, 궁수의 공격 거리 제한 D가 주어진다. 둘째 줄부터 N개의 줄에는 격자판의 상태가 주어진다. 0은 빈 칸, 1은 적이 있는 칸이다. www.acmicpc.net 문제 풀이 문제가 조금 길어서 요약해 보면 다음과 같다. 궁수의 위치는 N행 즉 주어진 배열 한 칸 아래에 있다. 궁수는 3명이고, 한 칸의 한 명만 있다. 궁수의 사정거리는 D이하이고, 여러명의 궁수가 하나의 적을 공격할 수 있다. 궁수는 반드시 가장 가까운 적을 공격해야하고, 가장 가까운 적이 여러 명이라면 가장 왼쪽의 적을 공격한다. 중요한 점은 하나의 적이 여러 명의 궁수에게 공격받을 수 있다는..
![]()
코틀린에서 특정 문자열이 포함되어 있는지 아닌지를 판별하기 위해 사용되는 정규표현식을 적을까 합니다. 우선 정규표현식의 정의를 알아볼 건데 아래 내용은 위키피디아에서 가져왔습니다. 정규표현식이란? 특정한 규칙을 가진 문자열의 집합을 표현하는 데 사용되는 형식 언어 (위키피디아) 그렇다면 정규표현식은 어떠한 상황에서 사용될까요? 휴대폰번호를 입력받는데, 휴대폰 번호의 양식과 일치하는지 판별(숫자만 와야 함) email를 입력받는데, @가 있는지, 비밀번호 양식 (몇 글자이상, 특수문자 한 글자 포함, 대문자 한글자 포함 등등) 이러한 예외처리를 if문을 통해서 할 경우 굉장히 코드가 복잡해지고, 더러워집니다. 따라서 코틀린에서는 Regex를 제공해서 문자열에서 특정 문자열이 포함되어 있는지를 판별해 줍니다..
