programmers.co.kr/learn/courses/30/lessons/17677 코딩테스트 연습 - [1차] 뉴스 클러스터링 뉴스 클러스터링 여러 언론사에서 쏟아지는 뉴스, 특히 속보성 뉴스를 보면 비슷비슷한 제목의 기사가 많아 정작 필요한 기사를 찾기가 어렵다. Daum 뉴스의 개발 업무를 맡게 된 신입사원 튜브 programmers.co.kr 2018 KAKAO BLIND RECRUITMENT(카카오 공채 1차)에 나온 문제이다. 1. 대소문자 구별을 하지 않으므로 str1과 str2 모두 대문자로 변환한다. 2. str1을 돌며 두 글자씩 끊어서 다중집합의 원소로 만들고 A에 넣는다. 두 글자로 끊은 원소가 이미 A에 있다면 갯수를 1증가시키고 아니면 새로운 index를 만들어준다. (영문자..
programmers.co.kr/learn/courses/30/lessons/43105 코딩테스트 연습 - 정수 삼각형 [[7], [3, 8], [8, 1, 0], [2, 7, 4, 4], [4, 5, 2, 6, 5]] 30 programmers.co.kr 1. 먼저 triangle 배열과 같은 모양의 dp 2차원 배열을 만든다. 2. 마지막 줄부터 올라갈 것이므로 dp의 마지막줄은 triangle의 마지막 줄과 같게 만들어준다. 3. 마지막에서 두번째 줄부터해서 dp[i][j]에 (밑의 두 숫자 중 큰 값 + triangle[i][j]값)을 넣어준다. 4. 최종적으로 맨 윗줄에 최댓값이 저장되므로 dp[0][0]을 return해준다. def solution(triangle): length = len(t..
programmers.co.kr/learn/courses/30/lessons/42584 코딩테스트 연습 - 주식가격 초 단위로 기록된 주식가격이 담긴 배열 prices가 매개변수로 주어질 때, 가격이 떨어지지 않은 기간은 몇 초인지를 return 하도록 solution 함수를 완성하세요. 제한사항 prices의 각 가격은 1 이상 10,00 programmers.co.kr 스택이 개념은 쉬운데, 마스터하기는 매우 어려운 자료구조인 것 같다. (나만 그런가..) 스택을 활용해 푸는 문제들이 유독 어렵게 느껴진다... 1. answer에 len(prices)-1부터 0까지 넣어준다. prices길이가 5이면 answer = [4, 3, 2, 1, 0] 2. prices가 [1, 2, 3, 2, 3]일 때, ..
programmers.co.kr/learn/courses/30/lessons/42839 코딩테스트 연습 - 소수 찾기 한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다. 각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이 programmers.co.kr 처음에 numbers에 있는 숫자들에 대해 모든 경우의 수를 구해야 한다. 이 문제를 풀고 나서 다른 사람들의 풀이를 보니 다양한 방법이 존재했다. 나는 itertools모듈의 permutations함수를 사용했다. 1. numbers에 있는 숫자를 num배열에 넣고 dab에도 넣어준다. (한자리 수는 따로 처리) -> permutations(num, 1)을 하..
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 백준에서 많이 풀어본 그래프 문제들과 비슷하다. 처음에 DFS로 풀어보려다 실패하고 BFS로 풀었다. from collections import deque def solution(n, edge): graph = [[] for _ in range(n+1)] dist = [0] * (n+1) visited = [False] * (n+1) q = deque() q.append(1) visited[1] = True for i in edge: graph[..
www.acmicpc.net/problem/14676 14676번: 영우는 사기꾼? 프로그램의 입력은 표준 입력으로 받는다. 입력의 첫 줄에는 건물 종류의 개수 N, 건물 사이 관계의 개수 M, 영우의 게임 정보의 개수 K가 주어진다.(1 ≤ N, M, K ≤ 100,000) 다음 줄부터 M줄에 걸쳐 www.acmicpc.net 앞서 올렸던 위상정렬 알고리즘을 응용해서 푸는 문제이다. 1. M만큼 X, Y를 입력받고 graph[X]에 Y를 append해주고, indegree[Y]에 1을 더해준다. 2. K만큼 반복문을 돌며 건물을 짓거나 파괴합니다. 3. 만약 command가 1이라면 building번 건물을 짓고자 하는 것이므로 indegree[building]을 확인한다. 3-1. indegree[b..
www.acmicpc.net/problem/2252 2252번: 줄 세우기 첫째 줄에 N(1≤N≤32,000), M(1≤M≤100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의미이 www.acmicpc.net 전형적인 위상정렬 문제이다. 위상정렬 알고리즘은 추후에 한 번 포스팅 할 예정이다. 1. N, M을 입력받고 M번 만큼 A와 B를 입력받는다. 2. A가 B 앞에 줄 서야 하므로 graph[A]에 B를 append해주고 indegree[B]에 1을 더해준다. (indegree 배열: 진입차수) 3. indegree[1]부터 indegree[N]까지 돌며 진입차수가 0인 노드를 큐..
www.acmicpc.net/problem/11946 11946번: ACM-ICPC 대회가 끝난 후 팀 별 성적을 순위에 따라 출력한다. 만약 순위가 같으면 팀 번호가 빠른 것을 먼저 출력한다. 각 팀마다 팀 번호, 푼 문제 수, 총 시간을 출력한다. www.acmicpc.net 단순 구현문제이지만, 생각보다 빡세서 포스팅해본다. 일단 입력값이 많고, 그에 대한 순서 처리가 생각보다 힘들다. 1. dic이라는 딕셔너리를 만들고 미리 1번팀의 1번문제 결과부터 n번팀의 m번 문제결과 까지 [0, -1]을 만들어 놓는다. (주석에 설명했듯이 '틀린횟수'와 '총 시간'이다) 2. q개의 로그를 입력받는다. 만약 log[3]이 'AC'가 아니라면 틀린 것이므로 해당하는 팀의 문제결과인 dic[dic[(int(l..
모르는 사이에 조금씩 조금씩..
