![]()
문제 & 링크https://www.acmicpc.net/problem/1644 풀이1. 에라토스테네스의 체를 이용하여 4,000,000까지의 모든 소수를 구해준다. (2부터 4,000,000까지 반복문을 이용하여 탐색한다. 탐색된 수 자기 자신을 제외한 모든 배수들을 bool 타입을 이용해서 체크한다.)2. 반복문을 마친 후 체크되지 않은 수들이 곧 소수이기에, 이를 따로 배열에 저장한다.3. 투 포인터(i = 0, j = 1)를 이용하여 해당 인덱스에 임시 연속합(tmp)을 만든다.4. N이 소수일 경우 cnt를 1 증가시킨다.5. 임시 연속합(tmp)이 N보다 클 경우 임시 연속합에서 i 인덱스에 해당하는 소수를 빼고, i를 증가시킨다.6. 임시 연속합(tmp)이 N보다 작을 경우 j를 증가시키고,..
![]()
https://www.acmicpc.net/problem/10451Algorithm순열이 주어졌을 때, 존재하는 사이클의 수를 출력하는 문제이다. 문제에서 주어지는 순열 순서대로 graph에 넣어주면 [[3], [2], [7], [8], [1], [4], [5], [6]] 와 같은 그래프가 만들어진다.우리는 존재하는 사이클의 수를 알고 싶기 때문에, bfs를 돌면서 모든 그래프를 방문할 때까지 시작점을 달리하여 반복해 주면 된다.cycle_cnt = 0 while (False in visited): start_p = visited.index(False) bfs(graph,start_p,visited) cycle_cnt+=1즉, 반복문을 통해 bfs를 돌린후에 ..
![]()
https://www.acmicpc.net/problem/1158 K번 쨰 수가 되기 직전까지 맨 앞의 원소를 K-1 번 꺼내오고(poll) 꺼내온 원소들을 맨 뒤로 넣는다.(offer)그리고 K번째로 뽑힌(poll) 원소는 출력하면 된다. import java.io.BufferedReader;import java.io.InputStreamReader;import java.io.IOException;import java.util.LinkedList;import java.util.Queue;import java.util.StringTokenizer; public class Main { public static void main(String[] args) throws IOException { Buf..
![]()
문제 풀이math 모듈을 이용하면 쉽게 최대공약수를 구할 수 있다.a, b의 최소공배수는 a * b / gcd(a, b)임을 이용한다코드
![]()
https://www.acmicpc.net/problem/15820알고리즘 분류구현result = ['Wrong Answer','Accepted','Why Wrong!!!']S1, S2 = map(int,input().split())state = 1lst1 = [list(map(int, input().split())) for _ in range(S1)]for i in lst1: if state == 0: break if i[0] == i[1]: state = 1 else: state = 0 lst2 = [list(map(int, input().split())) for _ in range(S2)]if not state == 0: for..
https://www.acmicpc.net/problem/13904문제웅찬이는 과제가 많다. 하루에 한 과제를 끝낼 수 있는데, 과제마다 마감일이 있으므로 모든 과제를 끝내지 못할 수도 있다. 과제마다 끝냈을 때 얻을 수 있는 점수가 있는데, 마감일이 지난 과제는 점수를 받을 수 없다. 웅찬이는 가장 점수를 많이 받을 수 있도록 과제를 수행하고 싶다. 웅찬이를 도와 얻을 수 있는 점수의 최댓값을 구하시오.입력/출력첫 줄에 정수 N (1 ≤ N ≤ 1,000)이 주어진다. 다음 줄부터 N개의 줄에는 각각 두 정수 d (1 ≤ d ≤ 1,000)와 w (1 ≤ w ≤ 100)가 주어진다. d는 과제 마감일까지 남은 일수를 의미하며, w는 과제의 점수를 의미한다. 얻을 수 있는 점수의 최댓값을 출력한다.코드f..
https://www.acmicpc.net/problem/1417문제다솜이는 사람의 마음을 읽을 수 있는 기계를 가지고 있다. 다솜이는 이 기계를 이용해서 2008년 4월 9일 국회의원 선거를 조작하려고 한다.다솜이의 기계는 각 사람들이 누구를 찍을 지 미리 읽을 수 있다. 어떤 사람이 누구를 찍을 지 정했으면, 반드시 선거때 그 사람을 찍는다.현재 형택구에 나온 국회의원 후보는 N명이다. 다솜이는 이 기계를 이용해서 그 마을의 주민 M명의 마음을 모두 읽었다.다솜이는 기호 1번이다. 다솜이는 사람들의 마음을 읽어서 자신을 찍지 않으려는 사람을 돈으로 매수해서 국회의원에 당선이 되게 하려고 한다. 다른 모든 사람의 득표수 보다 많은 득표수를 가질 때, 그 사람이 국회의원에 당선된다.예를 들어서, 마음을 ..
https://www.acmicpc.net/problem/2164문제N장의 카드가 있다. 각각의 카드는 차례로 1부터 N까지의 번호가 붙어 있으며, 1번 카드가 제일 위에, N번 카드가 제일 아래인 상태로 순서대로 카드가 놓여 있다.이제 다음과 같은 동작을 카드가 한 장 남을 때까지 반복하게 된다. 우선, 제일 위에 있는 카드를 바닥에 버린다. 그 다음, 제일 위에 있는 카드를 제일 아래에 있는 카드 밑으로 옮긴다.예를 들어 N=4인 경우를 생각해 보자. 카드는 제일 위에서부터 1234 의 순서로 놓여있다. 1을 버리면 234가 남는다. 여기서 2를 제일 아래로 옮기면 342가 된다. 3을 버리면 42가 되고, 4를 밑으로 옮기면 24가 된다. 마지막으로 2를 버리고 나면, 남는 카드는 4가 된다.N이 ..
![]()
https://www.acmicpc.net/problem/1100풀이1. 8줄에 걸쳐 문자열을 리스트로 받는다2. 행의 짝/홀에 따라 선별할 칸을 설정한다3. 해당하는 칸의 문자가 'F' 이면 cnt를 증가시킨다코드
![]()
문제 & 링크https://www.acmicpc.net/problem/9252 풀이1. dp 테이블을 0으로 초기화한다.2. 두 문자열을 dp 테이블의 1부터 시작하도록 반복문을 설정한다.3. 각 문자열의 원소가 같을 경우 dp[i][j]라면 dp[i-1][j-1]에서 1을 더해서 저장한다. 대각선의 값에서 1을 더하는 이유는 각 문자열에서 i번째 j번째 문자가 빠졌을 때 i-1번째, j-1번째 까지의 공통 부분 수열이 1 줄어야 하기 때문이다.4. 각 문자열의 원소가 다를 경우 dp[i][j]라면 dp[i-1][j]와 dp[i][j-1] 중 큰 값을 저장한다. 5. 3 - 4의 과정을 반복하며 dp 테이블의 마지막 원소에서 LCS의 길이를 구할 수 있다.6. dp 테이블의 마지막 원소(LCS의 길이)로..
![]()
문제 & 링크https://www.acmicpc.net/problem/1107 풀이1. 리모컨은 0 - 9까지 10개의 버튼을 가지고 있기에 길이가 10인 bool 자료형의 배열을 만들고, 입력받은 버튼을 true로 설정한다.2. 현재 채널이 100이기에 +, - 버튼만으로 원하는 채널에 도달할 때 누르는 횟수를 저장한다. 이때 음수값을 가질 수도 있으니 abs() 함수를 이용하여 양수로 저장한다.3. 이동하고자 하는 채널이 최대 500,000번 이기에 1,000,000번 채널에서 - 버튼을 누르는 경우도 생각하여 반복문을 수행한다.4. 해당 채널의 번호가 부서진 버튼을 포함하고 있는지 check 함수를 통해 확인한다. 이때 채널 번호를 string 형태로 바꾸고 한 글자 단위로 확인한다.5. 만약 채널..
![]()
https://www.acmicpc.net/problem/11728 문제풀이두 배열의 크기를 각각 A, B로 정의하고 정수값을 입력받습니다.A만큼 item으로 들어갈 정수를 a, B만큼 item으로 들어갈 정수를 b로 입력받습니다. a와 b를 더한 값을 combined라는 변수에 저장합니다.combined에 저장한 값을 정렬합니다.그 후 정렬된 값을 공백을 낀 채로 출력합니다.문제풀이A, B = map(int, input().split())a=list(map(int, input().split()))b=list(map(int, input().split()))combined=a+bsorted_arr=sorted(combined)print(' '.join(map(str, sorted_arr)))감사합니다.
