유니피즈

백준 14889 스타트와 링크 파이썬 문제 https://www.acmicpc.net/problem/14889 14889번: 스타트와 링크 예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다. www.acmicpc.net 문제이해돕기 4일때는 12 / 34 팀 일때 S12+S21 / S34 + S43 인건 알겠는데, 6일때는 ? 123 /456 팀 일때 S12+S13+S21+S23+S31+S32 / S45+S46+S54+S56+S64+S65 입니다. 접근과정 1. 스타트팀의 모든 조합을 구한다. --> DFS이용하기 2. 전체집합에서 스타트집합을 뺀 여집합을 구한다. --> 링크 팀 3. 그래..

백준 14888 연산자 끼워넣기 파이썬 문제 https://www.acmicpc.net/problem/14888 14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, www.acmicpc.net 접근법 연산자들을 중복을 제거하여 순서대로 줄세우는게 관건이다. 12345 를 순서대로 줄 세운다면, 경우의 수는 5! = 5*4*3*2*1 = 120 이다. 만약 11234 라면 ? 5!/2 = 5*4*3*2*1/2 = 60 이다. 수학의정석 10-가 였나? 공부했던 기억이 난다. 중복을 제거하는..

백준 1002 터렛 파이썬 https://www.acmicpc.net/problem/1002 1002번: 터렛 각 테스트 케이스마다 류재명이 있을 수 있는 위치의 수를 출력한다. 만약 류재명이 있을 수 있는 위치의 개수가 무한대일 경우에는 -1을 출력한다. www.acmicpc.net 접근 중학교3학년인가 풀었던 수학문제랑 같았다. 1. 두 원이 겹쳐 있을 때, 2. 두 원이 떨어져 있을 떄, 3. 위의 두 케이스에서 접 점일 때, 4. 중심점이 같고 반지름 길이가 다를 때 를 고려하면 풀린다. import sys import math input=sys.stdin.readline for _ in range(int(input())): a=list(map(int,input().split())) # 0 1 2..

문자열을 다뤄보자. 백준 2675 문자열 반복 자바 파이썬 https://www.acmicpc.net/problem/2675 2675번: 문자열 반복 문자열 S를 입력받은 후에, 각 문자를 R번 반복해 새 문자열 P를 만든 후 출력하는 프로그램을 작성하시오. 즉, 첫 번째 문자를 R번 반복하고, 두 번째 문자를 R번 반복하는 식으로 P를 만들면 된다 www.acmicpc.net [JAVA] 기초적인 문자열 다루는 문제이다. 1. BufferedReader 로 입력 받고 2. 한 문자씩 다룰 수 있게 배열에 넣고 3. 반복하면서 StringBuffer에 담아 최종 출력하기 >> for문안에 new char[] 가 마음에 안들어서 밖으로 빼야겠다고 자꾸만 생각이 든다. import java.io.Buffer..

https://www.acmicpc.net/problem/1753 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가 www.acmicpc.net 풀이과정. 최단경로를 구하는 문제로 Queue에 간선을 넣어 순서대로 꺼내며 dp배열에 최단 경로를 갱신해나가면 된다고 생각했다. 허나 무수한 '시간초과' 로 상당히 애먹었던 문제. 그 이유는 '서로 다른 두 정점 사이에 여러 개의 간선이 존재할 수도 있음에 유의한다.' '유의'란 언급이 있다면 진짜 유의해야한다. 처음에 heapq를 사용하지도 않았다. 우선순..

백준 9184 동적계획법 - 신나는 함수 여행 문제 재귀 호출만 생각하면 신이 난다! 아닌가요? 다음과 같은 재귀함수 w(a, b, c)가 있다. if a 20, then w(a, b, c) returns: w(20, 20, 20) if a < b and b < c, then w(a, b, c) returns: w(a, b, c-1) + w(a, b-1, c-1) - w(a, b-1, c) otherwise it returns: w(a-1, b, c) + w(a-1, b-1, c) + w(a-1, b, c-1) - w(a-1, b-1, c-1) 위의 함수를 구현하는 것은 매우 쉽다. 하지만, 그대로 구현하면 값을 구하는데 매우 오랜 시간이 걸린다. (예를 들면, a=15, b=15, c=15) a, b,..

백준 10815 Map - 숫자 카드 >> 기본적인 중복제거를 위한 Map 사용 문제 파이썬에서는 'dict' 클래스를 사용하자 Map 은 순차적이지 않고 Key-Value 구조로 만든 데이터형식이며, Key값은 중복을 허용하지 않는 특성을 이용한다. 문제 숫자 카드는 정수 하나가 적혀져 있는 카드이다. 상근이는 숫자 카드 N개를 가지고 있다. 정수 M개가 주어졌을 때, 이 수가 적혀있는 숫자 카드를 상근이가 가지고 있는지 아닌지를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10,000,000보다 작..

백준 18870 정렬 - 좌표 압축 문제. 수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다. Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표의 개수와 같아야 한다. X1, X2, ..., XN에 좌표 압축을 적용한 결과 X'1, X'2, ..., X'N를 출력해보자. 입력. 첫째 줄에 N이 주어진다. 둘째 줄에는 공백 한 칸으로 구분된 X1, X2, ..., XN이 주어진다. 출력. 첫째 줄에 X'1, X'2, ..., X'N을 공백 한 칸으로 구분해서 출력한다. 제한. 1 ≤ N ≤ 1,000,000 -109 ≤ Xi ≤ 109 >> 몹시 문제가 불친절하다. 해당 숫자의 순위를 출력하는 문제. 서로 다른 좌표의 개수 ..

백준 11650 정렬 - 좌표 정렬하기 오답1. 시간초과 . 접근. 배열 2개 준비. 1. 배열1 을 정렬할 때 배열2도 배열1의 기준에 맞춰 같이 정렬 2. 배열1 을 for문으로 쭉 탐색하면서 정렬이 필요한 시작 번호, 끝 번호를 추려내어 배열2를 정렬. >> 정답은 도출하는 데에는 문제가 없지만 시간 초과가 떴다.. 이 문제는 노가다식의 방법으로 푸는 것이 아니다.. 어떤 방법으로 풀어야 할까?? import sys N=int(input()) arr=[] arr2=[] for _ in range(N): a,b=sys.stdin.readline().split() arr.append(a) arr2.append(b) s=100001 for i in range(0,N-1): for j in range(1,..