본문 바로가기

알고리즘 & PS69

[Python] 프로그래머스 Lv 3 - 자물쇠와 열쇠(2020 카카오 코테 기출) 2020 카카오 블라인드 채용 코테 기출문제 자물쇠와 열쇠 풀이 어려운 아이디어 보다는 쌩 구현력을 묻는 문제로, 리스트가 왔다갔다 하는 상황이 많아서, 어떻게 대처해야 할지를 잘 고려해야 하는 문제이다. 함수로 잘 쪼개야 한다. 다행히 좌표 장난질은 덜하되, 알고리즘 (1) 일단, 열쇠가 삐져나와도, 구멍에만 정확하게 맞게 끼워주면 된다는 의미는, 열쇠가 바깥으로 벗어날 수 있다는 점이다.따라서, 자물쇠의 판을 넓혀서 양쪽으로 열쇠가 자연스럽게 들어갈 수 있게 해주자. (2) 열쇠를 1번 돌려서 넓게 핀 자물쇠칸 각 칸에 모두 꽂아보고, 안되면 열쇠 돌리고 총 열쇠를 4번 돌려서 다 안되면 실패로 False를 return 해버린다. 이 때, 자물쇠의 첫 칸을 변수로 줘서 다음 번 시도에도 편리하게 넣을.. 2021. 4. 24.
[Python] 프로그래머스 Lv 2 - 최대 용량이 정해진 FIFO 큐 클래스 스택 2개로 큐를 만들 수 있다? 이에 대해서 알아보자. 프로그래머스 Lv 2 최대 용량이 정해진 FIFO 큐 클래스 문제풀이. 풀이 방법 스택 2개를 준비한다. 각각 1번스택, 2번 스택이라고 하자. (1) 삽입의 경우 최대 용량까지만, 1번에 무조건 넣는다. (2) 삭제의 경우 1번의 바닥의 거를 꺼내는데, 이는 다음과 같이 한다. - 바닥까지 모두 다 순차적으로 꺼내서 2번 스택에 넣는다. - 2번 스택의 가장 윗부분은, 1번 스택의 밑부분이다. 2번에서 다시 pop을 한다. - 2번 스택에 남은 거를 모두 1번으로 옮긴다. 다시 돌려놔야 하는걸 잊지말자! 코드 # Stack 2개로 queue를 구현할 수 있다? ㅋㅋ루이지 class MyStack(object): def __init__(self):.. 2021. 4. 24.
[Python] 프로그래머스 Lv 3 - 게임아이템 Heap을 활용하는 또 다른 문제 프로그래머스 Lv 3 게임아이템 풀이 출처 : 프로그래머스 스쿨 알고리즘 우선 포인트는 다음과 같다. (1) 템 어차피 1개 밖에 못 낀다. (2) 남이 못 낀 템, 내가 HP가 충분하면 먹을 수 있다. (3) 그런데 먹을 수 있는 템 중에선 제일 좋은거를 껴야 한다. 따라서 다음 순서대로 푼다. (1) 캐릭의 HP와 item을 정렬한다. (1)-1 이 때, item에는 체력, 공격력, index를 부여하는 새로운 item list를 만든다. enumerate를 활용하자. (1)-2 다중리스트여도 별 조건 없으면 첫 성분의 오름차순 기준으로 정렬된다. 따라서 깎이는 HP를 맨앞에 쓴다. (2) 캐릭별로 한명씩 item 착용을 시도한다. 이제 낮은 hp를 가진 사람은 hp.. 2021. 4. 23.
[Python] 프로그래머스 Lv 3 - 방문 길이 큰 집단에서 데이터를 가져와야 할 때 제발 좀 해시, 해시를 생각해내자고 좀. 프로그래머스 Lv 3 출처 : https://programmers.co.kr/learn/courses/30/lessons/49994 알고리즘 알고리즘은 단순하다, 그저 정말로 방문한 길을 다 저장해버리면 그만이다. 단, 못가는 길을 막아야하므로, 범위에 조건을 걸어야 할 것이다. 그런데, 길이 몇백개인데, 그걸 다 한번의 이동마다 모두 조사는 불가능하므로, dict를 활용한다. 코드 def solution(dirs): # coord를 어떻게 저장 x, y = 0, 0 # 이렇게 dict를 만들어버린다. key값은 중복될수 없다 활용. coord = dict() for cmd in dirs: if cmd == 'U' and y .. 2021. 4. 23.
[Python] 프로그래머스 Lv 3 - N-queen Problem 이놈의 DFS DFS 신나는 노래... DFS의 대표적인 예시 문제인, N-queen proble에 관한 내용이다. 예전에 한번 풀었다가 멘탈이 그대로 날라가고 런했던 문제... 다시 재도전했다. 출처 : programmers.co.kr/learn/courses/30/lessons/12952 문제 개요 N * N 체스판위에 N개의 퀸을 놓는다. 퀸은 가로, 세로, 대각선 즉 8방향을 자유롭게 오갈수 있다. 서로 공격하지 않게 N개의 퀸을 놓는 경우의 수를 구하여라. 알고리즘 설계, 접근 아이디어 사실, 조합론 쪽에서도 연구되고 있는 문제 중 하나로, 이건 컴퓨터로 특정 값까진 다 계산되어있다. 그래서 정말 꼼수를 부린다면 구글링을 해서 값을 조사해서 if문 12개로 클리어 가능하다. 우리는 그런 나쁜 짓.. 2021. 4. 22.
[Python] 프로그래머스 Lv 3 - FloodFill 그놈의 BFS ! DFS ! 제발 좀 익숙해지고 싶다.(1) 프로그래머스 Lv 3 - FloodFill 문제풀이 알고리즘 한 점에서 시작해서 Image의 값이 같은 것을 모두 탐사하고 갈 수 있는 칸이 없으면 들어간 칸을 내역을 모두 돌려주고 return 하고 안 간 칸을 찾아야 한다. BFS를 시전하면 된다. 단계별로 정리하면 다음과 같다. (1) Image 크기 만큼 방문 내역을 만든다. (2) 첫 칸부터 bfs로 탐사를 보낸다. (3) 갈 수 있는 칸들은 모두 queue에 넣는다. 이 때, 이동 가능 검사를 해줘야 한다. 상하, 좌우로 인덱스를 넘어가지 않는지, 방문 한적이 있는데 또가는건 아닌지, 이미지 색이 같은지 4가지를 모두 검사해야 한다. (4) 이미지가 같다면, 더 갈 수 있으므로 que.. 2021. 4. 22.

티스토리툴바