반갑습니다!

프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 입력값의 범위가 작기 때문에 완전탐색으로 해결할 수 있는 문제이다. 항상 자물쇠의 크기가 열쇠의 크기 이상이기 때문에 자물쇠를 확장하여서 풀이하였다. 위 그림의 기존의 자물쇠를 가로, 세로로 확장하여 아래의 그림과 같이 만든다. 이 상태에서 열쇠를 회전시켜가며 탐색하면 된다. 위의 그림들과 같은 순서로 모든 지점을 탐색하면 된다. (그림이 너무 많아져서 생략...) 코드 #include #include using namespace std; // 배열 90도 회전 함수 void rotate(vector& ..

프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 해당 문제는 크게 3단계로 풀이된다. 사다리 설치가 필요없는 지형들 그룹화 그룹화된 지형들 사이를 이동하는 최소 비용 저장 저장된 최소 비용들로 MST 생성 1. 사다리 설치가 필요없는 지형들 그룹화 DFS 혹은 BFS를 사용하여 사다리가 필요없이 이동가능한 지형들을 하나의 그룹으로 표시한다. 아래의 코드에서는 방문 여부를 체크하는 visited배열을 int형으로 선언하여 방문 여부의 체크와 그룹 표시를 같이 진행하였다. 2. 그룹화된 지형들 사이를 이동하는 최소 비용 저장 visited배열에 그룹을 구..

프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 문제가 길어서 어렵다고 겁먹을 수 있지만 명시된 규칙대로 구현하면 의외로 쉽게 해결할 수 있다. '균형잡힌 괄호 문자열'의 여부는 stack을 이용하여 확인하였다. 자세한 풀이는 주석으로 남겨두었다. 코드 C++ #include #include #include using namespace std; // 올바른 괄호 문자열인지 체크해주는 함수 bool isCorrect(string str) { stack s; for (char c : str) { if (c == '(') s.push(c); else { i..

프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 직선의 방정식을 구해서 직선보다 y좌표 값이 작은 사각형의 개수를 구하고 2배하는 방법으로 풀어보려했지만 시간초과가 계속 발생해서 결국 방법을 바꿔서 해결한 문제이다. 규칙을 찾는게 어려운 문제였다. 풀이 잘리는 사각형의 개수를 패턴을 통해서 알 수 있다. w와 h의 최대공약수를 g라고 하면 가로가 w/g, 세로가 h/g인 패턴이 g번 반복되는 것을 알 수 있다. (아래 그림 참조) 그리고 해당 패턴 안에 잘리는 사각형을 생각해보면 w/g + h/g - 1개의 사각형이 잘린다는 것을 알 수 있다. 따라서 가능..

프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 규칙성을 찾아서 해결하는 문제이다. 처음엔 규칙이 잘 보이지 않았지만 차분하게 생각해보니 간단한 규칙을 발견할 수 있었다. 풀이 종이를 접게 되면 접은 선의 개수는 홀수가 된다. n번 접은 종이의 선들 중에서 가운데 선을 기준으로 왼쪽의 선들은 n-1번 접은 종이의 선의 모양과 같다는 것을 알 수 있다. 가운데 있는 선은 제일 처음 반을 접을 때 생기는 선이므로 결국 가운데 선을 중심으로 원점 대칭 꼴이라는 것을 알 수 있다. 예시로 확인해보면 3번 접은 경우는 0 0 1 0 0 1 1 0 0 0 1 1 0 ..