분류 전체보기354

• [백준] 1439번: 뒤집기 - 파이썬(python) 문제 다솜이는 0과 1로만 이루어진 문자열 S를 가지고 있다. 다솜이는 이 문자열 S에 있는 모든 숫자를 전부 같게 만들려고 한다. 다솜이가 할 수 있는 행동은 S에서 연속된 하나 이상의 숫자를 잡고 모두 뒤집는 것이다. 뒤집는 것은 1을 0으로, 0을 1로 바꾸는 것을 의미한다. 예를 들어 S=0001100 일 때, 전체를 뒤집으면 1110011이 된다. 4번째 문자부터 5번째 문자까지 뒤집으면 1111111이 되어서 2번 만에 모두 같은 숫자로 만들 수 있다. 하지만, 처음부터 4번째 문자부터 5번째 문자까지 문자를 뒤집으면 한 번에 0000000이 되어서 1번 만에 모두 같은 숫자로 만들 수 있다. 문자열 S가 주어졌을 때, 다솜이가 해야하는 행동의 최소 횟수를 출력하시오. 입력 첫째 줄에 문자열 .. 알고리즘/그리디 2022. 9. 29.

• [이것이 코딩테스트다] 곱하기 혹은 더하기 - 파이썬(python) 문제 각 자리가 숫자(0부터 9)로만 이루어진 문자열 S가 주어졌을 때, 왼쪽부터 오른쪽으로 하나씩 모든 숫자를 확인하며 숫자 사이에 'X' 혹은 '+' 연산자를 넣어 결과적으로 만들어질 수 있는 가장 큰 수를 구하는 프로그램을 작성하세요. 단, +보다 X를 먼저 계산하는 일반적인 방식과는 달리, 모든 연산은 왼쪽에서부터 순서대로 이루어진다고 가정합니다. 예를 들어 02984라는 문자열이 주어지면, 만들어질 수 있는 가장 큰 수는 (((( 0 + 2 ) x 9) x 8) x 4) = 576 입니다. 또한, 만들어질 수 있는 가장 큰 수는 항상 20억 이하의 정수가 되도록 입력이 주어집니다. 입력 조건 첫째 줄에 여러 개의 숫자로 구성된 하나의 문자열 S가 주어집니다. (1 알고리즘/그리디 2022. 9. 29.

• [이것이 코딩테스트다] 모험가 길드 - 파이썬(python) 문제 한 마을에 모험가가 N명 있습니다. 모험가 길드에서는 N명의 모험가를 대상으로 '공포도'를 측정했는데, '공포도'가 높은 모험가는 쉽게 공포를 느껴 위험 상황에서 제대로 대처할 능력이 떨어집니다. 모험가 길드장인 동빈이는 모험가 그룹을 안전하게 구성하고자 공포도가 X인 모험가는 반드시 X명 이상으로 구성한 모험가 그룹에 참여해야 여행을 떠날 수 있도록 규정했습니다. 동빈이는 최대 몇개의 모험가 그룹을 만들 수 있는지 궁금합니다. 동빈이를 위해 N명의 모험가에 대한 정보가 주어졌을 때, 여행을 떠날 수 있는 그룹 수의 최댓값을 구하는 프로그램을 작성하세요. 예를 들어 N=5이고, 각 모험가의 공포도가 다음과 같다고 가정합시다. 2 3 1 2 2 이때 그룹 1에 공포도가 1, 2, 3인 모험가를 한 명.. 알고리즘/그리디 2022. 9. 29.

• 

  [프로그래머스] 약수의 개수와 덧셈 - 파이썬(python) 나의 풀이 def solution(left, right): answer =0 for i in range(left, right+1): if i**0.5 == int(i**0.5) : answer -= i else : answer += i return answer 어떤 수가 제곱수라면, 항상 약수의 개수는 홀수가 된다. 왜냐하면, 약수는 항상 짝을 곱했을 때 해당 숫자가 되는데, 제곱근의 경우 자기 자신과 곱해야지만 해당 숫자가 되기 때문이다. 알고리즘/이것저것 2022. 9. 26.

• 

  [프로그래머스] 키패드 누르기 - 파이썬(python) 문제 설명 스마트폰 전화 키패드의 각 칸에 다음과 같이 숫자들이 적혀 있습니다. 이 전화 키패드에서 왼손과 오른손의 엄지손가락만을 이용해서 숫자만을 입력하려고 합니다. 맨 처음 왼손 엄지손가락은 * 키패드에 오른손 엄지손가락은 # 키패드 위치에서 시작하며, 엄지손가락을 사용하는 규칙은 다음과 같습니다. 엄지손가락은 상하좌우 4가지 방향으로만 이동할 수 있으며 키패드 이동 한 칸은 거리로 1에 해당합니다. 왼쪽 열의 3개의 숫자 1, 4, 7을 입력할 때는 왼손 엄지손가락을 사용합니다. 오른쪽 열의 3개의 숫자 3, 6, 9를 입력할 때는 오른손 엄지손가락을 사용합니다. 가운데 열의 4개의 숫자 2, 5, 8, 0을 입력할 때는 두 엄지손가락의 현재 키패드의 위치에서 더 가까운 엄지손가락을 사용합니다. 4.. 알고리즘/이것저것 2022. 9. 26.

• 

  [프로그래머스] 크레인 인형뽑기 게임 문제 설명 게임개발자인 "죠르디"는 크레인 인형뽑기 기계를 모바일 게임으로 만들려고 합니다. "죠르디"는 게임의 재미를 높이기 위해 화면 구성과 규칙을 다음과 같이 게임 로직에 반영하려고 합니다. 게임 화면은 "1 x 1" 크기의 칸들로 이루어진 "N x N" 크기의 정사각 격자이며 위쪽에는 크레인이 있고 오른쪽에는 바구니가 있습니다. (위 그림은 "5 x 5" 크기의 예시입니다). 각 격자 칸에는 다양한 인형이 들어 있으며 인형이 없는 칸은 빈칸입니다. 모든 인형은 "1 x 1" 크기의 격자 한 칸을 차지하며 격자의 가장 아래 칸부터 차곡차곡 쌓여 있습니다. 게임 사용자는 크레인을 좌우로 움직여서 멈춘 위치에서 가장 위에 있는 인형을 집어 올릴 수 있습니다. 집어 올린 인형은 바구니에 쌓이게 되는 데,.. 알고리즘/이것저것 2022. 9. 26.

• 

  [프로그래머스] 신규 아이디 추천 - 파이썬(python) 문제 설명 카카오에 입사한 신입 개발자 네오는 "카카오계정개발팀"에 배치되어, 카카오 서비스에 가입하는 유저들의 아이디를 생성하는 업무를 담당하게 되었습니다. "네오"에게 주어진 첫 업무는 새로 가입하는 유저들이 카카오 아이디 규칙에 맞지 않는 아이디를 입력했을 때, 입력된 아이디와 유사하면서 규칙에 맞는 아이디를 추천해주는 프로그램을 개발하는 것입니다. 다음은 카카오 아이디의 규칙입니다. 아이디의 길이는 3자 이상 15자 이하여야 합니다. 아이디는 알파벳 소문자, 숫자, 빼기(-), 밑줄(_), 마침표(.) 문자만 사용할 수 있습니다. 단, 마침표(.)는 처음과 끝에 사용할 수 없으며 또한 연속으로 사용할 수 없습니다. "네오"는 다음과 같이 7단계의 순차적인 처리 과정을 통해 신규 유저가 입력한 아이.. 알고리즘/이것저것 2022. 9. 25.

• [프로그래머스] 신고 결과 받기 - 파이썬(python) 문제 설명 신입사원 무지는 게시판 불량 이용자를 신고하고 처리 결과를 메일로 발송하는 시스템을 개발하려 합니다. 무지가 개발하려는 시스템은 다음과 같습니다. 각 유저는 한 번에 한 명의 유저를 신고할 수 있습니다. 신고 횟수에 제한은 없습니다. 서로 다른 유저를 계속해서 신고할 수 있습니다. 한 유저를 여러 번 신고할 수도 있지만, 동일한 유저에 대한 신고 횟수는 1회로 처리됩니다. k번 이상 신고된 유저는 게시판 이용이 정지되며, 해당 유저를 신고한 모든 유저에게 정지 사실을 메일로 발송합니다. 유저가 신고한 모든 내용을 취합하여 마지막에 한꺼번에 게시판 이용 정지를 시키면서 정지 메일을 발송합니다. 다음은 전체 유저 목록이 ["muzi", "frodo", "apeach", "neo"]이고, k = 2.. 알고리즘/이것저것 2022. 9. 25.

• 

  [프로그래머스] 순위 - 파이썬(python) 나의 풀이 from collections import deque def find_person(winner, loser, node) : q = deque() visited = [False] * (len(winner)+1) for i in winner[node] : q.append(i) while q : x = q.popleft() for i in winner[x] : if not visited[i] : # 아직 탐색하지 않은 선수라면 visited[i] = True winner[node].add(i) # 내가 이길 수 있는 사람에 i를 추가 loser[i].add(node) # i가 지는 사람에 나를 추가 q.append(i) def solution(n, results): winner = [set([]) .. 알고리즘/Graph 그래프 2022. 9. 25.

• 

  [프로그래머스] 가장 먼 노드 - 파이썬(python) 나의 풀이 from collections import deque def solution(n, edge): visited = [-1] * (n+1) graph = [[] for _ in range(n+1)] q = deque() for x,y in edge : graph[x].append(y) graph[y].append(x) q.append(1) visited[1] = 0 while q : node = q.popleft() for i in graph[node] : if visited[i] == -1 : visited[i] = visited[node] + 1 q.append(i) max_cnt = max(visited) return visited.count(max_cnt) BFS 로 푼 문제이다. 1번 노.. 알고리즘/Graph 그래프 2022. 9. 25.

• 

  [프로그래머스] 징검다리 - 파이썬(python) 도저히 이분탐색으로 푸는 방법을 생각해내지 못해, 다른 분들의 풀이를 참고하여 아이디어를 얻은 채, 다시 코드를 작성하였다. 풀이 def solution(distance, rocks, n): answer = 0 start, end = 0, distance rocks.append(distance) # 맨 뒤 거리도 계산할 수 있도록 한다 rocks.sort() # 바위 정렬 #이분 탐색 while start 바위 간격의 최솟값 del_stones = 0 # 제거한 돌 개수 pre_stone = 0 # 기준이되는 돌(시작지점) min_dis = distance for rock in rocks: dis = rock - pre_stone # 현재 바위 - 이전 바위 사이 간격 if dis < mid: # 돌사이.. 알고리즘/이분탐색 2022. 9. 24.

• 

  [프로그래머스] 입국심사 - 파이썬(python) 나의 풀이 def binarySearch(left, right, n, times): answer = right while left = n : answer = min(answer, mid); right = mid - 1 else : left = mid + 1 return answer def solution(n, times): min_time = 0 max_time = max(times) * n answer = binarySearch(min_time, max_time, n, times) return answer 이분탐색은 탐색하는데 걸리는 시간이 O(log N) 이기 때문에, 탐색해야 하는 input 이 아주 큰 숫자일 때 사용하기 좋다. 따라서, 위 문제에서도 심사를 하는데 걸리는 시간을 기준으로 이분탐색.. 알고리즘/이분탐색 2022. 9. 24.