본문 바로가기

전체 글276

[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.
[Python] 프로그래머스 Lv 3 - 빙고 아싸 빙고! 프로그래머스 Lv 3 빙고 풀이 알고리즘 처음에는, 일단 빙고판을 하나 또 깡으로 복사해서 0으로 모두 채우고, 리스트에 하나씩 있나 검사를 한다음 열이 모두 채워졌나, 행이 모두 채워졌나, 대각선은 되나 이렇게 각각을 검사했다. 어떻게던 풀겠지만 당연히 효율성에서 실패! 따라서 애초에 행과 열, 대각선을 입력 시점에서 모두 검사해야 한다. 이에 따라 행별로 숫자를 기록할때마다 1을 더할 리스트, 열도 1개 만들고, 대각선은 각 방향별로 변수를 미리 만들어둔다. board의 각 칸에 있는 값이 nums에 있는지 검사하면 된다. 근데, 이마저도 그냥 board in nums 를 하는 순간 효율성을 또 통과하지 못한다. 효율성을 위해 nums를 val값 없이, 키 값만 존재해도 dict를 만들어.. 2021. 4. 22.
[Python] 프로그래머스 Lv 3 - 등굣길 프로그래머스 Lv 3 - 등굣길 풀이 출처 : https://programmers.co.kr/learn/courses/30/lessons/42898 알고리즘 우선 길찾기는 기본적으로 순열/조합으로 풀 수 있다. 그런데, 문제는 물 웅덩이가 존재한다는 것과 그것이 몇 개인지 모른다는 것이 가장 큰 문제이다. 따라서 순열/조합의 일반화는 절대 불가능하고, 직접 경우의 수를 컴퓨터가 세 줘야 할 것이다. 여기에서, DP로 풀어야 하는 문제임을 눈치챌 수 있다. 기본적으로 자신의 윗칸까지 온 경우의 수와, 좌측까지 온 경우의 수를 더하면 그 자리까지 가는 경우의 수가 될 것이다. 변수는 물웅덩이인데, 물 웅덩이로는 못 오니까 그 칸은 0으로 센다. 또한, 물웅덩이의 추가 변수가 있다. 가장 윗 줄과 가장 왼쪽 .. 2021. 4. 22.
[Python] 프로그래머스 Lv 3 - 야근 지수 프로그래머스 Lv 3 - 야근지수 풀이 출처 : https://programmers.co.kr/learn/courses/30/lessons/12927 알고리즘 제곱의 특성 상, 큰 값을 더 크게 만드므로, 남은 N시간 동안, 가장 작업량이 많은 거를 1개씩 줄여 나가면 될 것이다. 즉, 계속 최댓값을 찾아줘야 하는 문제이다. 이에 적합한 자료구조는 최대와 최소를 간편하게 찾아주는 heap 자료구조이다. 다행히, Python에는 heapq 형태로 자료구조가 이미 구현되어 있다. 허나, 문제는 heapq는 Min Heap을 기반으로 하고 있다. 이를 Max로 바꾸려면 어떻게 해야 하나.? 자료구조를 Max로 바꿀 생각을 하지 말고, 주어진 배열이 모두 양수이므로, -1을 곱해서 모두 음수로 만들면 Min H.. 2021. 4. 22.

티스토리툴바