본문 바로가기

Problem Solving

 (152)
[백준 / Python] 체스판 다시 칠하기 문제 설명 문제 풀이 우선 다른 알고리즘이 떠오르지 않아 무식하게 모든 경우의 수를 풀어내고자 했다. 체스판 사이즈만큼 모든 보드를 돌아보며 실행하면 (8 * 8) * (50 - 8 + 1) * (50 - 8 + 1)번이며 이는 1억번보다 작아 풀어낼 수 있겠다고 생각했다. 검은색으로 시작하는 경우와 흰색으로 시작하는 경우를 한 번에 확인하기 위해 black, white를 선언했고 row가 바뀔 때마다 색이 바뀌는 것을 보고 따로 코드로 작성해주었다. 이후 각 경우에서 색칠해야하는 횟수가 가장 적은 것을 최솟값으로 저장한 후 제출하였다. 코 드 import sys N, M = map(int,sys.stdin.readline().split()) board = [] for i in range(N): list..
[프로그래머스/Python] 행렬 테두리 회전하기 문제 설명 rows x columns 크기인 행렬이 있습니다. 행렬에는 1부터 rows x columns까지의 숫자가 한 줄씩 순서대로 적혀있습니다. 이 행렬에서 직사각형 모양의 범위를 여러 번 선택해, 테두리 부분에 있는 숫자들을 시계방향으로 회전시키려 합니다. 각 회전은 (x1, y1, x2, y2)인 정수 4개로 표현하며, 그 의미는 다음과 같습니다. x1 행 y1 열부터 x2 행 y2 열까지의 영역에 해당하는 직사각형에서 테두리에 있는 숫자들을 한 칸씩 시계방향으로 회전합니다. 다음은 6 x 6 크기 행렬의 예시입니다. 이 행렬에 (2, 2, 5, 4) 회전을 적용하면, 아래 그림과 같이 2행 2열부터 5행 4열까지 영역의 테두리가 시계방향으로 회전합니다. 이때, 중앙의 15와 21이 있는 영역은..
[프로그래머스] 숫자의 표현 수학적 풀이 및 증명 문제 해석 Finn은 요즘 수학공부에 빠져 있습니다. 수학 공부를 하던 Finn은 자연수 n을 연속한 자연수들로 표현 하는 방법이 여러개라는 사실을 알게 되었습니다. 예를들어 15는 다음과 같이 4가지로 표현 할 수 있습니다. 1 + 2 + 3 + 4 + 5 = 15 4 + 5 + 6 = 15 7 + 8 = 15 15 = 15 자연수 n이 매개변수로 주어질 때, 연속된 자연수들로 n을 표현하는 방법의 수를 return하는 solution를 완성해주세요. 제한사항 n은 10,000 이하의 자연수 입니다 문제 풀이 [풀이 1번: 투포인터] 숫자 1만까지를 1부터 N까지 합이 1만일 때, 2부터 N까지 합이 1만일 때... 모든 경우를 찾는 코드를 처음에 생각해냈다.시간이 너무 길어질 것 같아서 꼼수를 생각해..
[백준/C++] 9935번 문자열 폭발 풀이 문제 해석 문제 풀이 우선 문자열은 100만 개라 O(N2)으로는 풀 수 없을 것 같았다. 문제에서 문자열을 찾아서 지워내면 되는 것이니 스택이나 정규식 풀이 방법이 먼저 떠올랐다. mirkovC4nizCC44 에서 C4를 추려내는 등의 과정을 고려했더니 문자열을 비교할 때 어디까지 겹치는 문자열을 보유했었는지 저장하도록 하였다. (전에 문자열 알고리즘 중에 이런 게 있었는데 까먹었다.ㅎㅎ) [로직] 문자열과 폭발 문자열을 한 문자씩 비교하며 정답 문자열에 추가한다. 문자가 같다면 폭발 문자열의 인덱스를 하나 증가시킨다. 다르다면 지금 인덱스를 스택에 넣어 저장하고 현재 문자열부터 다시 비교한다. 만약 인덱스가 폭발 문자열의 길이와 같다면 길이만큼 정답 문자열에서 제거한다. 만약 이전 인덱스 스택이 비었..
[백준/C++] 14003번 가장 긴 증가하는 부분 수열 5 풀이 문제 해석 문제 풀이 우선 수열의 크기가 100만이라서 O(N2) 풀이로는 해결할 수 없다. dp +이분탐색을 이용한 O(NlogN) 풀이 방법이 필요하다. 풀이 방법은 14002번을 풀어보면 알 수 있는데 DP 배열을 1차원으로 사용한다고 생각해보면 될 것 같다. 지금 숫자가 내가 가진 숫자 최대값보다 크다면 배열의 마지막 값으로 추가한다. (코드상 order 배열) 지금 숫자가 최대값보다 작다면 이분탐색을 통해 지금 숫자보다 큰 최소값과 교환해준다. 이 때 1차원 DP의 경우 값을 덮어 씌워가며 계산을 진행하는게 정석인데, 가장 긴 증가하는 부분 수열의 길이를 찾을 때 바뀌어나간 값들의 길이가 최대가 되지 않는 이상 길이 자체에는 영향을 미치지 않는다. 여기까지가 14002번의 문제 풀이다. 그러나 ..
[프로그래머스/Python] 수식 최대화 문제 설명 IT 벤처 회사를 운영하고 있는 라이언은 매년 사내 해커톤 대회를 개최하여 우승자에게 상금을 지급하고 있습니다. 이번 대회에서는 우승자에게 지급되는 상금을 이전 대회와는 다르게 다음과 같은 방식으로 결정하려고 합니다. 해커톤 대회에 참가하는 모든 참가자들에게는 숫자들과 3가지의 연산문자(+, -, *) 만으로 이루어진 연산 수식이 전달되며, 참가자의 미션은 전달받은 수식에 포함된 연산자의 우선순위를 자유롭게 재정의하여 만들 수 있는 가장 큰 숫자를 제출하는 것입니다. 단, 연산자의 우선순위를 새로 정의할 때, 같은 순위의 연산자는 없어야 합니다. 즉, + > - > * 또는 - > * > + 등과 같이 연산자 우선순위를 정의할 수 있으나 +,* > - 또는 * > +,-처럼 2개 이상의 연산자..
[프로그래머스/Python] 순위 검색 문제 설명 [본 문제는 정확성과 효율성 테스트 각각 점수가 있는 문제입니다.] 카카오는 하반기 경력 개발자 공개채용을 진행 중에 있으며 현재 지원서 접수와 코딩테스트가 종료되었습니다. 이번 채용에서 지원자는 지원서 작성 시 아래와 같이 4가지 항목을 반드시 선택하도록 하였습니다. 코딩테스트 참여 개발언어 항목에 cpp, java, python 중 하나를 선택해야 합니다. 지원 직군 항목에 backend와 frontend 중 하나를 선택해야 합니다. 지원 경력구분 항목에 junior와 senior 중 하나를 선택해야 합니다. 선호하는 소울푸드로 chicken과 pizza 중 하나를 선택해야 합니다. 인재영입팀에 근무하고 있는 니니즈는 코딩테스트 결과를 분석하여 채용에 참여한 개발팀들에 제공하기 위해 지원자..
[프로그래머스/C++] 거리두기 확인하기 문제 해석 문제 설명 개발자를 희망하는 죠르디가 카카오에 면접을 보러 왔습니다. 코로나 바이러스 감염 예방을 위해 응시자들은 거리를 둬서 대기를 해야하는데 개발 직군 면접인 만큼 아래와 같은 규칙으로 대기실에 거리를 두고 앉도록 안내하고 있습니다. 대기실은 5개이며, 각 대기실은 5x5 크기입니다. 거리두기를 위하여 응시자들 끼리는 맨해튼 거리1가 2 이하로 앉지 말아 주세요. 단 응시자가 앉아있는 자리 사이가 파티션으로 막혀 있을 경우에는 허용합니다. 예를 들어, 위 그림처럼 자리 사이에 파티션이 존재한다면 맨해튼 거리가 2여도 거리두기를 지킨 것입니다. 위 그림처럼 파티션을 사이에 두고 앉은 경우도 거리두기를 지킨 것입니다. 위 그림처럼 자리 사이가 맨해튼 거리 2이고 사이에 빈 테이블이 있는 경우는..

티스토리툴바