운동하는 개발자/알고리즘, 코딩테스트 (40) 썸네일형 리스트형 HackerRank [Implementation] Forming a Magic Square /알고리즘 해커랭크 문제 주소 : www.hackerrank.com/challenges/magic-square-forming/problem 난이도 : Medium 성공률 : 74.83% 문제 : 3x3의 입력된 배열값으로 매직스퀘어(1부터 9까지 한번씩만 사용하여 3x3 크기의 어느 방향의 세 숫자의 합을 구하더라도 15가 되는)로 수정하기 위해 발생하는 비용 구하기 풀이 1. 3x3으로 만들 수 있는 모든 매직스퀘어를 저장해 준다 2. 입력된 배열과 같은 위치(행,열)에 있는 매직스퀘어 8개와 값을 비교한다 3. 차이 값을 누적시킨 후 가장 적은 누적값을 리턴한다 답안 #!/bin/python3 import math import os import random import re import sys # Complete the.. HackerRank [Strings] Two Characters /알고리즘 해커랭크 문제 주소 : https://www.hackerrank.com/challenges/two-characters/problem 난이도 : easy 성공률 : 76.74% 문제 : 2개의 문자만 남기고 모두 지웠을 경우 가장 긴 길이 값을 가지는 문자열을 만들어라 그리고 그 문자열의 길이를 리턴하라 단 동일한 문자가 연속으로 위치하면 안된다 만들 수 없을 경우 0 리턴 풀이 1. 문자 종류별로 별도 리스트를 만든다 (lCharList) 2. 리스트에서 2개씩 뽑아서 문자열을 만든다 만드는 도중 연속된 문자이면 다음으로 넘어간다 3. 문자열이 완성 됐을 경우 길이를 구해서 최댓값과 비교한다 4. 모든 반복(2개의 문자로 문자열 만들기)이 끝난 후 최종 맥스 길이를 리턴한다 답안 #!/bin/python3 imp.. HackerRank [Search] Hackerland Radio Transmitters /알고리즘 해커랭크 문제 주소 : https://www.hackerrank.com/challenges/hackerland-radio-transmitters/problem 문제 : 1차원 배열의 마을에서 모든 집에 라디오가 들르게 하는데 필요한 송신기의 수 풀이 1. 시작점(nBefore)에서 최대로 멀리 세울 수 있는 안테나 위치(nPos)를 찾는다 2. 그 위치로부터 영향을 주는 최대거리(nAfter)를 찾는다 그리고 안테나 수(Antcnt) 값을 누적시킨다 3. 그 다음칸을 시작점으로 변경 후 위 작업을 반복하여 마을의 끝 위치에 도달하면 종료 답안 #!/bin/python3 import math import os import random import re import sys # Complete the hackerlan.. HackerRank [Graph Theory] Roads and Libraries /알고리즘 해커랭크 문제 주소 : www.hackerrank.com/challenges/torque-and-development/problem 문제 : 도서관의 수, 도시의 수, 도서관 건설비용, 도로 건설비용 값을 주고 모든 도시가 최소 하나이상의 도서관과 연결되기 위해 발생하는 최소 비용 계산 풀이 1. 우선 도로건설 비용보다 도서관 건설 비용이 더 저렴하면 모든곳에 도서관을 지으면 된다 2. 도시의 수만큼 2차원 리스트를 만들어 깊이우선탐색으로 이어질 수 있는 최대의 도로 길이를 구한다(도로가 더 저렴하니 최대 도로길이가 중요) 3. 도로길이*도로비용 + (도시의 수 - 도로길이)*도서관 비용 을 계산한다 4. 결과적으로 몇개의 도시가 있는지가 중요한게 아니라 최대 몇개의 도로를 이을 수 있는지가 관건이다 답안 imp.. HackerRank [Constructive Algorithms] Flipping the Matrix /알고리즘 해커랭크 문제주소 : www.hackerrank.com/challenges/flipping-the-matrix/problem 문제 : 2n * 2n 크기의 매트릭스를 큐브돌리듯이 상하 좌우를 회전시켜서 n * n 크기의 좌측상단 매트릭스에 최대값이 위치하도록 한 뒤 그 매트릭스의 모든값을 합한값을 리턴하라 풀이 1. 매트릭스 가장 좌측상단의 1열1행에 있는 값은 아무리 회전한들 결국 존재할 수 있는 위치는 n열n행, 1열 n행, n열 1행, 1열1행 4곳밖에 존재 할 수 없다 2. 반대로 그 4곳에 위치하는 값중 가장 큰 값이 1열1행에 존재하게 될 것이다 3. 모든 나머지 매트릭스의 위치값들도 matrix[i][j], matrix[i][n-j-1], matrix[n-i-1][j], matrix[n-i-1][n-.. HackerRank [Bit Manipulation]Lonely Integer /알고리즘 해커랭크 문제주소 : www.hackerrank.com/challenges/lonely-integer/problem 문제 : 주어진 int array에서 같은 수의 값을 한쌍씩 제외시킨 후 홀로남는 값을 리턴하라 풀이 1. 같은 값을 한쌍씩 없애는 가장 쉬운방법은 모든값을 누적으로 xor시켜버리면 된다 답안 #!/bin/python3 import math import os import random import re import sys def lonelyinteger(a): result = 0 for i in a: result = result ^ i return result if __name__ == '__main__': # fptr = open(os.environ['OUTPUT_PATH'], 'w') fptr =.. HackerRank [Bit Manipulation] Counter game /알고리즘 해커랭크 문제 주소 : www.hackerrank.com/challenges/counter-game/problem 문제 : Louise와 Richard가 번갈아 가며 주어진 숫자가 2의 제곱근 값인지 확인한다 2의 제곱근 값이라면 1/2 값을 상대에게 넘기고 아니라면 주어진 숫자보다 작은 숫자 중 가장 높은 2의 제곱 값과의 차이 값을 상대에게 넘겨주되 1을 넘겨주면 승리한다 Louise가 항상 먼저 시작한다 풀이 1. 공학용 계산기에 2의 제곱근을 순서대로 입력해보았다 (2..4..8..16..32) 이 값들의 2진수 값들은 10, 100, 1000, 10000이다 가장 앞자리는 1이고 2의 승수만큼 뒤에 0이 붙는다 2. 전달받은 값 n을 2진수로 바꾸고 그 길이를 구한 뒤 그 길이와 같은 2의 제곱근 값을 .. HackerRank [Recursion] The Power Sum /알고리즘 해커랭크 문제 주소 : https://www.hackerrank.com/challenges/the-power-sum/problem The Power Sum | HackerRank Split up a number in a specified manner. www.hackerrank.com 문제 : X값과 N값이 주어졌을때 X값을 자연수의 N승만큼 한 값을 합해 만들 수 있는 케이스의 수를 구하는문제 보기에 나오는 예를 보면 X가 100 N이 2로 주어졌을경우 자연수의 2승의 합으로 100을 만들 수 있는 경우는 10^2, 6^2+8^2, 1^2+3^2+4^2+5^2+7^2 이와같이 3가지 방법으로 표현이 가능하다 풀이 1. 먼저 X루트 N을하면 어떤 값을 N승 했을 때 X보다는 작은 최대값을 구할 수 있다 예) 위의.. 이전 1 2 3 4 5 다음
