동학 개발 운동

문제 출처 : www.acmicpc.net/problem/1238 1238번: 파티 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어 www.acmicpc.net 문제 해석 : 어떤 정점에서 한 정점으로 왕복하는 거리가 가장 먼 것을 찾는 문제이다. 파티를 갔다오는 사람들은 항상 최단 경로로 왕복한다고 했기 때문에 최단 경로로 특수 정점을 왕복하는 문제로 해석 가능하다. 문제 풀이 : 다익스트라 알고리즘을 통해서 문제를 풀 수 있다. - 플루이드 워셜 문제로 풀 경우에는 10^9로 시간 복잡도가 너무 크기 때문에 시간 초과가 ..

※ 아래의 글은 주관적인 생각을 적은 것입니다. ※ 코딩테스트 문제나, 면접의 구체적인 문제, 내용, 진행 과정은 일절 포함하고 있지 않습니다. 간략한 본인 소개 대학 : 경기권 4년제 대학 전공 : 소프트웨어학 졸업 예정 : 2021년 2월 졸업예정 학점 : 3.66/4.5 경험 1. University of California Irvine 방문 연구원 활동 2. University of Pennsylvania 어학연수 3. 스타트업 인턴 16주 4. 중소기업 인턴 8주 5. 교내 연구실 활동 10개월 어학 TOEIC : 865 TOEIC SPEAKING : LEVEL 6 이번 2020 하반기에 처음 취업 준비를 시작했습니다. 삼성전자의 경우 9월 초~중순에 서류전형 공고를 띄우기 때문에 가장 먼저 서..

문제 출처 : www.acmicpc.net/problem/1167 1167번: 트리의 지름 트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2≤V≤100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. (정점 번호는 1부터 V까지 www.acmicpc.net 문제 해석 : 트리의 정점과 정점 사이의 거리가 주어 졌을 때 한 정점에서 다른 정점까지의 거리가 가장 멀때의 거리를 구하는 문제이다. 문제 풀이 : 이 문제는 BFS, DFS로 풀이 할 수 있다. 이때 아래의 2가지를 주의하면서 차근차근 풀어야 한다. 1. 어떤 점에서 출발하는지를 정해야 한다. -> 항상 1에서 시작하는게 가장 길지 않을 수 있다. --> 따라서 1번 수행하면서 가장..

문제 출처 : www.acmicpc.net/problem/1043 1043번: 거짓말 지민이는 파티에 가서 이야기 하는 것을 좋아한다. 파티에 갈 때마다, 지민이는 지민이가 가장 좋아하는 이야기를 한다. 지민이는 그 이야기를 말할 때, 있는 그대로 진실로 말하거나 엄청나게 www.acmicpc.net 문제 해석 : 지민이는 이야기의 진실을 모르는 자리에서는 과장된 이야기를 하고 진실을 아는 사람이 있는 곳에서는 진실된 이야기를 한다. 이때 과장된 이야기를 할 수 있는 파티의 수를 구하는 문제이다. 문제 풀이 : 단순하게 진실을 아는 사람 수를 체크하면 순서관계가 얽히게 되면 정답을 도출할 수 없게 된다. 예를 들어 1번 파티 1, 2 2번 파티 2, 3 3번 파티 3, 4 4번 파티 4, 5 5번 파티 ..

문제 출처 : www.acmicpc.net/problem/1149 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 문제 해석 : RGB 거리를 구하는 문제로 각각 RGB마다 주어진 값이 있다. 이 값을 최소로 만들어야 한다. 이때 자신의 바로 앞에서 선택된 색은 고를 수 없다. 문제 풀이 : DP로 문제를 해결 할 수 있다. -> 각 3가지 경우 모두를 매번 자신의 색을 제외한 최소값으로 고르면서 진행하면 마지막에 최소를 구할 수 있다. 풀이 코드 import sys input = sys..

문제 출처 : www.acmicpc.net/problem/18870 18870번: 좌표 압축 수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다. Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표의 개수와 같아야 한다. X1, X2, ..., XN에 좌 www.acmicpc.net 문제 해석 : 좌표를 새롭게 부여하는 문제이다. 즉 자신이 몇번째 순서인지로 수를 바꾸는 것이다. 이때 중복되는 수가 있을 경우 같은 수를 가진다. 문제 풀이 : 중복을 제거하고 정렬한 다음 딕셔너리로 만들어서 해당 숫자를 매핑 해주면 된다. 따라서 파이썬에서 제공하는 set() 과 sorted(), dictionary 자료형을 활용하면 풀 수 있..

문제 출처 : www.acmicpc.net/problem/17626 17626번: Four Squares 라그랑주는 1770년에 모든 자연수는 넷 혹은 그 이하의 제곱수의 합으로 표현할 수 있다고 증명하였다. 어떤 자연수는 복수의 방법으로 표현된다. 예를 들면, 26은 52과 12의 합이다; 또한 42 + 32 + 1 www.acmicpc.net 문제 해석 : 모든 수는 4개 이하의 제곱 수로 나타 낼 수 있다. 이때 주어진 N은 최소 몇개의 제곱수로 나타낼 수 있는가? 문제 풀이 : DP 문제로 풀이 할 수 있다. 자신의 수에서 그보다 작은 수의 제곱수를 뺀 것의 최소를 구하고 거기에 한개를 더해주면 된다. 가능한 다른 풀이 : 브루트포스로 가능한 모든 경우를 풀어 볼 수도 있다. 풀이 코드 N = i..

문제 출처 : www.acmicpc.net/problem/17219 17219번: 비밀번호 찾기 첫째 줄에 저장된 사이트 주소의 수 N(1 ≤ N ≤ 100,000)과 비밀번호를 찾으려는 사이트 주소의 수 M(1 ≤ M ≤ 100,000)이 주어진다. 두번째 줄부터 N개의 줄에 걸쳐 각 줄에 사이트 주소와 비밀번 www.acmicpc.net 문제 해석 : 저장한 비밀번호를 찾아 이를 출력하는 문제이다. 문제 풀이 : 간단한 딕셔너리 활용 문제이다. 저장을 딕셔너리로 하고 사이트를 키값으로 지정해 주면 된다. 풀이 코드 import sys input = sys.stdin.readline N, M = map(int, input().split()) add = {} for _ in range(N): site, ..

문제 출처 : www.acmicpc.net/problem/11727 11727번: 2×n 타일링 2 2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×17 직사각형을 채운 한가지 예이다. www.acmicpc.net 문제 해석 : 1X2, 2X1, 2X2 타일을 사용해서 2XN의 타일을 모두 채우는 방법의 경우의 수를 구하는 문제이다. 문제 풀이 : 전형적인 DP 문제로 dp[i] = (dp[i-2]*2) + dp[i-1] 의 점화식을 사용해서 풀 수 있다. 풀이 코드 N = int(input()) dp = [0,1,3,5] for i in range(4,N+1): dp.append((dp[i-2]*2) + dp[i-1] ) print(d..

문제 출처 : www.acmicpc.net/problem/11726 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net 문제 해석 : 2X1 짜리 타일로 2XN의 타일을 채울 수 있는 방법의 수를 구하는 문제이다. 문제 풀이 : 이 문제는 DP로 풀 수 있다. 모든 경우는 앞에 있는 경우에 한쪽 끝에 타일이 붙은 것으로 생각할 수 있다. 이는 dp[i] = dp[i-1] + dp[i-2]라는 점화식으로 만들 수 있고 이를 그대로 활용하면 문제를 풀 수 있다. 풀이 코드 N = int(input()) dp = [0,1,2] for i i..