Archive

www.acmicpc.net/problem/1003 1003번: 피보나치 함수 각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다. www.acmicpc.net 풀이 메모이제이션 문제 0, 1의 개수 정보를 글로벌 변수로 선언해 입력값 들어왔을 때 기존에 계산한 정보 있으면 바로 리턴해줌. 그리고 계산정보 없을경우 이전 개수 정보를 기반으로 최소한의 계산만 수행해 시간을 단축 # global 변수로 0, 1 카운트 정보 놔둠 zero = [1, 0] one = [0, 1] def solution(n): # 입력값 n이 이전 정보에 있을 경우 -> 바로 값을 리턴함.(중복계산 방지) if n

www.acmicpc.net/problem/10451 10451번: 순열 사이클 1부터 N까지 정수 N개로 이루어진 순열을 나타내는 방법은 여러 가지가 있다. 예를 들어, 8개의 수로 이루어진 순열 (3, 2, 7, 8, 1, 4, 5, 6)을 배열을 이용해 표현하면 \(\begin{pmatrix} 1 & 2 &3&4&5&6&7&8 \\ 3 www.acmicpc.net 풀이 DFS문제. 처음 시작노드 -> 방문안한노드를 방문 -> 방문한 노드를 마주치면 while문 밖으로 처음 시작노드 = 최종 도착노드일 경우(cycle) count 변수 +1해줌. def solution(): n = int(input()) lst = [0] + list(map(int, input().split())) cnt = 0 vi..

https://programmers.co.kr/learn/courses/30/lessons/42892 코딩테스트 연습 - 길 찾기 게임 [[5,3],[11,5],[13,3],[3,5],[6,1],[1,3],[8,6],[7,2],[2,2]] [[7,4,6,9,1,8,5,2,3],[9,6,5,8,1,4,3,2,7]] programmers.co.kr 풀이 입력으로 [x, y] 좌표 데이터를 원소로 하는 리스트를 받아 조건에 맞게 이진트리를 만든 뒤 전위 순회, 후위 순회했을 때 방문해야할 노드 index리스트를 반환하는 문제 y값이 level이라 먼저 y값으로 내림차순, x값은 오름차순으로 동시에 정렬하면 순차적으로 node를 추가할 수 있음. 전위 순회, 후위 순회는 재귀함수를 사용하면 간단히 구현할 수 있..

https://programmers.co.kr/learn/courses/30/lessons/42893 코딩테스트 연습 - 매칭 점수 매칭 점수 프렌즈 대학교 조교였던 제이지는 허드렛일만 시키는 네오 학과장님의 마수에서 벗어나, 카카오에 입사하게 되었다. 평소에 관심있어하던 검색에 마침 결원이 발생하여, 검색개발팀� programmers.co.kr 풀이 특정 단어 word, html 소스로 구성된 pages를 입력으로 받음. 각 page별로 word에 대한 점수를 부여해야 하는데 다음 과정으로 구함. 본문(body tag)에서 word의 개수를 기본 점수로 정함. 본문은 알파벳을 제외한 다른 문자로 구별가능하고, 대소문자 상관 없이 word와 딱 맞아야함. word = 'abc', body에 'abcd',..

https://www.hackerrank.com/challenges/ctci-connected-cell-in-a-grid/problem DFS: Connected Cell in a Grid | HackerRank Find the largest connected region in a 2D Matrix. www.hackerrank.com 풀이 0과 1로 구성된 grid가 주어지면, 1을 기준으로 한 영역의 최댓값을 구하는 문제. 8가지 방향에 1이 있으면 같은 영역이라 가정.(왼쪽 대각선 위부터 시계방향) visited를 확인하기 위한 matrix 만들고, 방향 정보 리스트 만들고, stack을 사용해 dfs 구현하면 됨. def maxRegion(grid): n = len(grid) m = len(grid..

https://www.hackerrank.com/challenges/ctci-bfs-shortest-reach/problem BFS: Shortest Reach in a Graph | HackerRank Implement a Breadth First Search (BFS). www.hackerrank.com 풀이 그래프와 시작노드가 주어졌을 때 BFS로 다른 노드까지의 depth를 구하는 문제. 도달할 수 없으면 -1 리턴. BFS로 depth를 구할 때, 아래와 같은 순서대로 풀면 됨. 먼저 start_node를 정의(혹은 주어짐). 방문 정보를 저장할 visited 리스트 0으로 초기화. start_node에 대해서는 1로 처리 queue에 start_node 저장. depth는 dictionary를..

https://www.hackerrank.com/challenges/find-the-nearest-clone/problem Find the nearest clone | HackerRank Find the shortest path length between any two nodes with the given condition. www.hackerrank.com 풀이 그래프 정보와 각 노드의 색깔 저보가 주어짐. 특정 색깔을 입력받았을 때 같은 색깔의 다른 노드에 도달할 수 있는 최단 거리를 구하는 문제 먼저 adj_matrix를 만들어주는데, 파이썬의 dictionary를 사용. key : node, value : [인접 노드] 방향이 없기 때문에 graph_from, graph_to에 있는 노드를 번갈아..

https://www.hackerrank.com/challenges/torque-and-development/problem Roads and Libraries | HackerRank Help the ruler of HackerLand determine the cheapest way to give his citizens access to libraries. www.hackerrank.com 풀이 그래프가 주어졌을 때 dfs로 전체 node를 방문하기 위한 경로를 세는 문제 첫 번째로 도서관 짓는 비용 c_lib이 길을 설치하는 비용 c_road보다 작을 경우 각 node에 도서관을 짓는다고 보면 됨. dictionary를 사용해 인접행렬을 구현했고, 방향이 없기 때문에 시작노드, 끝 노드를 각각의 valu..