본문 바로가기

분류 전체보기

(129)
[알고리즘/프로그래머스] 비밀지도 2018 KAKAO BLIND RECRUITMENT > [1차] 비밀지도 코딩테스트 연습 - [1차] 비밀지도 비밀지도 네오는 평소 프로도가 비상금을 숨겨놓는 장소를 알려줄 비밀지도를 손에 넣었다. 그런데 이 비밀지도는 숫자로 암호화되어 있어 위치를 확인하기 위해서는 암호를 해독해야 한다. 다 programmers.co.kr 나의 풀이 - 비트연산자 ㅣ 사용 - 이진수 변환 함수 bin() --> 출력값 0bXXX (str형) - replace 함수 사용 def solution(n, arr1, arr2): answer = [] for i in range(n): bin_str = bin(arr1[i] | arr2[i]).replace('b', '0')[-n:] answer.append(((n-len(bin..
[알고리즘/프로그래머스] 튜플 2019 카카오 개발자 겨울 인턴십 > 튜플 코딩테스트 연습 - 튜플 "{{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 나의 풀이 - replace 함수 사용 - 숫자만 남긴 리스트를 구한 후 각 숫자의 개수를 세어 순서를 맞춰 리스트에 추가해준다. def solution(s): s = s.replace('{', '') s = s.replace('}', '') num_list = list(map(int, s.split(','))) answer = [0] * len(set(num_lis..
[알고리즘/프로그래머스] 숫자 문자열과 영단어 2021 카카오 채용연계형 인턴십 >숫자 문자열과 영단어 코딩테스트 연습 - 숫자 문자열과 영단어 네오와 프로도가 숫자놀이를 하고 있습니다. 네오가 프로도에게 숫자를 건넬 때 일부 자릿수를 영단어로 바꾼 카드를 건네주면 프로도는 원래 숫자를 찾는 게임입니다. 다음은 숫자의 일부 자 programmers.co.kr 나의 풀이 - 너무 복잡하게 풀었다.. 😥 def solution(s): number = ["zero", "one", "two", "three", "four", "five","six" ,"seven","eight","nine"] answer = 0 while s: if '0'
[알고리즘/백준] 11724번 연결 요소의 개수 11724번 연결 요소의 개수 - https://www.acmicpc.net/problem/11724 Python으로 제출하면 시간 초과 / PyPy3로 제출하면 통과 (메모리 197904KB / 시간 868ms) 접근 방법 - BFS로 품 ( queue 사용) - 2644번 촌수계산 문제와 마찬가지로 중첩 리스트로 graph를 만들어주고 visited list를 활용하여 queue에 넣어준다. - sum(visited list) 가 N이 되면 모두 방문했다는 뜻으로 멈춰준다. from collections import deque def bfs(graph, N): visited = [0] * N count = 0 while sum(visited) != N: queue = deque([visited.ind..
[알고리즘/백준] 2644번 촌수계산 2644번 촌수계산 - https://www.acmicpc.net/problem/2644 ( 개인적으로 BFS로 푸는 코드를 생각하기까지 어려웠음 😥 ) 접근 방법 처음에는 BFS_DFS 문제라고 생각하지 못했다. 그래프 문제인 것은 알았는데 조금 복잡하게 구현했다. - 그래프를 dictionary로 만들었다. - num1의 부모 노드를 num1_list에 모두 담아주고 루트노드일 때 멈춘다. - num2도 num1과 마찬가지로 진행하되 num1_list에 들어있는 노드가 나오게 되면 index로 촌수를 계산해준다. def relatives(graph, num1, num2): result = -1 num1_list = [num1] num2_list = [num2] while num1 in graph.ke..
[알고리즘] 다이나믹 프로그래밍(LIS) - 병사 배치하기 출처 : 동빈나 유튜브 - (이코테 2021 강의 몰아보기) 6. 다이나믹 프로그래밍 병사 배치하기 ( 직접 못 풀어서 답안 예시를 공부 ) N명의 병사가 무작위로 나열, 각 병사는 특정한 값의 전투력을 보유 병사를 배치할 때 전투력이 높은 병사가 앞쪽에 오도록 내림차순으로 배치 다시 말해서, 앞쪽에 있는 병사의 전투력이 항상 뒤쪽에 있는 병사보다 높아야 한다. 또한 배치 과정에서는 특정한 위치에 있는 병사를 열외시키는 방법을 이용한다. 그러면서도 남아 있는 병사의 수가 최대가 되도록 하고 싶다. 첫째 줄에 N이 주어진다. (1
[알고리즘] 다이나믹 프로그래밍(동적 계획법) - 2 공부 : 동빈나 유튜브 + 책 실전문제 - 효율적인 화폐 구성 N가지 종류의 화폐가 있다. 이 화폐들의 개수를 최소한으로 이용해서 그 가치의 합이 M원이 되도록 만들기 이때 각 화폐는 몇 개라도 사용할 수 있으며, 사용한 화폐의 구성은 같지만 순서만 다른 것은 같은 경우로 구분 첫째줄에 N, M ( 1
[알고리즘] 다이나믹 프로그래밍(동적 계획법) - 1 공부 : 동빈나 유튜브 + 책 다이나믹 프로그래밍 메모리를 적절히 사용하여 수행 시간 효율성을 비약적으로 향상시키는 방법 - 이미 계산된 결과(작은 문제)는 별도의 메모리 영역에 저장하여 다시 계산하지 않도록 한다. - 구현은 일반적으로 Top-Down(하향식)/Bottom-Up(상향식)으로 구성된다. - Top-Down은 재귀로 / Bottom-Up은 반복문으로 구현 가능 - 다이나믹 프로그래밍의 전형적인 형태는 Bottom-Up 방식 결과 저장용 리스트는 DP 테이블이라고 부른다. - 다이나믹은 자료구조의 동적과 다르게 별다른 의미 없이 사용된 단어 더보기 자료구조에서 동적 할당(Dynamic A..