본문 바로가기

알고리즘44

[Java] 프로그래머스 > 폰켓몬 https://programmers.co.kr/learn/courses/30/lessons/1845 코딩테스트 연습 - 폰켓몬 당신은 폰켓몬을 잡기 위한 오랜 여행 끝에, 홍 박사님의 연구실에 도착했습니다. 홍 박사님은 당신에게 자신의 연구실에 있는 총 N 마리의 폰켓몬 중에서 N/2마리를 가져가도 좋다고 했습니다. programmers.co.kr class Solution { public int solution(int[] nums) { int answer = 0; int n = 0; for(int i=0;i=nums.length/2) break; } return answer; } } 첫번째 원소를 기준으로 배열 값들과 비교하고 같지 않으면 answer+1을 해주고 같으면 다시 검색하도록 구현하였다. 단.. 2021. 12. 31.
[Java] 백준 9251번 LCS https://www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net LCS(Longest Common Subsequence) 란 최장 공통부분 수열을 의미한다. 예제에서 ACAYKP, CAPCAK의 LCS는 ACAYKP CAPCAK 이다. 테이블을 그려 이해해보자. 테이블을 그리면 다음과 같다. 규칙을 찾아보면 1) x번째 원소와 y번째 원소의 값이 같을 때 C의 경우, AC와 C의 공통부분은 {C} 하나로 길이가 1이.. 2021. 11. 9.
[Java] 백준 11054번 가장 긴 바이토닉 부분 수열 https://www.acmicpc.net/problem/11054 11054번: 가장 긴 바이토닉 부분 수열 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000) www.acmicpc.net 바이토닉 수열이란 특정값을 기준으로 왼쪽은 오름차순, 오른쪽은 내림차순인 수열을 말한다. LIS(최장 증가 부분 수열) 문제와 비슷하다. 왼쪽과 오른쪽으로 각각 탐색하여 더하고 중복을 빼면 된다. 다음은 예제 입력인 {1 5 2 1 4 3 4 5 2 1} 수열에서 왼쪽, 오른쪽 각각 LIS를 탐색한 결과이다. 두 수열을 합친 결과이다. 수열을 합친 후 자기 자신이 중복되어 있으므로 -1을 해주어 결과를 구한다. 따라.. 2021. 11. 9.
[Java] 프로그래머스 > 모의고사 https://programmers.co.kr/learn/courses/30/lessons/42840 코딩테스트 연습 - 모의고사 수포자는 수학을 포기한 사람의 준말입니다. 수포자 삼인방은 모의고사에 수학 문제를 전부 찍으려 합니다. 수포자는 1번 문제부터 마지막 문제까지 다음과 같이 찍습니다. 1번 수포자가 찍는 programmers.co.kr 문제 설명 수포자 삼인방은 모의고사에 수학 문제를 전부 찍으려 한다. 수포자는 1번 문제부터 마지막 문제까지 다음과 같이 찍습니다. 1번 수포자가 찍는 방식: 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, ... 2번 수포자가 찍는 방식: 2, 1, 2, 3, 2, 4, 2, 5, 2, 1, 2, 3, 2, 4, 2, 5, ... 3번 수포자가 찍는 방식.. 2021. 8. 29.
[python] 백준 1920번 수 찾기 https://www.acmicpc.net/problem/1920 1920번: 수 찾기 첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들 www.acmicpc.net def bin_search(a,key): start=0 end=len(a)-1 while starta[mid]: start= mid+1 else: end=mid-1 if start > end: return 0 n=int(input()) N=list(map(int,input().split())) N.sort() m=int(input()) M=list(.. 2021. 5. 5.
[python] 백준 2750번 수 정렬하기 https://www.acmicpc.net/problem/2750 2750번: 수 정렬하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 숫자가 주어진다. 이 수는 절댓값이 1,000보다 작거나 같은 정수이다. 수는 중복되지 않는다. www.acmicpc.net ls =[] n= int(input()) for i in range(0,n): ls.append(int(input())) for j in range(0,n): for k in range(0,n): if ls[j] 2021. 5. 4.

티스토리툴바