구현

[프로그래머스 Lv.2] 괄호 변환 (Python)

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/60058 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr풀이DFS와 구현이 섞인 문제로 볼 수 있다. 흔히 볼 수 있는 DFS 문제와 다르긴 하나, 재귀를 사용해 한 문장 p의 끝까지 들어가며 특정 로직을 적용하기에 DFS 문제라고 생각한다.구현 부분은 어려운 알고리즘을 사용하는 게 아니다 보니, 문제에 주어진 대로 그저 한 단계씩 구현하면 된다. 한 단계씩 구현해 나가고, 재귀적으로 다시 실행해야 하는 부분은 DFS를 통해 진행하면 비교적 쉽게 풀 수 있다.  처음에는 p의 길이가 10..

[프로그래머스 Lv.2] 줄 서는 방법 (Python)

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/12936 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr풀이처음에 단순하게 문제를 생각했을 때, itertools의 permutation을 활용하여 순열을 모두 생성해 두고, 여기서 k번째에 해당하는 순열을 찾는 방식으로 해결하려 하였다. 하지만 n의 최댓값인 20의 경우를 생각하여 보면, 20!이라는 어마무시한 숫자이기에 이 방법으로는 해결이 불가능하였다. 그래서 약간은 수학적인 방법을 사용해보았다. n=3일 때의 간단한 예시를 들어보겠다.[1, 2, 3], [1, 3, 2], [2, ..

[프로그래머스 Lv.2] 스킬트리 (Python)

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/49993 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr풀이스킬트리대로 스킬을 하나씩 배워나갈 때마다 해당 스킬이 선행 관계가 존재하는 스킬인 경우, 그 스킬이 순서에 맞게 배워졌는지 체크하고 만약 그렇지 않다면 이는 옳지 않은 스킬트리이므로 바로 배제하고, 스킬트리의 모든 스킬들을 모두 무사히 배웠다면 이는 올바른 스킬트리인 것이다. 즉, 스킬이 선행 관계가 존재하는 스킬인지 확인하는 로직과 순서에 맞게 배워졌는지 체크하는 로직을 코드로 구현하면 쉽게 풀 수 있는 문제이다. 먼저 스킬이..

[프로그래머스 Lv.2] 2개 이하로 다른 비트 (Python)

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/77885 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr풀이x보다 크고 x와 비트가 1~2개 다른 수들 중에서 제일 작은 수를 구하는 함수를 구현하는 문제이다.구현 문제이기에 우선 간단한 예시를 통해 규칙을 찾아야 한다. 2부터 시작하여 규칙을 찾아보겠다.2는 이진수로 10이고 2보다 크고 2와 비트가 1~2개 다른 수들 중 제일 작은 수는 이진수로 11로 3이다.3은 이진수로 11이고 3보다 크고 3과 비트가 1~2개 다른 수들 중 제일 작은 수는 이진수로 101으로 5이다.4는 이진수..

(Python) 백준 2578번 - 빙고

문제 링크: https://www.acmicpc.net/problem/2578 풀이단순 구현 문제로, 우리가 빙고 게임을 실제 하는 방법을 코드로 구현하면 되는 간단한 문제이다. 먼저 입력받은 숫자들을 board라는 배열에 담아, 빙고판을 완성한다. 다음으로 사회자가 부르는 수들을 called_nums라는 배열에 저장한다.사회자가 수를 하나씩 부를 때마다 숫자를 board에서 지우고(-1로 변경), 현재 board의 상태에서 몇 개의 빙고가 존재하는지 카운트한다. 그리고 카운트한 값이 3 이상이면 그때의 수가 몇 번째로 부른 숫자인지 출력하면 된다. 주의해야 할 점은 반드시 3 이상인지 체크해야 한다는 것이다. 빙고의 수가 정확히 3인지 체크를 하다 보니, 하나의 수에 의해 빙고가 한 번에 2개 이상 완..

[프로그래머스 Lv.2] 거리두기 확인하기 (Python)

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/81302 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr풀이이 문제는 BFS로도 풀 수 있으나 배열의 크기가 5 X 5로 상당히 작으며 또한 맨해튼 거리가 2 이내인 경우가 아래의 6가지 경우 밖에 없기에 이 경우만 조건문으로 체크해 주면 더 간단하게 풀이가 될 것이라고 판단하여 BFS를 사용하지 않았다.아래가 사람인 경우두 칸 아래가 사람이며 중간에 파티션이 없는 경우오른쪽 대각선 아래가 사람이며 중간에 파티션이 없는 경우왼쪽 대각선 애라개 ..

[프로그래머스 Lv.2] 삼각 달팽이 (Python)

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/68645 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr풀이2단계 문제이기에 코드 자체의 구현 난이도는 어렵지 않으나 풀이를 위한 아이디어를 생각하는 것이 난이도에 비해 어려웠다.아이디어는 피라미드 모형으로 되어있는 예시의 배열을 아래처럼 좌측으로 붙여 정렬을 시키는 것이었다.이렇게 좌측으로 정렬함으로써 배열을 채워나가는 로직을 생각하는 것이 훨씬 쉬워진다.배열의 절반인 삼각형을 이루는 칸을 벗어나거나, 배열에 이미 값이 채워진 경우 채워가는 ..

[프로그래머스 Lv.2] 행렬 테두리 회전하기 (Python)

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/77485?language=python3 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr풀이우선 아래와 같이 우측으로 행렬의 테두리를 회전하도록 풀이해 보았다. 하지만 아래 풀이대로 진행하면 시간 초과가 발생한다. rows와 columns가 100이고, queries도 10000 이하이므로 풀이 로직 상에서는 시간 초과가 발생하지 않을 것이라고 생각하였으나 시간 초과가 발생하여 상당히 당황스러웠었다.시간 초과 발생 코드import copydef ..

(C++) 백준 15686번 - 치킨 배달

문제 링크 : https://www.acmicpc.net/problem/15686 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net 풀이 Permutation을 사용하여 M개의 치킨집들의 조합을 뽑아내고 이에 대한 모든 집에서의 치킨 거리를 구한 후 모두 더함으로써 도시의 치킨 거리를 구하였다. 골드 문제치고 난이도가 어렵진 않다. 다만 Permutation을 사용하여 조합을 뽑아내는 방법에 익숙해질 필요가 있다고 느낀 문제였다. #include #include #include #define..

(C++) 백준 18808번 - 스티커 붙이기

문제 링크 : https://www.acmicpc.net/problem/18808 18808번: 스티커 붙이기 혜윤이는 최근에 다양한 대회를 참여하면서 노트북에 붙일 수 있는 스티커들을 많이 받았다. 스티커는 아래와 같이 사각 모눈종이 위에 인쇄되어 있으며, 스티커의 각 칸은 상하좌우로 모두 연 www.acmicpc.net 풀이 모든 경우를 고려하여 풀이를 진행해야 하는 브루트포스 문제이다. 스티커를 회전하는 것을 구현하는 방법을 생각하는 것과 스티커를 붙일 수 있는 경우를 판별하는 방법을 구현하는 것이 매우 어려웠다. 또한 checknput() 메서드의 이중 for문 뒤에 위치한 제일 마지막 경우를 체크하기 위한 코드를 생각하지 못해 상당히 헤매었다. #include using namespace std..