본문 바로가기

Algorithm

 (175)
[프로그래머스] Lv.2 쿼드압축 후 개수 세기 https://school.programmers.co.kr/learn/courses/30/lessons/68936?language=python3 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 1. 해결방법 생각보다 해결할 수 있는 아이디어가 금방 떠올랐다. 예제1로 생각을 하면 처음에는 큰 사각형을 탐색을 시작하고, 그 다음에는 4등분으로 쪼개져서 탐색을 한다. 이때, (0, 0), (0, 2), (2, 0), (2, 2)가 시작점이 된다. 시작점의 값은 0 또는 1이므로 사각형을 탐색했을 때, 시작점의 값과 다르다면 dfs 백트래킹을 이용해서 다시 한번..
[BOJ] 2580. 스도쿠 https://www.acmicpc.net/problem/2580 2580번: 스도쿠 스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루 www.acmicpc.net 1. 해결방법 전형적인 스도쿠 문제이다. 스도쿠 문제를 해결하는 원리만 알면 쉽게 풀 수 있는 문제인데 python3로 제출하면 시간초과가 나왔다. 그렇기에 pypy3로 제출,,, 2차원 배열에서 인덱스 값이 0에 해당하는 인덱스 위치를 zero라는 리스트레 append한다. dfs 백트래킹을 이용해서 탐색을 해야하는데, 1 ~ 9 까지 for문을 돌고 0인 위치에서 행과 열, 3X3 정사각형에 ..
[BOJ] 1987. 알파벳 https://www.acmicpc.net/problem/1987 1987번: 알파벳 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으 www.acmicpc.net 1. 해결방법 상하좌우를 이동하면서 배열에 넣고 방문 여부 체크를 하도록 했다. 방문 체크를 하기 때문에 중복으로 들어가는 알파벳이 없고, DFS 재귀를 이용해서 계속적으로 그래프를 탐색할 수 있다. 위를 인지하고 완전 탐색을 이용하여 해결하였는데,,, 시간초과가 떠버렸다.... 아마 이유는 리스트에서 append와 pop을 사용한 문제인 것 같았다. 물론 set()를 이용한 add, re..
[BOJ] 2529. 부등호 https://www.acmicpc.net/problem/2529 2529번: 부등호 두 종류의 부등호 기호 ‘’가 k개 나열된 순서열 A가 있다. 우리는 이 부등호 기호 앞뒤에 서로 다른 한 자릿수 숫자를 넣어서 모든 부등호 관계를 만족시키려고 한다. 예를 들어, 제시 www.acmicpc.net 1. 해결방법 완전탐색 백트래킹을 이용하여 문제를 해결하였다. 아이디어는 쉽지만 코드로 옮기는 과정에서 3시간 정도 잡아 먹은 것 같다.. 역시 아직 알고리즘을 더 해야겠다. 각 숫자 0 ~ 9는 하나만 들어가야 하므로, 방문 여부 체크는 반드시 해주어야 하고 첫 번째 숫자는 부등호와 상관없이 s 문자열에 포함되어야 하는 부분을 신경 써주면 된다. 가장 중요한 부분은 부등호에 맞게 큰 값과 작은 값이 들어가야..
[BOJ] 10971. 외판원 순회 2 https://www.acmicpc.net/problem/10971 10971번: 외판원 순회 2 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 10) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j www.acmicpc.net 1. 해결항법 순회라는 조건이 붙었다. 예를 들어 문제의 N이 4라면 시작점에서 부터 순회를 해야하고 4이기 때문에 정사각형의 모형으로 순회를 할 것이다. 이 점을 유의하고 완전탐색 백트래킹 방법으로 하면 된다. 본인도 문제 이해가 어려웠고, 어떻게 순회하면서 재귀를 돌 것인가에 대해서 고민을 엄청 했다. 이에 관련해서는 코드에서 dfs() for문을 ..
[BOJ] 15686. 치킨 배달 https://www.acmicpc.net/problem/15686 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net 1. 해결 방법 완전 탐색 (백트래킹) 문제이다. 본인은 dfs말고 조합으로 접근하였다. 물론 두 가지다 하겠지만 순열, 조합 라이브러리를 사용한 경험이 적다보니 완전 탐색 알고리즘에서 다 사용해볼 예정이다. 접근 방식은 치킨집의 위치와 집의 위치를 각 리스트에 저장한다. 먼저 치킨집을 for문 돌고, 다음으로 집을 for문 돈다. 그 전에 조합을 이용해서 M만큼의 치킨집을 ..
[프로그래머스] Lv.2 소수 찾기 https://school.programmers.co.kr/learn/courses/30/lessons/42839 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 1. 해결 방법 일단 본인은 DFS 방법으로 완전탐색(백트래킹)을 해결하였다. dfs 시작은 "" 빈 문자열을 매개 변수로 재귀를 돌렸고, numbers를 리스트로 만들어서 하나 하나 탐색을 한 후 word + numbers[i]를 매개 변수로 재귀를 돌렸다. 종료 지점은 for문을 이용해서 숫자가 1자리 일때부터 len(numbers) 까지 돌리고 방문 체크도 해주면 모든 경우의 수가 나오게 된..
[프로그래머스] Lv.2 2개 이하로 다른 비트 https://school.programmers.co.kr/learn/courses/30/lessons/77885 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 1. 해결방법 numbers를 for문 돌리서 num이 짝수이면, +1만 해주면 된다. num이 홀수이면, bin[2:]앞에 '0'을 추가하고 rfind() 메서드를 이용하여 0의 인덱스 위치를 구하고 0을 1로 갱신해준다. 그리고 0의 위치에서 +1에 위치한 인덱스 값을 0으로 바꿔준다 2. 정답코드 def solution(numbers): answer = [] for num in numbers..

티스토리툴바