본문 바로가기

알고리즘 삽질장

 (228)
[프로그래머스] 순위 검색 문제설명 https://programmers.co.kr/learn/courses/30/lessons/72412
[프로그래머스] 예상 대진표 문제설명 https://programmers.co.kr/learn/courses/30/lessons/12985# 코딩테스트 연습 - 예상 대진표 △△ 게임대회가 개최되었습니다. 이 대회는 N명이 참가하고, 토너먼트 형식으로 진행됩니다. N명의 참가자는 각각 1부터 N번을 차례대로 배정받습니다. 그리고, 1번↔2번, 3번↔4번, ... , N-1번↔N programmers.co.kr 사고과정 특정한 자료구조나 알고리즘을 사용하는 문제보다는 규칙을 파악하는 문제인 듯 싶었다. 서로 인접한 번호끼리 묶은 후, 새로운 번호를 부여받는 것인데, 입력 예시로 규칙을 찾아보니, 각 원소가 2로 나누어떨어질 때, 떨어지지 않을 때에 따라 처리해주는 규칙을 찾은 후(소스코드에서 divide 함수) 이 규칙을 계속 적용하..
[프로그래머스] 게임 맵 최단거리 문제설명 https://programmers.co.kr/learn/courses/30/lessons/1844 코딩테스트 연습 - 게임 맵 최단거리 [[1,0,1,1,1],[1,0,1,0,1],[1,0,1,1,1],[1,1,1,0,1],[0,0,0,0,1]] 11 [[1,0,1,1,1],[1,0,1,0,1],[1,0,1,1,1],[1,1,1,0,0],[0,0,0,0,1]] -1 programmers.co.kr 사고과정 전형적인 BFS 유형 문제였다. 2차원 배열이 주어질 때, 특정 시작점에서 도착점까지의 최단거리 비용을 구하는 것이였다. 큐를 활용했고 방문 테이블을 따로 정의해주어서 방문 테이블을 방문 여부 체크와 거리 이동 칸 수를 계산하는 용으로 활용했다. 그리고 주어진 maps 테이블을 활용해서 벽인..
[프로그래머스] 조이스틱 문제설명 https://programmers.co.kr/learn/courses/30/lessons/42860# 코딩테스트 연습 - 조이스틱 조이스틱으로 알파벳 이름을 완성하세요. 맨 처음엔 A로만 이루어져 있습니다. ex) 완성해야 하는 이름이 세 글자면 AAA, 네 글자면 AAAA 조이스틱을 각 방향으로 움직이면 아래와 같습니다. ▲ - 다 programmers.co.kr 사고과정 그리디 문제인데, 상/하 방향, 좌/우 방향 두 개의 기준으로 각각 최소값을 갱신해야 했었다. 개인적으로 그리디 문제가 좀 체감이 많이 어렵다.. 마치 숨겨진 규칙을 찾는 느낌... 애써 풀어보려고 했지만 실패했다.. 구글링을 해서 다른 분의 좋은 풀이를 참고했다. 나는 주어진 문자열에서 모든 문자열을 A로 만드는 관점으로..
[프로그래머스] 소수 찾기 문제설명 https://programmers.co.kr/learn/courses/30/lessons/42839 코딩테스트 연습 - 소수 찾기 한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다. 각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이 programmers.co.kr 사고과정 DFS로 완전탐색 하면서 특정 수가 소수인지 판별하는 알고리즘을 사용하면 된다. 어차피 수는 0~9 사이로 주어진다고 했으니 주어지는 문자열 즉, 숫자가 붙어있는 문자열에 "109"라면 1,0,9 인지 10, 9 인지 따로 처리해주지 않아도되서 편했다. 무조건 1,0,0를 뜻하니깐! 처음에 완전탐색할 때, 부분집합을 구하는 것인가..
[프로그래머스] 프린터 문제설명 https://programmers.co.kr/learn/courses/30/lessons/42587 코딩테스트 연습 - 프린터 일반적인 프린터는 인쇄 요청이 들어온 순서대로 인쇄합니다. 그렇기 때문에 중요한 문서가 나중에 인쇄될 수 있습니다. 이런 문제를 보완하기 위해 중요도가 높은 문서를 먼저 인쇄하는 프린 programmers.co.kr 사고과정 큐를 활용한 풀이었다. 예전에 인프런 강의를 들으면서 풀어보았던 응급실 문제와 매우 유사했다. 오랜만에 풀었지만 그래도 푸는 데 성공! 주의할 점은 이번 문제도 문서의 중요도와 그 문서의 위치를 튜플로 큐에 담고있어야 한다! 그리고 큐 길이가 1이 될때까지 문제에서 주어진 규칙을 수행하면서 큐에서 popleft한 튜플의 원소가 문제에서 매개변수로 ..
[프로그래머스] 전화번호 목록 문제설명 https://programmers.co.kr/learn/courses/30/lessons/42577 코딩테스트 연습 - 전화번호 목록 전화번호부에 적힌 전화번호 중, 한 번호가 다른 번호의 접두어인 경우가 있는지 확인하려 합니다. 전화번호가 다음과 같을 경우, 구조대 전화번호는 영석이의 전화번호의 접두사입니다. 구조 programmers.co.kr 사고과정 해쉬를 사용해야 하는 풀이라는데 해결하지 못했다.. 접두어를 어떻게 활용해야할지 고민하다가 결국 포기.. 예전에 풀었던 풀이로는 테스트 케이스가 추가되지 않아서 통과되지 않았다(startswith 문법 사용한 풀이) 그래서 해쉬를 활용한 정석으로 풀어보자 했는데 풀이법을 떠올리기 쉽지 않았다.. 그래서 다른 분의 풀이 중에 해쉬를 활용한 정..
[프로그래머스] 빛의 경로 사이클 문제설명 https://programmers.co.kr/learn/courses/30/lessons/86052 코딩테스트 연습 - 빛의 경로 사이클 각 칸마다 S, L, 또는 R가 써져 있는 격자가 있습니다. 당신은 이 격자에서 빛을 쏘고자 합니다. 이 격자의 각 칸에는 다음과 같은 특이한 성질이 있습니다. 빛이 "S"가 써진 칸에 도달한 경우, 직진 programmers.co.kr 사고과정 DFS 탐색으로 사이클을 판별하는 문제라는 것을 인지는 했지만 어떻게 풀어나가야 할지 도저히 감이 오지 않았다.. 그래서 문제의 질문하기에서 어떤 분이 설명해주신 글을 보고 방문용 테이블을 3차원 배열로 정의해야 한다는 것을 알았다..보통은 사이클을 판별하기 위해서는 도착한 방향에 상관없이 그냥 그 노드에만 다시 돌..
[프로그래머스] 튜플 문제설명 https://programmers.co.kr/learn/courses/30/lessons/64065 코딩테스트 연습 - 튜플 "{{2},{2,1},{2,1,3},{2,1,3,4}}" [2, 1, 3, 4] "{{1,2,3},{2,1},{1,2,4,3},{2}}" [2, 1, 3, 4] "{{4,2,3},{3},{2,3,4,1},{2,3}}" [3, 2, 4, 1] programmers.co.kr 사고과정 문자열 형태로 주어지는 것을 보니 스택을 활용해야 하는 듯한 문제 느낌이 팍! 왔다. 크게 보면 스택 유형의 문제인 듯 하다. 문제에서 주의해야 할 점은 튜플의 부분집합 결과가 주어졌을 때, 이를 튜플로 변환해야 하는데 튜플의 원소 순서가 다르면 다른 것으로 간주한다는 점이다. 이를 어떻게 활..
[프로그래머스] 수식 최대화 문제설명 https://programmers.co.kr/learn/courses/30/lessons/67257 코딩테스트 연습 - 수식 최대화 IT 벤처 회사를 운영하고 있는 라이언은 매년 사내 해커톤 대회를 개최하여 우승자에게 상금을 지급하고 있습니다. 이번 대회에서는 우승자에게 지급되는 상금을 이전 대회와는 다르게 다음과 programmers.co.kr 사고과정 느낌이 스택과 완전탐색을 활용한 문제라고 생각했다. DFS를 활용해서 연산 우선순위 완전탐색을 잘 구현하긴 했지만 우선순위 연산에 따라 스택을 활용해서 계산을 계속 갱신하는 데 실패했다.. 대체 스택을 어떻게 활용해야 할까.. 어려워서 1시간 넘게 고민한 후 결국 구글링의 도움을 받았다. 결과적으로 DFS 탐색으로 완전탐색으로 구현해도 되었지..
[프로그래머스] 거리두기 확인하기 문제설명 https://programmers.co.kr/learn/courses/30/lessons/81302 코딩테스트 연습 - 거리두기 확인하기 [["POOOP", "OXXOX", "OPXPX", "OOXOX", "POXXP"], ["POOPX", "OXPXP", "PXXXO", "OXXXO", "OOOPP"], ["PXOPX", "OXOXP", "OXPOX", "OXXOP", "PXPOX"], ["OOOXX", "XOOOX", "OOOXX", "OXOOX", "OOOOO"], ["PXPXP", "XPXPX", "PXPXP", "XPXPX", "PXPXP"]] [1, 0, 1, 1, 1] programmers.co.kr 사고과정 문제를 풀기 위해서 크게 DFS 탐색을 활용해서 구현했다. 그리고 pla..
[프로그래머스] 뉴스 클러스터링 문제설명 https://programmers.co.kr/learn/courses/30/lessons/17677 코딩테스트 연습 - [1차] 뉴스 클러스터링 뉴스 클러스터링 여러 언론사에서 쏟아지는 뉴스, 특히 속보성 뉴스를 보면 비슷비슷한 제목의 기사가 많아 정작 필요한 기사를 찾기가 어렵다. Daum 뉴스의 개발 업무를 맡게 된 신입사원 튜브 programmers.co.kr 사고과정 해쉬를 사용해 풀이를 했다. 주의해야 할 점은 문제에서 자카드 유사도를 설명해주고 구하는 공식을 설명해주는데, 이 때 '원소의 중복을 허용하는 다중집합' 일 경우를 고려해야 하기 때문에 섣불리 집합자료구조(set)으로 하게 되면 구현할 수가 없다고 생각했다. 우선 주어진 집합 각 A, B에 대한 해쉬를 만들어서 원소를 키로..
[프로그래머스] 메뉴 리뉴얼 문제설명 https://programmers.co.kr/learn/courses/30/lessons/72411 코딩테스트 연습 - 메뉴 리뉴얼 레스토랑을 운영하던 스카피는 코로나19로 인한 불경기를 극복하고자 메뉴를 새로 구성하려고 고민하고 있습니다. 기존에는 단품으로만 제공하던 메뉴를 조합해서 코스요리 형태로 재구성해서 programmers.co.kr 사고과정 문제가 DFS 탐색으로 완전탐색을 하는 것이라고 예상했다. 심지어 주어진 문제 범위도 매우 작았다. 처음에 문제에서 얻어지는 조합 개수마다 각 개수에서 '가장 많이 함께 주문된 단품메뉴'를 한 번에 캐치하지 못해서 그냥 단순히 2명의 이상 손님에게 함께 주문된 단품메뉴를 추출한 후 왜 답이랑 다르지? 생각했다. 문제를 다시 읽고 캐치한 후 구현에..
[프로그래머스] 행렬 테두리 회전하기 문제설명 https://programmers.co.kr/learn/courses/30/lessons/77485 코딩테스트 연습 - 행렬 테두리 회전하기 6 6 [[2,2,5,4],[3,3,6,6],[5,1,6,3]] [8, 10, 25] 3 3 [[1,1,2,2],[1,2,2,3],[2,1,3,2],[2,2,3,3]] [1, 1, 5, 3] programmers.co.kr 사고과정 행렬을 90도 회전하는 문제가 아닌 행렬 형상은 유지하면서 위치를 시계방향으로 한칸씩 이동시켜야 했다.. 처음에 스와핑을 이용해서 구현하려 했지만 실패했다.. 그러면 테두리 해당하는 행렬을 뽑아서 일차원 리스트로 한 다음 한 칸 씩 이동시켜야 할까? 했지만 여러개의 쿼리가 주어지면서 이동시킨 값을 행렬 위치에 계속 갱신시켜야 ..
[프로그래머스] 짝지어 제거하기 문제설명 https://programmers.co.kr/learn/courses/30/lessons/12973 코딩테스트 연습 - 짝지어 제거하기 짝지어 제거하기는, 알파벳 소문자로 이루어진 문자열을 가지고 시작합니다. 먼저 문자열에서 같은 알파벳이 2개 붙어 있는 짝을 찾습니다. 그다음, 그 둘을 제거한 뒤, 앞뒤로 문자열을 이어 붙 programmers.co.kr 사고과정 같은 알파벳이 2개 연속으로 있는 것을 제거해야 한다는 점에서 스택을 이용해야 하는 문제라는 게 감이 팍 왔다. 그래서 연습장에 스택으로 어떻게 구현해야 할지 고민하는 시간을 가졌다. 몇 번의 시행착오 끝에 주어진 문자열 s 원소를 loop로 돌면서 스택이 비어있거나 스택 마지막 원소가 현재 돌고 있는 원소랑 동일하지 않으면 스택에..
[프로그래머스] 타겟 넘버 문제설명 https://programmers.co.kr/learn/courses/30/lessons/43165 코딩테스트 연습 - 타겟 넘버 n개의 음이 아닌 정수가 있습니다. 이 수를 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다. -1+1+1+1+1 = 3 +1-1+1+1+ programmers.co.kr 사고과정 주어진 numbers 중에 len(numbers) 개수 만큼 순열 경우의 수를 완전탐색하는 DFS를 활용하는 문제였다. 단, 상태트리를 만들 때, 특정 수를 더해주거나 빼줄지 두 갈래길로 뻗어나가도록 해주어야 한다. 그리고 백트래킹할 경우에는 해당 인덱스 숫자에 -를 붙여서 res 리스트에 ..
[프로그래머스] 더 맵게 문제설명 https://programmers.co.kr/learn/courses/30/lessons/42626 코딩테스트 연습 - 더 맵게 매운 것을 좋아하는 Leo는 모든 음식의 스코빌 지수를 K 이상으로 만들고 싶습니다. 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 Leo는 스코빌 지수가 가장 낮은 두 개의 음식을 아래와 같 programmers.co.kr 사고과정 최소 힙 정렬을 이용하는 문제이다. 우선 최소 힙에다가 주어지는 스코빌 지수를 모두 담아서 최소 힙 안에서 스코빌 지수 기준으로 오름차순 정렬하도록 만든다. 그리고 최소 힙 길이가 1이 될 때까지 무한 반복문을 도는데, 이 때, 최소 힙의 가장 앞자리에 있는 값이 K보다 크거나 같으면 바로 break하면 된다. 왜냐하면 최소 힙 안..
[프로그래머스] 기능개발 문제설명 https://programmers.co.kr/learn/courses/30/lessons/42586 코딩테스트 연습 - 기능개발 프로그래머스 팀에서는 기능 개선 작업을 수행 중입니다. 각 기능은 진도가 100%일 때 서비스에 반영할 수 있습니다. 또, 각 기능의 개발속도는 모두 다르기 때문에 뒤에 있는 기능이 앞에 있는 programmers.co.kr 사고과정 큐를 활용한 문제였다. 힌트는 문제에서 '기능 개발이 모두 완료되더라도 배포 순서는 앞에서부터 지켜야 한다'라는 텍스트로부터 캐치할 수 있었다. 그래서 작업 진도가 담겨있는 배포순서가 담긴 progresses 와 속도 speeds 리스트 모두 큐로 변환시켜준 뒤 매번 해당 작업에 해당 속도를 추가한다. 그리고 순간마다 큐 맨 앞에 작업완..
[프로그래머스] 124 나라의 숫자 문제설명 https://programmers.co.kr/learn/courses/30/lessons/12899 코딩테스트 연습 - 124 나라의 숫자 programmers.co.kr 사고과정 이것도 DP로 풀어야 하나 싶었지만 그런 문제는 아니었다. N진법 변환문제인건가 싶었지만 그것도 아니었다.. 엄청 난해한 문제라 질문하기에서 아이디어를 봤는데 3진법을 좀 특수적으로 운영해서 풀어야 했다.. 즉, 3진법을 이용하되 3으로 나누어떨어질때는 몫을 하나 감소시켜서 나머지가 0이 안되게 한 뒤 3은 4로 바꾸어주저야 한다.. 매우 난해한 문제인 듯하다.. 이걸 어찌 풀라고...흑 풀이(스스로 못 푼 풀이) def solution(n): answer = '' while n: t = n % 3 if not t:..
[프로그래머스] 멀쩡한 사각형 문제설명 https://programmers.co.kr/learn/courses/30/lessons/62048 코딩테스트 연습 - 멀쩡한 사각형 가로 길이가 Wcm, 세로 길이가 Hcm인 직사각형 종이가 있습니다. 종이에는 가로, 세로 방향과 평행하게 격자 형태로 선이 그어져 있으며, 모든 격자칸은 1cm x 1cm 크기입니다. 이 종이를 격자 선을 programmers.co.kr 사고과정 주어진 문제 범위가 1억이라 DP문제일 것 같아서 어떻게든 규칙을 찾아내려 했다.. 그러나 실패했다.. 질문하기 탭에 가서 보았는데, w, h의 최대공약수를 활용해서 푸는 문제였다..윾.. 그래도 덕분에 파이썬으로 최대공약수를 구현하는 방법을 알게 되었다. 일명 유클리드 호제법! 유클리드 호제법은 큰 수를 작은수로 나..

티스토리툴바