본문 바로가기

자료구조 & 알고리즘 & cs/CodingTest

 (67)
[python] 1167 - 트리의 지름 1167번: 트리의 지름 (acmicpc.net) 1167번: 트리의 지름 트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. 정점 번호는 1부터 V까지 www.acmicpc.net 트리의 지름이란? 트리의 모든 경로들 중 가장 긴 경로의 길이를 의미한다. 문제 자체는 dfs나 bfs 로 구현하면 되는 문제였는데 트리의 지름을 구하기 위해 필요한 공식이 있었다. 트리의 지름이 u-v라고 할 때, 임의의 점 x에서 가장 먼 노드는 u 또는 v가 된다. 따라서 임의의 노드에서 가장 먼거리에 있는 노드를 찾고 그 노드에서 다시 가장 먼 거리의 노드를 찾으면 트리의 지름을 찾을 수 ..
[java/python] 프로그래머스 Lv2. - JadenCase 문자열 만들기 코딩테스트 연습 - JadenCase 문자열 만들기 | 프로그래머스 스쿨 (programmers.co.kr) 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 파이썬으로 코드를 짤 때 처음에는 isupper, islower 등의 함수를 이용하여 짰는데 풀이코드를 참고하던 중 간단한 함수가 있어 기록하려 한다. [python] def solution(s): answer='' s=s.split(" ") for i in range(len(s)): s[i] = s[i].capitalize() answer =' '.join(s) return answer capital..
[java/python] 프로그래머스 Lv2. - 하노이 탑 코딩테스트 연습 - 하노이의 탑 | 프로그래머스 스쿨 (programmers.co.kr) 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 이전에 백준에서 똑같은 문제를 풀었을 때 잘 이해가 가지 않았는데 이번에 다시 풀어보니 이해가 갔던 문제였다. 재귀함수의 기본인 하노이탑 문제를 정리해보았다. 1. 원반 n개를 가장 오른쪽 기둥으로 모두 옮겨야 한다. 2. 한 번에 하나씩만 옮길 수 있다. 3. 크기가 큰 원반 위에 작은 원반을 올려야 한다. 이 사항들을 지키며 주어진 원반을 옮겨야 한다. 문제에서는 최소로 움직이는 경로를 구해야하는데 재귀함수를 이용하여..
[python] 13549 - 숨바꼭질 3 13549번: 숨바꼭질 3 (acmicpc.net) 13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 이번 문제는 bfs와 다익스트라 두 가지 방법으로 풀이할 수 있다. 전에 bfs 문제를 풀 때 다루었던 문제랑 똑같은게 아닌가? 했는데 이 문제에서는 가중치를 고려해야한다. 그래서 전에 풀었던 bfs 방식에서 가중치를 고려하여 살짝 변형하여 풀고 최근에 학습한 다익스트라로도 코드를 짜 보았다. [BFS] import sys from collections import deque #..
[python/java] 프로그래머스 Lv2. - 최솟값 만들기 코딩테스트 연습 - 최솟값 만들기 | 프로그래머스 스쿨 (programmers.co.kr) 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 파이썬으로는 배열의 정렬을 사용하여 매우 간단하게 풀었다. [python] def solution(A,B): answer = 0 A.sort() B.sort(reverse=True) for i in range(len(A)): answer += A[i]*B[i] return answer 그런데 자바를 사용할 경우 이슈가 발생했다. 기존에 알고있던 Arrays.sort()와 Arrays.sort(arr, Collection..
[python] 프로그래머스 Lv2. - 줄 서는 방법 코딩테스트 연습 - 줄 서는 방법 | 프로그래머스 스쿨 (programmers.co.kr) 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제를 이해하는 것이 꽤나 어려웠다. 팩토리얼까지는 접근을 했는데 그 다음 식으로 구현하는 것에 애를 먹었다. 문제와 같이 n=3, k=5일 경우 모든 경우의 수를 나열해보면 다음과 같다. [1,2,3] [1,3,2] [2,1,3] [2,3,1] [3,1,2] [3,2,1] 따라서 결과는 5번째 방법인 [3,1,2]가 리턴되어야 한다. 줄을 서는 모든 경우의 수는 n을 일렬로 나열하는 경우의 수 n!가지이다. 예를 들어..
[java/python] 프로그래머스 Lv2. - 숫자의 표현 코딩테스트 연습 - 숫자의 표현 | 프로그래머스 스쿨 (programmers.co.kr) 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 난이도가 높지 않은 문제였다. [python] def solution(n): answer=1 for i in range(1, n+1): sum=i for j in range(i, n-1): sum+= j+1 if sum > n: break if sum == n: answer+=1 break return answer 처음에 sum의 크기를 고려하지 않았다가 효율성 테스트에서 시간초과가 발생했다. 계산 횟수를 줄이기 위해 s..
[java/python] 프로그래머스 Lv.2 - 땅따먹기 코딩테스트 연습 - 땅따먹기 | 프로그래머스 스쿨 (programmers.co.kr) 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr dp를 사용하여 해결하였다. [python] def solution(land): if len(land) == 1: return max(land) else: for i in range(1,len(land)): for j in range(4): if j == 0: land[i][j] += max(land[i-1][1], land[i-1][2], land[i-1][3]) elif j ==1: land[i][j] += max(lan..
728x90

티스토리툴바