본문 바로가기
반응형

python61

주식 가격 [프로그래머스] 코드 def solution(prices): answer = [] prices = list(reversed(prices)) for index, price in enumerate(prices): if len(answer) == 0: answer.append(index) else: flag = False for i in range(index-1, -1, -1): if prices[i] < price: answer.append(index-i) flag = True break if not flag: answer.append(index) answer = list(reversed(answer)) return answer 문제 풀이 스택/큐 문제라는데 어떻게 써야할지 감이 안잡혔다. (지금도...) 첫번째 시도에선 .. 2021. 11. 17.
문자열 압축 [프로그래머스] 코드 def solution(s): answer = len(s) for n in range(1, len(s)//2+1): count = 1 temp_sentence = "" for index in range(0, len(s), n): prev_s = s[index:index+n] next_s = s[index+n:index+(2*n)] if prev_s == next_s: count+=1 else: if count != 1: temp_sentence += str(count)+prev_s else: temp_sentence += prev_s count = 1 # print(temp_sentence, len(temp_sentence)) if answer > len(temp_sentence): answer =.. 2021. 11. 14.
삼각 달팽이 [프로그래머스] 쉬운 문제인데 집중력이 약해서 그런지 딴짓하느라 못풀었다. 어려운건 각 조건이 만족할때 방향을 바꿔야 하는데 그부분이 어려웠다. 처음에 떠올린건 더이상 아래방향으로 못내려갈때까지 내려간다. 그 후 왼쪽으로 더이상 왼쪽방향으로 못갈때까지 움직인다. 그후 대각선 위로 대각선 위로 움직인다. 움직일 방향에 숫자가 있다면 아래로 1-2-3을 반복한다. 아래, 왼쪽, 대각선 위가 숫자로 차있다면 멈춘다. 문제는 4번 과정에서 아래, 왼쪽, 대각선을 검사할때 index error(out of bound)가 발생했다는 점이다. 그래서 row+1, column+1 이 n을 넘지 않을때로 제한하는 로직을 추가했다. n ≥3 일때 잘 돌아갔지만 n ≤ 2 일때 돌아가지 않는 문제가 발생했다. 4번 로직을 지우고 새로운 로.. 2021. 11. 5.
n^2 배열 자르기 [프로그래머스] 문제 풀이 정리 문제를 머리속에 집어넣어놓고 풀진 않고 언젠간~ 하면서 지내다가 회사에서 점심 먹고 쉬는와중에 끄적이다 풀었다. (진짜 아무 생각없이 써보다가!) 문제 움짤을 보면 좀더 이해하기 쉽지만 다시 써보자면 입력으로 주어지는 n 숫자 ⇒ n * n 행렬을 만든다. 숫자를 채워넣는다. (위 움짤처럼) 행렬을 1*n^2의 배열로 재배치한다.(한줄로 쭈르륵 줄세운다고 보면 된다.) 입력으로 주어지는 left ~ right 까지의 index에 써진 숫자를 반환한다. 얼핏 생각하면 1~4 단계를 구성해 숫자를 채워넣은뒤, 행렬을 차례대로 지나면서 써져있는 숫자를 반환하면 될 것 같지만 문제에서 주어지는 n의 숫자가 매우 컸다. (n이 커지면 n*n행렬을 만든뒤 숫자를 쓰는 것도 시간이 오래걸릴것...) .. 2021. 10. 30.
문서 요약 하기 (with textrank) 구글은 pagerank 라는 알고리즘을 통해 검색의 품질을 높혔다. pagerank 알고리즘을 설명해보자면 "더 중요한 페이지는 더 많은 사이트로부터 링크를 받는다" 는 관찰에 기조해 만들어진 알고리즘이다. 위키피디아에 써져있는 예를 보자면 페이지 A가 페이지 B,C,D 로 총 3개의 링크를 걸었다면 B는 A의 페이지 랭크 값의 (1/3) 만큼을 가져온다(?) 풀어서 써보자면 특정 페이지 A 에 B, C, D 의 링크를 걸었다면 ( B 페이지의 중요도(pageRank) + C 페이지의 중요도 + D 페이지의 중요도 ) / 3(=A페이지에 걸린 링크 수) 의 페이지 중요도 (pageRank A)를 가지게 되는 것이다. 또 알고리즘은 인터넷 서핑하는 가상의 인물(random surfer)를 정의 하고, 해당.. 2021. 10. 23.
뉴스 문서 군집화 하기.ver2 ( document clustering using Minhash & LSH) 두 문서의 유사도는 문서에 나타난 요소들 (ex. 음절, 어절, 형태소) 을 집합 형태로 만들어 집합간의 비교로 치환해 비교할 수 있다. 문서1 = "나는 밥을 먹었다. 나는 학교에 갔다." 문서2 = "나는 밥을 먹었고, 학교에 갔다." 두 문서가 존재 할때 두 문서를 어절 단위(띄어쓰기로 나눠서) 집합으로 변경시켜보면 문서1_집합 = { '나는', '밥을', '먹었다.', '학교에', '갔다.' } 문서2_집합 = { '나는', '밥을', '먹었고,', '학교에', 갔다.' } 이때 두 문서의 유사성을 비교할때 여러 방법들이 존재하지만 이번 글에서는 자카드 유사도(Jaccard similarity) 라는 방법을 이용한다. 자카드 유사도 ⇒ https://ko.wikipedia.org/wiki/자카드_.. 2021. 10. 15.
전력망을 둘로 나누기 [프로그래머스] 문제 넋두리 나는 문제를 set으로 풀려고 했다. 계획은 이랬다. 특정 node(ex.wires[0][0]) 를 left set에 넣는다. wires중 하나를 제거한다. 잘라진(하나가 제거된) wires 배열을 루프돌면서 left set에 wire[0], wire[1]이 존재한다면 left에 추가 한다. 루프가 끝난시점에 left에 담긴 node 와 그렇지 않은 node set 간의 갯수 차이를 리턴 2-4번 (n-1)번 반복 하면서 차이가 제일 작은 값을 answer로 저장 그런데 자꾸 틀렸다. 틀린 이유를 못찾았는데 예상하기로는 left set에 담기는 조건이 wire[0] 이나, wire[1]이 left set에 존재하는지 여부 였는데, (⇒ if wire[0] in left or wire[1] i.. 2021. 10. 9.
예상 대진표 [프로그래머스] 문제 풀이 예전엔 안 풀리던 문제가 이제는 '음~ 너무 쉽고~' 정도로 풀리는 것 같아서 기분이 좋다. 이 문제는 저렇게 말할 정도로 쉬웠기 때문에 설명을 생략할까 하다가 적어본다. (아니 사실은 쉽게 풀어서 기분좋게 글쓴다.) 문제 조건에 써있듯이 부전승이 없다. 게다가 2^n 승의 참가자가 존재한다 = 그럼 무조건 어디선가 만난다. 그림으로 보자. 우리가 주의 깊게 봐야하는건 left와 right를 나누는 저 경계선이다. 저 경계선을 기준으로 left / right 나뉜다면 무조건 n번 경기를 한다. 만약 선수 a,b가 경계보다 작거나, 클경우엔? 경계선을 다시 그려준 뒤, 해당 경계에서 left / right인지 검사, 나뉜다면 n-1번 경기 아니면 다시 경계선 그리기... 이렇게 반복하는 걸 우린.. 2021. 9. 23.
dfs 유형의 문제 [프로그래머스 & leetcode] 프로그래머스에서 풀었던 문제가 마침 leetcode에서 비슷하게 출제되어 푸는김에 같이 정리하는게 나을듯하다. dfs란? 그림으로 보자면, 마지막 노드까지 전부 확인한 뒤, 이동하는 것을 볼 수 있다. 문제를 보자 문제 설명 n개의 음이 아닌 정수가 있습니다. 이 수를 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다. 1+1+1+1+1 = 3 +1-1+1+1+1 = 3 +1+1-1+1+1 = 3 +1+1+1-1+1 = 3 +1+1+1+1-1 = 3 사용할 수 있는 숫자가 담긴 배열 numbers, 타겟 넘버 target이 매개변수로 주어질 때 숫자를 적절히 더하고 빼서 타겟 넘버를 만드는 방법의 수를 ret.. 2021. 9. 20.
반응형

티스토리툴바