본문 바로가기
728x90
반응형

Study134

[프로그래머스][DFS] 여행경로(201008) 1. 문제 설명 programmers.co.kr/learn/courses/30/lessons/43164 코딩테스트 연습 - 여행경로 [[ICN, SFO], [ICN, ATL], [SFO, ATL], [ATL, ICN], [ATL,SFO]] [ICN, ATL, ICN, SFO, ATL, SFO] programmers.co.kr 1. 문제 설명 문제 설명 버스정류장 N개가 있습니다. 각 정류장에는 1번부터 N번까지의 번호가 매겨져 있습니다. 2차원 배열로 주어진 정류장 표지판(signs)에는 A번 정류장에서 B번 정류장으로 가는 버스가 있다면 1, 없다면 0으로 표시되어 있습니다. 예를 들어, 3개의 버스정류장이 있을 때 로 표시된 정류장 표지판이 주어진다면, 1번 정류장에서 2번 정류장으로 갈 수 있습니다.. 2020. 10. 8.
[프로그래머스][DFS] 여행경로(201008) 1. 문제 설명 programmers.co.kr/learn/courses/30/lessons/43164 코딩테스트 연습 - 여행경로 [[ICN, SFO], [ICN, ATL], [SFO, ATL], [ATL, ICN], [ATL,SFO]] [ICN, ATL, ICN, SFO, ATL, SFO] programmers.co.kr 1. 문제 설명 문제 설명 버스정류장 N개가 있습니다. 각 정류장에는 1번부터 N번까지의 번호가 매겨져 있습니다. 2차원 배열로 주어진 정류장 표지판(signs)에는 A번 정류장에서 B번 정류장으로 가는 버스가 있다면 1, 없다면 0으로 표시되어 있습니다. 예를 들어, 3개의 버스정류장이 있을 때 로 표시된 정류장 표지판이 주어진다면, 1번 정류장에서 2번 정류장으로 갈 수 있습니다.. 2020. 10. 8.
[프로그래머스][DFS] N-queen (201008) 백준과 프로그래머스 공통으로 있는 문제이며 전형적인 백트레킹 DFS 문제이다. [ 백트래킹 DFS 문제는 뭔가 ? ] idea-sketch.tistory.com/29 [알고리즘] 되추적(Backtracking)을 알아보자. 오늘의 주제는 되추적(Backtracking) 이다. 저번 포스팅인 깊이우선탐색(Depth-First Search)과 넓이우선탐색(Breath-First Search)의 몸풀기를 거치고 최단경로(Shortest Path) 알고리즘에 들어가는 첫 걸음이라.. idea-sketch.tistory.com [ 프로그래머스 풀이 ] 1. 문제 설명 핵심 * [퀸 조건] 같은 행 렬에 대각선에 위치해서는 안된다. * 첫 행부터 각 행마다 조건에 맞게 설치해보고 마지막 행까지 설치하기 전에 n 개.. 2020. 10. 8.
[프로그래머스] [BinarySearch] 가로등 (201008) 1. 문제 설명 본 문제는 두 가지 방법으로 풀 수 있습니다. PR을 올리실 때에는 두 방법을 모두 올려주세요. 그리디를 이용해 푸는 방법 - O(N) 소요(이는 sorting 에 들어가는 시간복잡도는 제외한 수치임) 이진 탐색을 이용해 푸는 방법 - O(NlogN) 소요 이진 탐색이 무엇인지 모르겠다면? 앞선 collab 노트를 참고해보세요! 서울시에 일직선 모양의 새로운 도로가 생겼습니다. 새로운 도로의 전체 길이는 l이고 도로에는 총 n개의 가로등이 세워졌습니다. 이 도로의 모든 가로등에 전구를 사서 달려고 합니다. 전구를 선택하는 기준은 다음과 같습니다. 전구는 길의 좌측, 우측 방향으로 각각 d 길이만큼 길을 밝힐 수 있고, d는 자연수입니다. 모든 가로등에는 같은 종류(d 값이 같은)의 전구를.. 2020. 10. 8.
[프로그래머스][queue/BFS] FloodFill 1. 문제 설명 2. 풀이 0) 설명 핵심은 매트릭스를 탐색하는 과정에서 같은 숫자가 가세로에 연이어 있으면 해당 뭉탱이를 하나로 카운트하고, 아니면 각각 카운트하는 함수를 짜는것 ! 여기서 뭉탱이를 하나로 --> 부분에서 BFS 가 활용된다. 1) BFS start point 에서 가세로를 탐색했을 때, 같은 색깔이 나오면, 해당 point를 다음 탐색 범위로 지정하고 재탐색 또같은 색깔이 있는지 확인 이렇게 애니팡처럼 같은 색깔 쭉쭉 탐색한뒤에 어느순간 끝나면, 1로 반환해준다. 가령 이 과정에서 3개의 point를 찾았다면, 이 뭉탱이는 1로 반환되어버림 (3이 아님) 2) 그리고 다시 새로운 start point 로 탐색한다. 말 설명이 더 어려운거 같으니 코드로... 1) 첫번째 시도 - 답은 .. 2020. 10. 8.
[프로그래머스][queue/BFS] 전염병 1. 문제 설명 https://huidea.tistory.com/93 [프로그래머스][queue/BFS] FloodFill (200906) 1. 문제 설명 2. 풀이 0) 설명 핵심은 매트릭스를 탐색하는 과정에서 같은 숫자가 가세로에 연이어 있으면 해당 뭉탱이를 하나로 카운트하고, 아니면 각각 카운트하는 함수를 짜는것 ! 여기서 뭉 huidea.tistory.com --> 앞의 Floodfill 과 거의 유사한 패턴이다. queue, BFS 로 너비 우선 탐색을 진행하는 것. 백신 칸을 제외한 모든 칸이 점염되기까지 소요되는 시간 계산 (루프문 +=1) 만약 전염이 막힌 상황이라면 -1 ** 유의할 점은 입력 형태가 1index 라서 매트릭스 넣고 뺄때 주의해야함 2. 풀이 om collections i.. 2020. 10. 8.
[프로그래머스] [hash] 방문길이 python (201006) programmers.co.kr/learn/courses/30/lessons/49994 코딩테스트 연습 - 방문 길이 programmers.co.kr 1. 문제 설명 게임 캐릭터를 4가지 명령어를 통해 움직이려 합니다. 명령어는 다음과 같습니다. U: 위쪽으로 한 칸 가기 D: 아래쪽으로 한 칸 가기 R: 오른쪽으로 한 칸 가기 L: 왼쪽으로 한 칸 가기 캐릭터는 좌표평면의 (0, 0) 위치에서 시작합니다. 좌표평면의 경계는 왼쪽 위(-5, 5), 왼쪽 아래(-5, -5), 오른쪽 위(5, 5), 오른쪽 아래(5, -5)로 이루어져 있습니다. 예를 들어, ULURRDLLU로 명령했다면 1번 명령어부터 7번 명령어까지 다음과 같이 움직입니다. 8번 명령어부터 9번 명령어까지 다음과 같이 움직입니다. 이때,.. 2020. 10. 6.
[프로그래머스][heap] 게임아이템 python (201005) 1. 문제 설명 2. 풀이 1) 공격력이 쎈 순으로 정렬 - 실패 import heapq def solution(healths, items): # 플레이어 체력 오름차순으로 정 healths.sort() # 아이템 리스트 딕셔너리로 만들어두기 item_id_dict = {one_item[0] : idx+1 for idx, one_item in enumerate(items)} # print(item_id_dict) items.sort(key = lambda x : x[0]) # 공격력이 쎈 순으로 정렬 # print(items) result_list = [] str_player = healths.pop() # 가장 공격력이 쎈 플레이어 for now_item in items: # print(now_item.. 2020. 10. 5.
[백준] 스타트와링크 python (201004) 1. 문제 www.acmicpc.net/problem/14889 14889번: 스타트와 링크 예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다. www.acmicpc.net 2. 풀이 import sys from itertools import permutations, combinations num = int(sys.stdin.readline()) skill_matrix = [] for idx in range(num): skill_matrix.append(list(map(int, sys.stdin.readline().split()))) players = list(range(num)) team_.. 2020. 10. 4.
[백준] 톱니바퀴 python (201004) 1. 문제 www.acmicpc.net/problem/14891 14891번: 톱니바퀴 첫째 줄에 1번 톱니바퀴의 상태, 둘째 줄에 2번 톱니바퀴의 상태, 셋째 줄에 3번 톱니바퀴의 상태, 넷째 줄에 4번 톱니바퀴의 상태가 주어진다. 상태는 8개의 정수로 이루어져 있고, 12시방향부터 � www.acmicpc.net 2. 풀이 import sys import collections wheels = [] turns = [] def turnLeft(i, d): if i 3: return if wheels[i][.. 2020. 10. 4.
728x90
반응형

티스토리툴바