본문 바로가기
728x90
반응형

분류 전체보기150

[백준] 1018번 체스판 다시 칠하기 python (201010) 1. 문제 설명 www.acmicpc.net/problem/1018 1018번: 체스판 다시 칠하기 첫째 줄에 N과 M이 주어진다. N과 M은 8보다 크거나 같고, 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 보드의 각 행의 상태가 주어진다. B는 검은색이며, W는 흰색이다. www.acmicpc.net 2. 풀이 0. 탐색방법은 윈도우를 옮기며 CNN 윈도우 사이즈 만큼 탐색하듯이 해줘야 한다. 여기서 초록색이 움직이는 것 처럼 !!! (빨간색은 무시하세요... CNN 알고리즘에서 긁어온거라..!) 즉 가세로가 8 초과인 경우는 행과 열을 움직여가며 8*8 사이즈 매트릭스 중 규칙에 어긋난 갯수를 구해야한다. 그중 가장 적게 어긋난 갯수를 반환해주는게 문제의 정답 ! 1. WB를 어떻게.. 2020. 10. 10.
[Machine learning] 차원축소, PCA, SVD, LSA, LDA, MF 간단정리 (day1 / 201009) Q. 차원의 저주에 대해 설명해주세요. dimension reduction 기법으로 보통 어떤 것들이 있나요? # 차원의 저주 - Curse of dimension 입력된 데이터의 수보다 데이터의 차원이 더 큰 경우 발생하는 문제를 차원의 저주라 합니다. 가령 입력한 데이터의 양은 100개 인데 각 데이터의 차원은 500인 상황입니다. 우리는 데이터(벡터)가 뿌려진 벡터 공간에서 분류 또는 예측하는 가장 적합한 함수를 찾는게 기계학습, 딥러닝 학습의 목표인데요. 입력한 데이터의 양은 적고, 데이터의 차원이 커지게 된다면 이때 벡터 공간의 차원이 무수히 커지고 데이터는 여기저기 흩뿌려져 있는 상황입니다. 이 흩어진 벡터들을 분류 예측하는 함수의 모형은 복잡해지게 됩니다. 즉, 모델의 복잡도가 증가하고 예측.. 2020. 10. 10.
[프로그래머스][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.
728x90
반응형

티스토리툴바