이숭간 공부기록

https://programmers.co.kr/learn/courses/30/lessons/42883 코딩테스트 연습 - 큰 수 만들기 programmers.co.kr 문제유형 : 그리디 문제풀이 : 스택을 이용한다. ( 숫자의 맨앞을 계속해서 더 크게 만들어주는것 ) 스택에 숫자가 있고 k가 0 이상이면 현재숫자와 비교해서 더 큰값이 스택의 앞쪽에 위치할 수 있도록 한다. 만약 현재숫자가 현재스택 최상단숫자보다 작으면 그냥 넣는다. 현재숫자가 더 크다면 스택에서 pop하고 k를 1감소시킨다. 이 과정을 더이상 스택의 최상단에서 현재숫자보다 큰값이 안나올때가지 반복한다. 숫자를 모두 확인했는데 k가 0이상이면 더 제거해야한다는 뜻이고, 이미 앞쪽에는 최대한 큰 숫자가 앞에 위치하도록 조정해 놓은것이므로 ..

https://programmers.co.kr/learn/courses/30/lessons/42898 코딩테스트 연습 - 등굣길 계속되는 폭우로 일부 지역이 물에 잠겼습니다. 물에 잠기지 않은 지역을 통해 학교를 가려고 합니다. 집에서 학교까지 가는 길은 m x n 크기의 격자모양으로 나타낼 수 있습니다. 아래 그림은 m = programmers.co.kr 문제유형 : DP 문제풀이 : 특정 좌표가 웅덩이에 포함되어있는지 확인할때 주어진 좌표는 행,열이 바뀌어잇기때문에 i,j가 아니라 j,i로 확인해줘야했다. 점화식 : S[i][j] = S[i-1][j] + S[j-1][i] 이때 j,i가 puddles에 포함되어있다면 위 점화식을 수행하지 않고 0으로 바꿔주고 넘어간다. 정답코드 : def soluti..

https://programmers.co.kr/learn/courses/30/lessons/42586 코딩테스트 연습 - 기능개발 프로그래머스 팀에서는 기능 개선 작업을 수행 중입니다. 각 기능은 진도가 100%일 때 서비스에 반영할 수 있습니다. 또, 각 기능의 개발속도는 모두 다르기 때문에 뒤에 있는 기능이 앞에 있는 programmers.co.kr 문제유형 : 스택 문제풀이 : 정답코드(파이썬): from collections import defaultdict def solution(progresses, speeds): answer = [] daycount = defaultdict(int) # progresses가 빌때까지 100이 안넘을때만 시간을 1씩 증가시키면서 더해준다. # 더해가면서 맨앞의..

https://programmers.co.kr/learn/courses/30/lessons/17677 코딩테스트 연습 - [1차] 뉴스 클러스터링 뉴스 클러스터링 여러 언론사에서 쏟아지는 뉴스, 특히 속보성 뉴스를 보면 비슷비슷한 제목의 기사가 많아 정작 필요한 기사를 찾기가 어렵다. Daum 뉴스의 개발 업무를 맡게 된 신입사원 튜브 programmers.co.kr 문제유형 : 문자열, 구현, 집합 문제풀이 : 주어진 조건에 맞게 문자열을 잘 조작하고 집합연산도 적절하게 사용해서 구현하는 문제 나는 Counter를 쓰긴 했는데 다른분 풀이보니까 그냥 리스트.count()하면 되긴한다 그래도 딕셔너리 쓰는게 더 시간복잡도가 좋지않을 ㄲ ㅏ..? 시픈데 어쨋든 내 코드가 더 복잡하긴 하다. 정규식을 잘 기..

https://programmers.co.kr/learn/courses/30/lessons/81303 코딩테스트 연습 - 표 편집 8 2 ["D 2","C","U 3","C","D 4","C","U 2","Z","Z"] "OOOOXOOO" 8 2 ["D 2","C","U 3","C","D 4","C","U 2","Z","Z","U 1","C"] "OOXOXOOO" programmers.co.kr 문제유형 : 구현 문제풀이 : 일단 이문제는 내가 푼 시점에서 푼사람이 0명인 문제다... 얼마전에 올라온건가?? 2시간동안 풀었는데 결국 효율성을 통과하지 못했다.. 최초가 되고싶었는데.. 근데 검색해도 하나도 안나오고 질문하기도 0이라 도저히 머리가 터질거같아서 일단 이쯤하고 올려둔다. 아시는분있음 댓글좀 부..

https://programmers.co.kr/learn/courses/30/lessons/49189 코딩테스트 연습 - 가장 먼 노드 6 [[3, 6], [4, 3], [3, 2], [1, 3], [1, 2], [2, 4], [5, 2]] 3 programmers.co.kr 문제유형 : 다익스트라 문제풀이 : 1번노드를 시작으로하는 다익스트라 알고리즘을 수행한다. 이때 모든 간선의 비용을 1로보고 계산한다. 다익스트라가 끝났을때 최단거리 테이블에서 INF을 제외한, 가장큰 비용을 갖는 노드의 개수를 출력한다. 정답코드 : # 1번노드를 출발지로하여 다익스트라 실행 # 모든 간선의 비용을 1로보고 다익스트라가 끝났을때 최단거리테이블에서 가장 값이 높은 노드를 출력한다. import heapq def so..