알고리즘(18)
-
[Python] 프로그래머스 Lv.2 과제 진행하기 풀이 및 해석 / 스택을 사용한 알고리즘
문제 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀기 전 생각하기 멈춰둔 과제가 여러 개일 경우, 가장 최근에 멈춘 과제부터 시작합니다 이걸 보고서 딱 아 얘는 stack을 사용해야하는구나 생각했다 멈춘 과제들을 stack에 넣고 후입선출로 마지막에 넣은 과제를 반복문으로 pop()하여 answer에 append 하면되지 않는가... 생각했지만 너무 너무 코드가 복잡해지고... 문법오류에 시달리고 내가 짠 코드가 뭔지도 까먹는 지경에 이르렀다 아직 코테 감자인 내가 이걸 어찌 시간 안에 어떻게 다 짜 하면서 울다 해당 블로그의 글을 찾았다.... 나는..
2024.02.09 -
[Python]🥇 15686번 치킨 배달 / 조합과 3중 for문을 이용한 풀이 및 문제 해설
예제 입력 1 5 3 0 0 1 0 0 0 0 2 0 1 0 1 2 0 0 0 0 1 0 0 0 0 0 0 2 예제 출력 1 5 예제 입력 2 5 2 0 2 0 1 0 1 0 1 0 0 0 0 0 0 0 2 0 0 1 1 2 2 0 1 2 예제 출력 2 10 예제 입력 3 5 1 1 2 0 0 0 1 2 0 0 0 1 2 0 0 0 1 2 0 0 0 1 2 0 0 0 예제 출력 3 11 문제 해석 치킨집을 m개 골랐을 때, 각 집(1)에서 가장 가까운 치킨거리를 찾고 그걸 모두 더해라! 그 중 가장 작은 값을 골라라 즉, 1에서 갈 수 있는 가장 가까운 2와의 거리를 찾고 그걸 모두 합하는 구현 문제! 또한 문제 범위가 작고, 그 중 m개를 선택한다면 조합을 떠올리자! 치킨집의 위치가 (x1, y1)이고..
2024.02.07 -
🥈백준 1966 프린터 큐 python 풀이 / 딕셔너리 큐를 사용한 풀이
문제 여러분도 알다시피 여러분의 프린터 기기는 여러분이 인쇄하고자 하는 문서를 인쇄 명령을 받은 ‘순서대로’, 즉 먼저 요청된 것을 먼저 인쇄한다. 여러 개의 문서가 쌓인다면 Queue 자료구조에 쌓여서 FIFO - First In First Out - 에 따라 인쇄가 되게 된다. 하지만 상근이는 새로운 프린터기 내부 소프트웨어를 개발하였는데, 이 프린터기는 다음과 같은 조건에 따라 인쇄를 하게 된다. 현재 Queue의 가장 앞에 있는 문서의 ‘중요도’를 확인한다. 나머지 문서들 중 현재 문서보다 중요도가 높은 문서가 하나라도 있다면, 이 문서를 인쇄하지 않고 Queue의 가장 뒤에 재배치 한다. 그렇지 않다면 바로 인쇄를 한다. 예를 들어 Queue에 4개의 문서(A B C D)가 있고, 중요도가 2 ..
2024.01.15 -
[Python] 🥇 백준 7576- 토마토 / BFS 알고리즘 이용하기
예제 입력 1 6 4 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 예제 출력 1 8 예제 입력 2 6 4 0 -1 0 0 0 0 -1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 예제 출력 2 -1 아이디어 생각하기 이 문제는 익은 토마토들의 주위를 확인하며 나아가야하므로 bfs 알고리즘을 사용해야한다 또한 미로 문제와 다르게 시작점이 여러개이므로, 1인 토마토의 위치값을 모두 큐에 넣어준다 로직 순서 (1) 토마토 박스에 토마토 넣어주기 (2) 익은 토마토들의 위치를 q에 넣어주기 🌟🌟🌟출발점이 여러개인 경우 출발점을 모~두 Queue에 미리 넣어야 한다.🌟🌟🌟 (3) bfs 함수 실행 -1 큐에서 익은 토마토들의 위치를 popleft -2 fo..
2023.02.21 -
[Python] 🥈백준 트리의 부모 찾기 - 11725 /DFS 알고리즘
예제 입력 1 7 1 6 6 3 3 5 4 1 2 4 4 7 예제 출력 1 4 6 1 3 1 4 아이디어 생각하기 그래프를 만들고, 방문여부를 체크하는 배열 visited를 선언한다. 루트 v를 dfs() 인수로 넘겨 V와 연결된 다른 노드를 재귀적으로 방문한다. for문으로 그래프를 도는데, 만약 visited[v]가 비어있다면, visited했다는 의미의 True가 아닌, 탐색을 시작한 값 즉, 부모를 넣어준다. 그리고 다시 재귀한다. 결국, dfs를 기존 그대로구현하고, visited에는 방문여부대신, v를 넣어주면 된다! 기존의 로직을 헷갈릴 것 같아서 변수명은 그대로 visited로 냅두고 진행하겠다 원한다면 father, parents 등으로 바꿔보자.... 주의사항 graph = [[0] *..
2023.02.19 -
[Python] 🥈백준 2667 단지 번호붙이기 /DFS를 활용하여 연결요소 구하기
예제 입력 1 7 0110100 0110101 1110101 0000111 0100000 0111110 0111000 예제 출력 1 3 7 8 9 아이디어 생각하기 연결요소 문제는 풀어도 풀어도 뇌리에 안 박혀서 이렇게 블로그를 쓰고자 한다.... 로직순서 변수설명 map: 지도, home: 각각 단지내 집의 수, nums: 각각 단지내 집의 수를 담는 리스트 (1) 단지 지도 생성 (2) dfs 알고리즘을 돌며, ⓐ 범위를 벗어날 때 ⓑ집이 있을 때 ⓒ집이 없을 때 경우를 나눈다. ⓐ ⓒ는 return False (3) ⓑ 집이 있을 때의 경우, home +=1 집을 1개 추가하고 maps[x][y] = 0 #숫자를 세고 0으로 집을 없앰 다시 못 돌게 집을 없애버린다 dfs(x-1,y) #상하좌우 재..
2023.02.19