프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 유형에는 완전탐색이라고 되어 있기하던데 난 다른 방식으로 풀었다.n개의 송전탑이 하나의 트리 형태로 연결되어 있고, 그 중 하나의 전선을 끊어 두 개의 트리로 만든다.그리고 각 트리에서의 원소 개수 차이가 최소가 되는 그 최소값을 구하면 된다. union-find를 통해서 풀었다.반복문을 통해 각 전선을 하나씩 제거하면서 union-find연산을 통해 각 송전탑들이 속하고 있는 트리를 저장한다.그리고 각 경우에 대해, 트리에 속한 송전탑의 개수 차이가 최솟값인 경우를 갱신해서 리턴한다. 풀이 코드from coll..
완전탐색
19_연산자 끼워넣기 14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 happenundo.tistory.com
14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, 곱 www.acmicpc.net itertools 패키지의 permutations 클래스를 활용해서 풀었다. 단, permutations를 사용해서 나올 수 있는 연산자 리스트의 후보를 구할 때, 한 연산자가 2개 이상 들어 있을 경우, 같은 연산자 리스트가 연산자 리스트 후보에 들어 있을 수 있으므로 set으로 바꿔줘서 중복을 없애주는 방식으로 구현했다. 내 풀이 코드 # 14888번: 연산자 끼워넣기 from itertools imp..
14_외벽 점검 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 구현 문 happenundo.tistory.com
프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 구현 문제다. 구현이 쉽지 않다. 내가 코드를 짜면 코드가 너무 복잡해진다. 그래서 풀이를 볼 수 밖에 없었다. 풀이 제한 조건을 봤을 때, weak 리스트와 dist 리스트의 길이가 매우 작으므로 완전 탐색 가능하다. -> 이건 알고 있었음 문제에서 찾고자 하는 것은 "투입해야 하는 친구 수의 최솟값"이다. 이 때 전체 친구의 수(dist의 길이)는 최대 8이므로, 모든 친구를 무작위로 나열하는 모든 순열의 개수를 계산하면 8P8 = 40,320으로 충분히 계산가능하다. -> 이것도 알고 있었음 그러므로 친..
13_치킨 배달 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위 happenundo.tistory.com
12_기둥과 보 설치 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 구현 문 happenundo.tistory.com
15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net 문제 이해는 쉽지만 구현이 까다로웠던 문제다. 완전탐색으로 풀려고하니, 내 구현에서는 4중 for문까지 들어가더라. 4중 for문으로 풀어도 되겠다는 생각이 들었던 이유는 대충 시간복잡도를 계산해보면 1초에 간당간당하게 들어간다고 판단했기 때문이다. 먼저 치킨 집을 최대 m개 뽑는다고 하는데 그래서 combinations를 사용했다. 먼저 전체 맵의 크기 N의 범위는 2
11_뱀 3190번: 뱀 'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난 happenundo.tistory.com
3190번: 뱀 'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 게임 www.acmicpc.net 지렁이가 사과를 먹으면서 크기를 키우는 게임이다. 큐 자료구조를 사용했다. 큐 자료구조에는 2가지를 저장한다. 1. 입력받은 command 2. 뱀의 몸이 위치하고 있는 칸 입력받은 command는 (시간, 방향) 정보를 저장하고 있는데, 왜 큐를 사용했냐면 문제 조건에서 방향 전환 정보는 시간이 증가하는 순서대로 주어진다고 했기 때문이다. 그러므로 큐 자료구조를 사용해서 popleft() 메소드를 통해 다음 방향 전환 정보를 얻을 수 있다. 그리고, 뱀의 몸이 위치하..
