본문 바로가기

알고리즘 삽질장

 (228)
[프로그래머스] 완주하지 못한 선수 문제설명 https://programmers.co.kr/learn/courses/30/lessons/42576 코딩테스트 연습 - 완주하지 못한 선수 수많은 마라톤 선수들이 마라톤에 참여하였습니다. 단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였습니다. 마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수 programmers.co.kr 사고과정 예전에 아나그램 문제에서 배운 딕셔너리 해쉬 문법을 활용해서 수월하게 구현했다! 다시한번 문법을 상시시켜보자. 빈 딕셔너리에 key, value 값을 바로 넣고자 한다면 dict.get(key, val) 이라고 하면 dict 이라는 딕셔너리에 key의 value 값에 아무것도 없으면 val을 생성하라는 뜻! 풀이 def so..
[프로그래머스] 소수 만들기 문제설명 https://programmers.co.kr/learn/courses/30/lessons/12977 코딩테스트 연습 - 소수 만들기 주어진 숫자 중 3개의 수를 더했을 때 소수가 되는 경우의 개수를 구하려고 합니다. 숫자들이 들어있는 배열 nums가 매개변수로 주어질 때, nums에 있는 숫자들 중 서로 다른 3개를 골라 더했을 때 programmers.co.kr 사고과정 문제에서 주어진 nums 에서 3개를 뽑아 만들 수 있는 경우의 수를 구하고 그 합이 소수인지 판별해서 소수라면 카운트하는 문제였다. nums에서 3개를 뽑아 만들 수 있는 경우의 수를 구하기 위해 중복을 허용하지 않는 3개를 뽑는 조합을 DFS로 하나하나씩 탐색하면서 한 조합을 구했을 때, 그 원소의 합이 소수인지 판별하는..
[프로그래머스] 내적 문제설명 https://programmers.co.kr/learn/courses/30/lessons/70128 코딩테스트 연습 - 내적 길이가 같은 두 1차원 정수 배열 a, b가 매개변수로 주어집니다. a와 b의 내적을 return 하도록 solution 함수를 완성해주세요. 이때, a와 b의 내적은 a[0]*b[0] + a[1]*b[1] + ... + a[n-1]*b[n-1] 입니다. (n은 a, b의 programmers.co.kr 사고과정 행렬 내적을 리스트로 구현하는 문제였다. 풀이 def solution(a, b): answer = 0 for i in range(len(a)): answer += a[i] * b[i] return answer
[프로그래머스] 음양 더하기 문제설명 https://programmers.co.kr/learn/courses/30/lessons/76501 코딩테스트 연습 - 음양 더하기 어떤 정수들이 있습니다. 이 정수들의 절댓값을 차례대로 담은 정수 배열 absolutes와 이 정수들의 부호를 차례대로 담은 불리언 배열 signs가 매개변수로 주어집니다. 실제 정수들의 합을 구하여 re programmers.co.kr 사고과정 쉬운 구현 문제였다. 숫자와 부호 모두 같은 리스트이고 같은 인덱스를 갖기 때문에 부호 True/False 에 따라 그 인덱스의 숫자값을 더해주거나 빼주면서 총 합을 구하면 된다. 풀이 def solution(absolutes, signs): answer = 0 for i in range(len(absolutes)): ..
[프로그래머스] 없는 숫자 더하기 문제설명 https://programmers.co.kr/learn/courses/30/lessons/86051 코딩테스트 연습 - 없는 숫자 더하기 0부터 9까지의 숫자 중 일부가 들어있는 배열 numbers가 매개변수로 주어집니다. numbers에서 찾을 수 없는 0부터 9까지의 숫자를 모두 찾아 더한 수를 return 하도록 solution 함수를 완성해주세요. 제한 programmers.co.kr 사고과정 매우 쉬운 유형의 구현 문제였다. 스킬적인 부분을 쓰기보다 에프엠 식으로 풀려고 했다. 그 중에 계수정렬을 활용해서 풀어보았다. 풀이 def solution(numbers): # 계수 정렬 활용 counts = [0] * 10 for num in numbers: counts[num] += 1 an..
[프로그래머스] 크레인 인형뽑기 게임 문제설명 https://programmers.co.kr/learn/courses/30/lessons/64061 코딩테스트 연습 - 크레인 인형뽑기 게임 [[0,0,0,0,0],[0,0,1,0,3],[0,2,5,0,1],[4,2,4,4,2],[3,5,1,3,1]] [1,5,3,5,1,2,1,4] 4 programmers.co.kr 사고과정 문제에서 크레인 위치가 2차원 배열 board의 열을 의미한다고 볼 수 있다. 그리고 각 크레인의 위치마다 가장 상위의 인형을 뽑아낸다고 했으니 크레인 위치가 주어졌을 때, board의 열은 크레인 위치로 고정시키고 행만 loop로 돌면서 인형이 발견되었을 때 바구니에 넣어준다. 이 때 바구니는 스택으로 구현하면 된다. 그런데 바구니에 인형을 새롭게 넣어주기 전에, 바구..
[프로그래머스] 키패드 누르기 문제설명 https://programmers.co.kr/learn/courses/30/lessons/67256 코딩테스트 연습 - 키패드 누르기 [1, 3, 4, 5, 8, 2, 1, 4, 5, 9, 5] "right" "LRLLLRLLRRL" [7, 0, 8, 2, 8, 3, 1, 5, 7, 6, 2] "left" "LRLLRRLLLRR" [1, 2, 3, 4, 5, 6, 7, 8, 9, 0] "right" "LLRLLRLLRL" programmers.co.kr 사고과정 우선 주어지는 키패드 좌표를 2차원 배열로 나타내었다. 이유는 키패드 간의 거리를 계산하기 위해서. 거리 계산할 때는 맨해튼 거리 기법을 사용했다. 주어진 거리가 1이라고 해서 맨해튼 거리를 적용할 수 있었다. 한 가지 중요한 점은 f..
[프로그래머스] 숫자 문자열과 영단어 문제설명 https://programmers.co.kr/learn/courses/30/lessons/81301 코딩테스트 연습 - 숫자 문자열과 영단어 네오와 프로도가 숫자놀이를 하고 있습니다. 네오가 프로도에게 숫자를 건넬 때 일부 자릿수를 영단어로 바꾼 카드를 건네주면 프로도는 원래 숫자를 찾는 게임입니다. 다음은 숫자의 일부 자 programmers.co.kr 사고과정 우선은 숫자를 알파벳로 나타낸 문자와 그에 매핑되는 숫자를 딕셔너리로 만들었다. 그리고 주어지는 문자와 숫자가 합해진 문자열 하나하나씩 도는데, 숫자이면 바로 결과값에 append 시켰다. 만약 알파벳인 경우에는 알파벳 하나하나 받을 때마다 딕셔너리의 key에 있는 값들 중에 존재하는지 확인하면서 숫자를 알파벳으로 나타낸 문자가 완성..
[프로그래머스] 신규 아이디 추천 문제설명 https://programmers.co.kr/learn/courses/30/lessons/72410 코딩테스트 연습 - 신규 아이디 추천 카카오에 입사한 신입 개발자 네오는 "카카오계정개발팀"에 배치되어, 카카오 서비스에 가입하는 유저들의 아이디를 생성하는 업무를 담당하게 되었습니다. "네오"에게 주어진 첫 업무는 새로 programmers.co.kr 사고과정 하.. 카카오 블라인드 문제는 레벨 1도 매우 까다롭다..증말.. 시간을 재서 풀지는 않았는데 오래걸리더라도 기어코 풀어냈다.. 1단계는 매우 쉽게 lower() 로 구현하면 된다 2단계는 replace 함수가 기본적으로 inplace가 안되기 때문에 무조건 새로운 변수 또는 기존 변수에 재할당시켜주어야 한다.. 이것때문에 또 시간 걸림..
[프로그래머스] 로또의 최고 순위와 최저 순위 문제설명 https://programmers.co.kr/learn/courses/30/lessons/77484 코딩테스트 연습 - 로또의 최고 순위와 최저 순위 로또 6/45(이하 '로또'로 표기)는 1부터 45까지의 숫자 중 6개를 찍어서 맞히는 대표적인 복권입니다. 아래는 로또의 순위를 정하는 방식입니다. 1 순위 당첨 내용 1 6개 번호가 모두 일치 2 5개 번호 programmers.co.kr 사고과정 이제 인프런 강의도 다 듣고 프로그래머스로 문제 유형을 사전에 확인하지 않고 실전 문제 풀이에 도전하고자 우선 프로그래머스 문제부터 도전했다. 해당 문제를 풀 때, 그리디 방식으로 푸는 느낌이었다. 우선 알아볼 수 없는 숫자 0개를 제외하고 정답과 민수가찍은 번호가 공통인 숫자들 개수가 가장 최저 ..
[인프런] 회장뽑기 문제설명 월드컵 축구의 응원을 위한 모임에서 회장을 선출하려고 한다. 이 모임은 만들어진지 얼마 되지 않았기 때문에 회원 사이에 서로 모르는 사람도 있지만, 몇 사람을 통하면 서로 모두 알 수 있다. 각 회원은 다른 회원들과 가까운 정도에 따라 점수를 받게 된다. 예를 들어, 어느 회원이 다른 모든 회원과 친구이면 이 회원의 점수는 1점이다. 어느 회원의 점수가 2점이면, 다른 모든 회원이 친구이거나 친구의 친구임을 뜻한다. 또, 어느 회원의 점수가 3점이면, 다른 모든 회원이 친구이거나, 친구의 친구이거나, 친구의 친구의 친구임을 말한다. 4점, 5점도 같은 방법으로 정해진다. 각 회원의 점수를 정할 때 주의할 점은 어떤 두 회원이 친구 사이이면서 동시에 친구의 친구사이이면, 이 두사람은 친구사이라고 ..
[인프런] 최대점수 구하기 문제설명 이번 정보올림피아드 대회에서 좋은 성적을 내기 위해 현수는 선생님이 주신 N개의 문제를 풀려고 한다. 각 문제는 그것을 풀었을 때 얻는 점수와 푸는 데 걸리는 시간이 주어지게 된다. 제한시간 M안에 N개의 문제 중 최대점수를 얻을 수 있도록 해야 한다.(해당 문제는 해당 시간이 걸리면 푸는 걸로 간주한다. 단, 한 유형당 한 개만 풀 수 있다.) 입력조건 첫 줄에 문제 개수 N(1
[인프런] 동전교환 문제설명 다음과 같이 여러 단위의 동전들이 주어질 때 거스름돈을 가장 적은 수의 동전으로 교환해주려면 어떻게 주면 되는가? 단, 각 단위의 동전은 무한정 사용할 수 있다. 만약 3개의 동전인 1원, 2원, 5원이 주어졌다고할 때, 15원을 만들 수 있는 가장 적은 수의 동전 개수는 3개이다.(5원 5원 5원) 입력조건 첫 줄에는 동전의 종류개수 N(1
[인프런] 가방문제 문제설명 최고 17kg의 무게를 저장할 수 있는 가방이 있다. 그리고 각각 3kg, 4kg, 7kg, 8kg, 9kg의 무게를 가진 5종류의 보석이 있다. 이 보석들의 가치는 각각 4, 5, 10, 11, 13이다. 이 보석을 가방에 담는데 17kg을 넘지 않으면서 최대의 가치가 되도록 하려면 어떻게 담아야 하는가? 각 종류 별 보석의 개수는 무한히 많아서 한 종류의 보석을 여러 번 가방에 담을 수 있다. 입력조건 첫 줄은 보석 종류의 개수와 가방에 담을 수 있는 무게의 한계값이 주어진다. 둘째 줄부터 각 보석의 무게와 가치가 주어진다. 가방의 최대 무게는 1000kg을 넘지 않는다. 보석의 개수는 30개 이내이다. 출력조건 첫 줄에 가방에 담을 수 있는 보석의 최대가치를 출력한다. 사고과정 냅색 알고리..
[인프런] 알리바바와 40인의 도둑 문제설명 알이바바는 40인의 도둑으로부터 금화를 훔쳐 도망치고 있다. 알리바바는 도망치는 길에 평소에 잘 가지 않던 계곡의 돌다리로 도망가고자 한다. 계곡의 돌다리는 N by N개의 돌들로 구성되어 있다. 각 돌다리들은 높이가 서로 다르다. 해당 돌다리를 건널 때 돌의 높이 만큼 에너지가 소비된다. 이동은 최단거리 이동을 한다. 즉, 현재 지점에서 오른쪽 또는 아래쪽으로만 이동해야 한다. N by N의 계곡의 돌다리 격자정보가 주어지면 (1, 1) 격자에서 (N, N)까지 가는데 드는 에너지의 최소량을 구하는 프로그램을 작성해라. 만약 N=3 이고, 계곡의 돌다리 격자 정보가 다음과 같다면 (1, 1) 좌표에서 (3, 3) 좌표까지 가는데 드는 최소 에너지는 14이다. 입력조건 첫 줄에는 자연수 N(1 ..
[인프런] 가장 높은 탑 쌓기 문제설명 밑면이 정사각형인 직육면체 벽돌들을 사용해 탑을 쌓고자 한다. 탑은 벽돌을 한 개씩 아래에서 위로 쌓으면서 만들어 간다. 아래의 조건을 만족하면서 가장 높은 탑을 쌓을 수 있는 프로그램을 작성해라. 조건1 : 벽돌은 회전시킬 수 없다. 즉, 옆면(높이)을 밑면으로 사용할 수 없다. 조건2 : 밑면의 넓이가 같은 벽돌은 없으며, 무게도 같은 벽돌은 없다. 조건3 : 벽돌들의 높이는 같을 수도 있다. 조건4 : 탑을 쌓을 때 밑면이 좁은 벽돌 위에 밑면이 넓은 벽돌은 놓을 수 없다. 조건5 : 무게가 무거운 벽돌을 무게가 가벼운 벽돌 위에 놓을 수 없다. 입력조건 입력 파일의 첫째 줄에는 입력될 벽돌의 수가 주어진다. 입력으로 주어지는 벽돌의 수는 최대 100개이다. 둘째 줄부터는 각 줄에 한 개의..
[인프런] 최대 선 연결하기 문제설명 왼쪽의 번호와 오른쪽의 번호가 있는 그림에서 같은 번호끼리 선으로 연결하려고 한다. 왼쪽번호는 무조건 위에서부터 차례로 1부터 N까지 오름차순으로 나열되어 있다. 오른쪽의 번호 정보가 위부터 아래 순서로 주어지면 서로 선이 겹치지 않고 최대 몇 개의 선을 연결할 수 있는지 구하라 위 그림은 오른쪽 번호 정보가 4, 1, 2, 3, 9, 8. 5, 6, 10, 8로 입력되었을 때 선이 서로 겹치지 않고 연결할 수 있는 최대 선을 개수 6으로 구한 경우이다. 입력조건 첫 줄에 자연수 N(1
[인프런] 피자 배달 거리 문제설명 N by N 크기의 도시지도가 있다. 도시지도는 1 by 1 크기의 격자칸으로 이루어져 있다. 각 격자칸에는 0은 빈칸, 1은 집, 2는 피자집으로 표현된다. 각 격자칸은 좌표(행번호, 열번호)로 표현된다. 행,열 번호 모두 1부터 N번까지 이다. 도시에는 각 집마다 '피자배달거리'가 있는데, 각 집의 피자배달거리는 해당 집과 도시에 존재하는 피자집들과의 거리 중 최솟값을 해당 집의 '피자배달거리'라고 한다. 집과 피자집의 피자배달거리는 $|x_1 -x_2| + |y_1 - y_2| $이다. 최근 도시가 불경기에 접어들어 우후죽순 생겼던 피자집들이 파산하고 있다. 도시 시장은 도시에 있는 피자집 중 M개만 살리고 나머지는 보조금을 주고 폐업시키려고 한다. 시장은 살리고자 하는 피자집 M개를 선택..
[인프런] 사다리 타기 문제설명 현수와 친구들은 과자를 사먹기 위해 사다리 타기를 한다. 사다리 표현은 2차원 배열로 되어 있으며, 0은 평면을 의미하고, 사다리는 1로 표현한다. 현수는 특정 도착지점으로 도착하기 위해서는 몇 번째 열에서 출발해야 하는지 알고 싶다. 특정 도착지점은 2로 표시된다. 주어지는 지도의 크기는 10 by 10이다. 입력조건 10 by 10의 사다리 지도가 주어진다. 출력조건 출발지 열 번호를 출력한다. 사고과정 스스로 풀 때 위에서 출발해야 한다는 것 떄문에 0행의 모든 열에서 DFS 탐색을 수행하면서 마지막 행에서 도착지점이면 출력하도록 했다. 그런데 이렇게 구현하려 하니 방문 체크용 테이블을 구현하는 데 살짝 애를 먹었따.. 결국 구현은 했다. 풀이를 보니, 역발상으로 도착지점에서 역으로 올라갔..
[인프런] 토마토 문제설명 현수의 토마토 농장에서는 토마토를 보관하는 큰 창고를 가지고 있ㅏ. 토마토는 아래의 그림과 같이 격자 모양 상자의 칸에 하나씩 넣어서 창고에 보관한다. 창고에 보관되는 토마토들 중에는 잘 익은 것도 있지만, 아직 익지 않은 토마토들도 있을 수 있다. 보관 후 하루가 지나면, 익은 토마토들의 인접한 곳에 있는 익지 않은 토마토들은 익은 토마토의 영향을 받아 익게 된다. 하나의 토마토의 인접한 곳은 왼쪽, 오른쪽, 앞, 뒤 네 방향에 있는 토마토를 의미한다. 대각선 방향에 있는 토마토들에게는 영향을 주지 못하며, 토마토가 혼자 저절로 익는 경우는 없다고 가정한다. 현수는 창고에 보관된 토마토들이 며칠이 지나면 다 익게 되는지, 그 최소 일수를 알고 싶어 한다. 토마토를 창고에 보관하는 격자모양의 상..

티스토리툴바