요즘은 백준으로 유형별 문제를 풀고 있다. 그 중에서도 bfs(너비 완전 탐색)문제들을 풀고 있다. 처음에는 조금 쉬운 문제 위주로 풀어서 금방 풀었지만, 조금씩 어려운 문제를 풀다보니 조금 더 응용을 요하는 것 같다. 풀이 방법을 고민하다가 다른 사람의 풀이를 참고했다. 스타트링크에서 판매하는 어린이용 장난감 중에서 가장 인기가 많은 제품은 구슬 탈출이다. 구슬 탈출은 직사각형 보드에 빨간 구슬과 파란 구슬을 하나씩 넣은 다음, 빨간 구슬을 구멍을 통해 빼내는 게임이다. 보드의 세로 크기는 N, 가로 크기는 M이고, 편의상 1×1크기의 칸으로 나누어져 있다. 가장 바깥 행과 열은 모두 막혀져 있고, 보드에는 구멍이 하나 있다. 빨간 구슬과 파란 구슬의 크기는 보드에서 1×1크기의 칸을 가득 채우는 사이..
[ 프로그래머스 ] 정수 삼각형 (C++)
전형적인 DP 문제다. 뭐.. 어렵지 않게 풀었다. 나는 재귀 방식으로 풀었는데, 다른 사람의 풀이를 보니까 굳이 재귀방식으로 풀지 않아도 되는 방법도 있어서 정리해보려한다. 위와 같은 삼각형의 꼭대기에서 바닥까지 이어지는 경로 중, 거쳐간 숫자의 합이 가장 큰 경우를 찾아보려고 합니다. 아래 칸으로 이동할 때는 대각선 방향으로 한 칸 오른쪽 또는 왼쪽으로만 이동 가능합니다. 예를 들어 3에서는 그 아래칸의 8 또는 1로만 이동이 가능합니다. 삼각형의 정보가 담긴 배열 triangle이 매개변수로 주어질 때, 거쳐간 숫자의 최댓값을 return 하도록 solution 함수를 완성하세요. 제한사항 삼각형의 높이는 1 이상 500 이하입니다. 삼각형을 이루고 있는 숫자는 0 이상 9,999 이하의 정수입니다..
이제 Level3을 풀게되니까 난이도가 갑자기 올라갔다.. 이번 문제도 재귀함수와 set을 이용하여 풀어서 구현은 간신히 했으나 시간초과..😨 이제부터는 구현도 어렵지만 구현보다는 효율적인 알고리즘과 방법을 생각하는 것이 관건이다..! 그 방법을 생각해내면 금방 풀 수 있지만 그 방법을 생각하는 것이 어렵다 ㅠㅠ 그래서 이번 문제도 다른사람의 풀이를 조금 참고하여 풀었다. 일렬로 나열된 n개의 풍선이 있습니다. 모든 풍선에는 서로 다른 숫자가 써져 있습니다. 당신은 다음 과정을 반복하면서 풍선들을 단 1개만 남을 때까지 계속 터트리려고 합니다. 임의의 인접한 두 풍선을 고른 뒤, 두 풍선 중 하나를 터트립니다. 터진 풍선으로 인해 풍선들 사이에 빈 공간이 생겼다면, 빈 공간이 없도록 풍선들을 중앙으로 밀..
처음에 이 문제 풀 때 다 풀지 못했다. 이 문제는 효율성 테스트가 있어서 효율적인 알고리즘을 생각해야한다. 무식한 방법으로 매번 for문을 돌려서 체크하는 것은 정확성 테스트에서는 맞을 수 있어도, 효율성 테스트를 넘어가지 못한다. 이 문제를 풀려했던 날에 컨디션이 안좋았던 것도 있고, 내 실력이 조금 부족해서도 있겠지만 해결할 방법이 생각나지 않았었다. 결국 어떻게 문제에 접근해야하는지 카카오 해설을 참고했고, 쉽게 풀 수 있었다. 내가 스쳐 생각했던 방법과 비슷했지만 시도해보진 않았었는데 이게 맞았었다니..! 문제를 풀면 풀수록 해시 즉, unordered_map 을 사용해야하는 문제가 많다는 것을 느낀다. 카카오는 하반기 경력 개발자 공개채용을 진행 중에 있으며 현재 지원서 접수와 코딩테스트가 종..
문자열과 정렬을 이용한 문제다. 클래스를 이용하여 어렵지 않게 풀었지만 그냥 정렬만을 이용하여 간단히 푼 풀이를 봤다. 충분히 나도 생각할 수 있는 수준이었다. 풀이를 보고 이해한 후에 다시 한번 풀어봤다. 다음에 비슷한 문제를 풀 때는 이렇게 간단하게 풀 수 있었으면 좋겠다. 그 때 생각이 났으면 좋겠다는 바람으로 정리를 해보려고 한다. 근데 속도는 내 코드가 훨씬 빠르게 나오는데 뭐가 더 좋은 코드인걸까..?! 어렵당 😨 세 차례의 코딩 테스트와 두 차례의 면접이라는 기나긴 블라인드 공채를 무사히 통과해 카카오에 입사한 무지는 파일 저장소 서버 관리를 맡게 되었다. 저장소 서버에는 프로그램의 과거 버전을 모두 담고 있어, 이름 순으로 정렬된 파일 목록은 보기가 불편했다. 파일을 이름 순으로 정렬하면 ..
최소공약수를 구하는 방법과 최소공배수를 구하는 방법 모두 자주 등장하는 문제이다. 유클리드 호제법을 이용하여 구하는 최소공약수, 그리고 최소공배수는 두 수의 곱/최소공약수이다. 그런데 이 문제에서는 여러개의 최소공배수를 구해야한다. 어떻게 구해야할 지 고민하다가 다른 풀이를 참고했다. 다음부터는 번뜩 생각나도록 정리해보기로 했다. 두 수의 최소공배수(Least Common Multiple)란 입력된 두 수의 배수 중 공통이 되는 가장 작은 숫자를 의미합니다. 예를 들어 2와 7의 최소공배수는 14가 됩니다. 정의를 확장해서, n개의 수의 최소공배수는 n 개의 수들의 배수 중 공통이 되는 가장 작은 숫자가 됩니다. n개의 숫자를 담은 배열 arr이 입력되었을 때 이 수들의 최소공배수를 반환하는 함수, so..
종류별로 해시를 이용하여 정보를 저장하는 것은 어렵지 않았다. 그런데, 조합의 갯수를 어떻게 구해야할지 어려웠다. 이론적으로 구할 수는 있었으나 코드로 구현하려면 너무 복잡해보였다. 다른 사람의 팁을 참고하여서 엄청난 풀이를 알아냈다..!!!😲 다음에 이런 종류의 문제에서 이런 사고방식을 떠올릴 수 있었으면 좋겠다. 스파이들은 매일 다른 옷을 조합하여 입어 자신을 위장합니다. 예를 들어 스파이가 가진 옷이 아래와 같고 오늘 스파이가 동그란 안경, 긴 코트, 파란색 티셔츠를 입었다면 다음날은 청바지를 추가로 입거나 동그란 안경 대신 검정 선글라스를 착용하거나 해야 합니다. 종류 이름 얼굴 동그란 안경, 검정 선글라스 상의 파란색 티셔츠 하의 청바지 겉옷 긴 코트 스파이가 가진 의상들이 담긴 2차원 배열 c..
인덱스 접근 오류가 몇번 나서 고치는 것 말고는 문제 이해도 쉽고 풀기에도 어렵지 않았던 문제다. 다른 사람의 풀이를 보던 중, 나와 너무 다르고 쉽게 접근한 것을 발견했다. 그리고 문제 자체가 해시에 분류되어 있는 만큼 해시를 이용해 푼 풀이도 있었다. 그래서 정리를 해보려고한다. 전화번호부에 적힌 전화번호 중, 한 번호가 다른 번호의 접두어인 경우가 있는지 확인하려 합니다. 전화번호가 다음과 같을 경우, 구조대 전화번호는 영석이의 전화번호의 접두사입니다. 구조대 : 119 박준영 : 97 674 223 지영석 : 11 9552 4421 전화번호부에 적힌 전화번호를 담은 배열 phone_book 이 solution 함수의 매개변수로 주어질 때, 어떤 번호가 다른 번호의 접두어인 경우가 있으면 false..