코딩테스트 풀이 (10) 썸네일형 리스트형 [프로그래머스](파이썬)-방문길이-Level3-set사용문제 안녕하세요. 진또배기입니다. 오늘은 프로그래머스의 방문길이 문제에 대해 풀어보는 시간을 가져보겠습니다. 이 문제는 set을 사용하는 문제로 중복을 줄여주어야하기 때문입니다. 그러면, 시작하겠습니다! 1. 문제 소개 -문제링크: programmers.co.kr/learn/courses/30/lessons/49994 코딩테스트 연습 - 방문 길이 programmers.co.kr 2. 슈도코드 앞서 말씀드린 것 처럼 set을 사용하는 문제입니다. 그 이유는 set은 원소를 unique하게 유지해주기 때문인데요. 여기서 A에서 --> B로 가는 것은 == B에서 -->A로 가는 것과 같은 것임을 고려해야합니다. 즉, set을 써서 지난 경로라면 unique하게 집계를 해주어야합니다.(Unique란 중복되지 않는.. [프로그래머스](파이썬)FloodFill-Level3-BFS알고리즘 사용 안녕하세요. 그러면 시작하겠습니다...!!입니다. 오늘은 프로그래머스의 FloodFill문제를 풀어보는 시간을 가져보겠습니다. 이 문제는 전형적인 BFS알고리즘을 사용하는 문제로, Level3에 해당하는 어려운 문제입니다. 하지만 아주 많이 응용되는 문제이니 슈도코드를 토대로 잘 따라오시면 되겠습니다. 그러면 시작하겠습니다! 1. 문제소개 2. 슈도코드 목표: 각 좌표를 하나하나 탐색하면서 효율적인 방법을 고안하자. 0. 좌표를 방문했는지 안했는지 체크리스트 생성-->2차원 배열로 체크해줄거임. -방문했으면 2차원 배열의 원소가 True, 방문안했으면 2차원 배열의 원소가 False. -큐를 이용한 bfs기법 1. (0,0)=> 처음보는 좌표이므로 큐에 넣음 -queue[(0,0)] 2-a. 큐에서 원소.. [프로그래머스](파이썬)-게임아이템-Level3-힙(heap)사용 문제 안녕하세요. 진또배기입니다. 오늘은 프로그래머스의 게임아이템 문제를 풀어보겠습니다. 이 문제는 사실 그냥 List로도 풀 수 있는 문제입니다. 하지만 List를 사용하면 시간복잡도가 증가해 비효율적인 알고리즘입니다. 따라서 제목에 나타낸 것처럼 heap이라는 자료구조를 사용해야 되는데요. 이러한 문제는 응시자가 효율성에 대한 개념이 있는 지 확인하는 문제입니다. 따라서 효율성을 검증하는 문제를 통해 여러분이 기존 방법대로 풀지 않는, 창의적인 지원자라는 것을 어필합시다! 그러면 시작하겠습니다. 1. 문제소개 2. 슈도코드 제가 처음 시도한 방식: 모든 캐릭터의 체력을 리스트에 담고, 배정가능한 아이템을 모두 찾은 후, 모든 배정 가능한 경우의 수를 리스트에 담은 뒤, 가장 높은 공격력을 뽑는다. 즉, 1.. [프로그래머스](파이썬)-이중 우선순위큐-Level2.5-힙,큐 문제 안녕하세요. 진또배기입니다. 오늘은 프로그래머스의 이중 우선순위큐 문제를 풀어보도록 하겠습니다. 음 제 생각에는 이런 문제는 복잡한 알고리즘은 쓰이지 않지만 다양한 스킬들과 2가지의 자료구조가 쓰이기때문에 2.5레벨의 문제라고 생각합니다. 이 정도 난이도의 문제는 현재 한국 대기업에서 가장 어려운 코딩테스트 문제에요. 물론 Level4, Level5의 문제도 있지만 거기까지는 나오지 않는 것 같습니다. (네이버, 카카오, 구글, AWS 등 자체 IT서비스 기업제외-여긴 더 어려운 문제나옴..ㅋㅋ) 그러면 시작하겠습니다! 1. 문제 소개 문제 설명 급한 일을 먼저 처리해주는 서버가 있습니다. 이 서버에 3초에 한 번씩 요청이 들어온다고 할 때, 서버가 각 요청을 처리하는 순서를 알아보려 합니다. 요청은 [.. [프로그래머스]-(파이썬)더맵게-Level2 보호되어 있는 글입니다. [프로그래머스](파이썬)나머지한점-Level2-2가지 방법 문제풀이 안녕하세요.진또배기입니다. 오늘은 프로그래머스에 올라와있는 '나머지 한점'문제를 파이썬을 사용해 2가지 방법으로 풀이를 해보겠습니다. 한 가지는 해시를 이용한 방법, 다른 한 가지는 Counter를 이용한 방법입니다. 1. 문제 소개 문제 설명 선행 스킬이란 어떤 스킬을 배우기 전에 먼저 배워야 하는 스킬을 뜻합니다. 예를 들어 선행 스킬 순서가 라이트닝 볼트 → 스파크 → 썬더일때, 썬더를 배우려면 먼저 스파크를 배워야 하고, 스파크를 배우려면 먼저 라이트닝 볼트를 배워야 합니다. 위 순서에 없는 다른 스킬(힐링 등)은 순서에 상관없이 배울 수 있습니다. 따라서 라이트닝 볼트 → 힐링 → 스파크 → 썬더와 같은 스킬트리는 가능하지만, 썬더 → 스파크나 라이트닝 볼트 → 힐링 → 썬더 → 스파크와 같은 .. [프로그래머스](파이썬)스킬트리2-Level3-큐(Queue), 해시(dict)사용 안녕하세요. 진또배기입니다. 오늘은 파이썬을 사용해 프로그래머스에 올라와있는 '스킬트리2'문제를 이전에 포스팅한 것과 다른 방법으로 풀어보도록 하겠습니다. 1. 문제 소개 문제 링크: programmers.co.kr/learn/courses/30/lessons/49993 코딩테스트 연습 - 스킬트리 programmers.co.kr 2. 슈도코드 스킬의 습득 순서를 저장할 필요가 있을 것 같아 enumerate() 함수를 이용해 인덱스와 스킬 페어로 저장했습니다. 이후 skill_tree의 각 skill에 대해 순회하며 인덱스를 비교하도록 구현했습니다 시간복잡도: 선행스킬 순서 배열(skills_order)의 길이 n과 스킬트리 배열(skill_tree)의 길이 m에 대해 O(n+m) 3. 문제풀이 [프로그래머스](파이썬) 스킬트리-Level2-문자열 안녕하세요. 진또배기입니다. 오늘은 파이썬을 사용해 프로그래머스에 올라와있는 '스킬트리'문제를 풀어보도록 하겠습니다. 1. 문제 소개 문제링크 : programmers.co.kr/learn/courses/30/lessons/49993 코딩테스트 연습 - 스킬트리 programmers.co.kr 선행 스킬이란 어떤 스킬을 배우기 전에 먼저 배워야 하는 스킬을 뜻합니다. 예를 들어 선행 스킬 순서가 스파크 → 라이트닝 볼트 → 썬더일때, 썬더를 배우려면 먼저 라이트닝 볼트를 배워야 하고, 라이트닝 볼트를 배우려면 먼저 스파크를 배워야 합니다. 위 순서에 없는 다른 스킬(힐링 등)은 순서에 상관없이 배울 수 있습니다. 따라서 스파크 → 힐링 → 라이트닝 볼트 → 썬더와 같은 스킬트리는 가능하지만, 썬더 → 스.. [프로그래머스] (파이썬)배상비용최소화-Level2-힙(heap) 자료구조 안녕하세요. 진또배기입니다. 오늘은 파이썬을 사용해 프로그래머스에 올라와있는 '배상비용최소화'문제를 풀어보도록 하겠습니다. 1. 문제 설명 문제 설명 OO 조선소에서는 태풍으로 인한 작업지연으로 수주한 선박들을 기한 내에 완성하지 못할 것이 예상됩니다. 기한 내에 완성하지 못하면 손해 배상을 해야 하므로 남은 일의 작업량을 숫자로 매기고 배상비용을 최소화하는 방법을 찾으려고 합니다. 배상 비용은 각 선박의 완성까지 남은 일의 작업량을 제곱하여 모두 더한 값이 됩니다. 조선소에서는 1시간 동안 남은 일 중 하나를 골라 작업량 1만큼 처리할 수 있습니다. 조선소에서 작업할 수 있는 N 시간과 각 일에 대한 작업량이 담긴 배열(works)이 있을 때 배상 비용을 최소화한 결과를 반환하는 함수를 만들어 주세요... [프로그래머스] (파이썬)올바른 괄호-Level2-스택(Stack)활용 안녕하세요. 진또배기입니다. 오늘은 파이썬을 사용해 프로그래머스에 올라와있는 '올바른 괄호'문제를 풀어보도록 하겠습니다. 1. 문제 programmers.co.kr/learn/courses/30/lessons/12909?language=python3 코딩테스트 연습 - 올바른 괄호 괄호가 바르게 짝지어졌다는 것은 '(' 문자로 열렸으면 반드시 짝지어서 ')' 문자로 닫혀야 한다는 뜻입니다. 예를 들어 "()()" 또는 "(())()" 는 올바른 괄호입니다. ")()(" 또는 "(()(" 는 올바르지 않은 programmers.co.kr 문제설명 괄호가 바르게 짝지어졌다는 것은 '(' 문자로 열렸으면 반드시 짝지어서 ')' 문자로 닫혀야 한다는 뜻입니다. 예를 들어 "()()" 또는 "(())()" 는 올.. 이전 1 다음
