😎 문제 설명 https://school.programmers.co.kr/learn/courses/30/lessons/67257 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제는 단순했다. 문자열로 주어진 수식을 계산하되, 연산자의 우선순위를 임의로 지정해 최댓값을 구하도록 하는 문제였다. 이때 수식을 계산한 값은 절댓값으로 비교하고, 최종 결괏값이 2의 63승 미만으로 나오기 때문에 long long 타입을 적극적으로 활용해야하는 문제였다. 💗 해결 과정 수식에는 최대 3개의 연산자가 주어져있고, 이 연산자의 우선순위를 정해서 Brute-force ..
😊문제 설명 해결 방법이 쉽사리 떠오르지 않는 구현 문제였다. 문자열 형태로 주어진 숫자 입력 중 K개를 제거하여 만든 문자열이 최대가 되도록 한다. 🐹 코드 설명 먼저, 큰 숫자를 만들기 위해서는 앞쪽의 숫자들 중 제거할 수 있는 것을 최대한 제거하여 제일 앞의 숫자를 큰 숫자로 만들어야 한다. 이때 제거할 수 있는 갯수는 정해져있으므로, 이 숫자를 제거할 지 말 지 앞으로 더 제거할 수 있는 갯수(K)를 기반으로 결정하면 된다. 4177252841라는 예제입력으로 설명해보겠다. 4 입장에서, 자신을 없애지 않으면 뒤의 네 가지 숫자를 없앨 수 있다. (K = 4) 뒤의 네 가지 숫자는 1, 7, 7, 2이다. 이 중에서 7은 4보다 크며, 7을 제거하는 것보다 4를 제거하는 것이 더 좋은 선택이다. ..
😎 문제 설명 😀 풀이 과정 후보키를 고르는 모든 조합을 비트마스크 집합을 이용하여 표현하였다. 아무것도 고르지 않는 i = 0를 제외한 모든 조합을 for문을 이용해 순회하며, 유일성과 최소성을 검사하여 사용이 가능한 후보키라면 답에 추가해주었다. 비트마스크의 원소 하나하나는 최대 8개의 Attribute의 집합을 표현하고 있고, 원소가 1이면 후보키, 0이면 후보키가 아닌 것으로 가정하였다. 어떻게 유일성을 검사하나요 ? i번, j번 Attribute가 후보키라고 가정하자. 모든 튜플의 i번, j번 속성에 해당하는 문자열을 이어붙인다. 그 결괏값 중에 중복되는 문자열이 하나라도 있으면 (i, j)는 후보키가 될 수 없다. 예를 들어서, ["이름", "전공"]을 후보키로 한 경우에 예제 입력에 주어진 ..
https://www.acmicpc.net/problem/16234 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모 www.acmicpc.net 문제 설명 구현 태그에 속한 문제이다. 문제를 요약해보자. 매일 각 나라의 인구를 인접한 나라와 비교하면서, L 이상 R 이하의 인구 수의 차이를 가진 나라와 국경선을 모두 열어 연합을 만든다. 이 연합에 속한 나라들의 인구수의 평균만큼 각 나라의 인구를 세팅한다. 1, 2번 과정을 반복하다가 더 이상 국경선을 열 수 있는 나라가 없을 때 인구 이동을 종료한다. 코드 설명 구현 문제..
https://www.acmicpc.net/problem/14499 14499번: 주사위 굴리기 첫째 줄에 지도의 세로 크기 N, 가로 크기 M (1 ≤ N, M ≤ 20), 주사위를 놓은 곳의 좌표 x, y(0 ≤ x ≤ N-1, 0 ≤ y ≤ M-1), 그리고 명령의 개수 K (1 ≤ K ≤ 1,000)가 주어진다. 둘째 줄부터 N개의 줄에 지 www.acmicpc.net 문제 설명 주사위를 굴릴 때마다 주사위의 숫자와 지도의 숫자가 계속해서 바뀌는 문제이다. 단순 구현 문제이므로 조건에 맞추어 주사위를 굴리는 상황을 구한다. 코드 설명 문제 해결 과정은 크게 세 가지로 나뉜다. K개의 방향으로 이동하는 것을 구현한다. 만약, 주사위가 이동할 수 없다면 이 명령을 무시한다. 입력된 방향으로 주사위를 ..
https://www.acmicpc.net/problem/3190 3190번: 뱀 'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 게임 www.acmicpc.net 문제 해설 단순 구현 문제이고, 처리해야하는 예외가 많아 시뮬레이션 해보고 구현해야하는 문제였다. 주의해야할 문제의 조건은 아래와 같다. 뱀의 머리가 먼저 이동한 후, 그 위치의 사과의 유무에 따라 꼬리의 이동 유무가 결정된다. 이 순서에 맞게 구현해야 한다. 방향을 전환할 때, 현재 뱀의 머리의 방향을 기준으로 왼쪽, 오른쪽 방향으로 전환한다. 뱀의 꼬리는 뱀의 머리가 지나간 위치로만 이동할 수 있다...
https://www.acmicpc.net/problem/28082 28082번: 기계오리 연구 인하대학교 기계공학과의 기계오리 연구실에서는 2023년 버전 기계오리를 완성하기 위해 실험을 진행하고 있다. 실험 도중, 기계오리에 1개 이상 $K$개 이하의 배터리를 삽입하면 기계오리가 언 www.acmicpc.net KnapSack을 응용한 DP 문제이다. 사용할 수 있는 배터리의 총 개수는 N, 기계오리에 장착할 수 있는 배터리의 최대 개수는 K이다. 배터리의 개수가 1 이상, K 이하일 때 만들 수 있는 모든 전력량을 출력하자. 배터리의 사용 개수가 K 이하인 전력량의 합이 하나라도 있다면 그 전력량은 출력한다. 따라서, 각 전력량의 합을 만들 수 있는 배터리의 최소 개수를 저장한 뒤, 최소 개수가 K..
https://www.acmicpc.net/problem/28081 28081번: 직사각형 피자 첫 번째 줄에 피자의 가로 길이 $W$와 세로 길이 $H$, 부원들이 먹을 수 있는 피자 조각의 최대 크기 $K$가 공백으로 구분되어 주어진다. 두 번째 줄에 가로 방향 커팅의 개수 $N$이 주어진다. 세 번 www.acmicpc.net 입력 제한이 큰 문제이기 때문에, 일반적인 브루트 포스 알고리즘으로 풀면 안 되고, 이분탐색 알고리즘으로 푼다. 가로 방향과 세로 방향에서의 피자 조각의 크기를 모두 배열에 저장한 다음, 각각의 가로 방향의 길이에 대해서 곱이 K 이하가 되는 세로 방향의 크기의 Upper bound 를 구한다. 이때 세로 방향에서의 피자 조각의 크기는 오름차순 정렬되어있으므로, Upper b..
https://www.acmicpc.net/problem/28079 28079번: 배 옮기기 치훈이는 배 \(N\)척을 강 건너편으로 옮기려고 한다. 강을 건너가거나 건너오기 위해서는 치훈이가 가지고 있는 배를 운전하여 건너야 한다. 배의 크기가 \(X\)라고 할 때, 치훈이가 그 배를 운전 www.acmicpc.net Bridge and torch problem과 유사한 문제로, 배가 한 번 이동하고 나면 다시 돌아와야 다음 과정을 진행할 수 있다는 점이 특징이다. 모든 배를 강 건너편 (오른쪽)으로 이동시키는 가장 최소 시간을 출력하자. 1. 문제의 상태를 비트마스크를 이용해 하나의 정점으로 만들어 그래프를 생성한다. 배의 크기 순대로 정렬 후, 강을 건너지 않은 배들은 0, 강을 건넌 배들은 1로 ..
