→

문제link: https://www.acmicpc.net/problem/30469두 소수 A, B를 입력받아 A로 시작하고 B로 끝나는 길이 N의 소수소수를 만드는 문제이다.소수소수는 해당 수 자체가 소수일 필요는 없지만 모든 연속된 두 자릿수가 소수인 수를 말한다. 접근처음에는 dfs를 활용해 코드를 작성했는데 시간 초과가 발생해 다른 방법으로 접근하기로 했다.아래 사진은 dfs로 코드를 짰을 때 만들었던 2차원 리스트의 내용물이다. 10 이상 99 이하의 소수를 저장한 목록인데, 십의 자리 숫자 인덱스로 접근할 수 있는 리스트에 일의 자리 숫자를 저장하도록 했다. 살펴 보니 두 자릿수 소수의 일의 자리 숫자는 1, 3, 7, 9 중 하나였다. 짝수일 경우 2의 배수이고 5로 끝나는 경우에는 5의 배수..

문제link: https://www.acmicpc.net/problem/11404n개의 도시와 m개의 버스가 있을 때, 모든 도시의 쌍 (A, B)에 대해서 도시 A에서 B로 가는데 필요한 비용의 최솟값을 구하는 문제이다. 접근플로이드-워셜 알고리즘을 활용했다.시작 도시와 도착 도시가 동일한 노선이 여러 개 존재할 수 있으므로 처음에 버스 정보를 입력받을 때 최솟값을 저장하도록 처리해야 한다. 코드import sysinput = sys.stdin.readlinen = int(input())m = int(input())costs = [[float('inf')]*(n) for _ in range(n)]for _ in range(m): a, b, c = map(int, input().split()) ..

문제link: https://www.acmicpc.net/problem/28422카드 게임을 진행했을 때 얻을 수 있는 최고 점수를 계산하는 문제이다.카드 게임의 규칙은 다음과 같다.N장의 카드 더미 맨 위에서부터 카드를 두 장 혹은 세 장씩 가져갈 수 있다.한 번에 가져간 카드들에 적힌 숫자를 XOR 연산하고, 연산한 값을 이진수로 변환했을 때 1의 개수만큼 점수를 획득한다.마지막에 카드 한 장이 남는다면 모든 점수를 잃고 0점으로 게임을 종료한다. 접근카드는 두 장 혹은 세 장씩만 가져갈 수 있으므로 N이 1인 경우에는 무조건 마지막에 카드 한 장이 남게 된다. 따라서 N이 1일 때는 0을 출력한다.N이 3 이하인 경우는 답을 직접 계산해 출력하도록 if문을 사용해 처리했고, 그 외에는 dp 리스트를..

문제link: https://www.acmicpc.net/problem/2075주어진 N*N 사이즈의 표에서 N번째로 큰 수를 찾아 출력하는 문제이다.표 내 모든 수는 열 안에서 오름차순 정렬되어있다.(표 내 모든 수는 자신의 한 칸 위에 있는 수보다 크다.) 접근처음에는 최대 힙을 통해 N번째 큰 수를 구하는 코드를 작성했다. 열별로 오름차순 정렬되어 있는 것에서 착안해 맨 밑 행을 일괄적으로 최대 힙에 넣은 후 '힙에서 pop->pop한 값의 한 칸 위 원소를 push' 동작을 반복했다. 그러나 메모리 초과가 발생했다.입력값을 2차원 리스트에 저장했던 게 원인인 것 같아 모든 값을 저장하지 않고 표를 한 줄씩 읽으며 처리하도록 변경했다. 최소 힙을 사용했고, 최소 힙의 크기를 N개로 유지하면서 pop..

문제link: https://www.acmicpc.net/problem/4378키보드에서 양손을 오른쪽으로 한 칸 이동한 채로 타자를 쳐서 만들어진 문장들을 입력받아 오류를 고쳐 출력한다.단어로 된 키(enter, tab, backspace 등)는 입력값에 포함되지 않으며, 공백은 동일하게 공백으로 처리한다. 접근딕셔너리를 이용해 오류를 고친 문장을 출력하도록 했다.입력이 여러 줄임에 유의해야 한다! 예제가 한 줄이라 이 점을 미처 확인하지 못하고 맨 처음에 틀린 답을 제출했다.그런데... 나의 경우 여러 줄을 입력받도록 처리한 후에도 출력 초과가 뜨는 문제가 발생했다.↓ 출력 초과가 발생했던 코드더보기import sysinput = sys.stdin.readlinekeyboards = dict()tmp..

문제link: https://www.acmicpc.net/problem/33709치매 예방 슬로건이 주어질 때 치매 예방 수칙의 개수를 구하는 문제이다.특수문자로 구분된 숫자들을 모두 합하면 치매 예방 수칙 개수를 구할 수 있다.., |, :, #의 네 가지 특수문자만 사용된다. 접근결론부터 말하자면 아래에 작성한 코드는 그다지 깔끔한 답안은 아니다ㅎㅎ 사용되는 네 종류의 특수문자 각각으로 if문을 만들어 해당 특수문자로 문자열을 구분한 후(split()을 사용했다) 숫자이면 더하고, 숫자가 아닌 경우(특수문자가 남아 있는 경우) 다음 특수문자를 기준으로 똑같은 행동을 반복한다. 다만 사용되는 특수문자가 4개인 점과 슬로건 길이가 1000 이하인 것을 고려했을 때 문제 해결에는 지장이 없을 것 같아 그냥..

문제link: https://www.acmicpc.net/problem/10026그림이 주어질 때, 적록색약이 아닌 사람이 봤을 때와 적록색약인 사람이 봤을 때의 구역 수를 각각 출력한다.그림에서는 R(적색), G(녹색), B(청색)의 세 가지 색상이 사용되며 같은 색상이 상하좌우로 인접해 있는 경우 같은 구역으로 본다. 적록색약인 사람의 눈에는 적색과 녹색이 같은 색으로 보인다. 접근BFS를 통해 문제를 해결했다. 적록색약이 아닌 경우와 적록색약인 경우를 각각 계산했다.(두 개의 while문으로 나누어 각각 계산했다.)방문했는지 체크하는 리스트 visited를 하나만 만들어서 사용했는데, 가독성 측면에서는 따로 만드는 것이 깔끔할 것 같다. 코드import sysfrom collections impor..

문제link: https://www.acmicpc.net/problem/26517함수 f(x) = ax + b (x k)가 주어질 때 함수가 x=k에서 연속인지 판별하는 문제이다.연속일 경우 Yes와 f(k)를, 연속이 아닐 경우 No를 출력한다. 접근ak + b == ck + d가 참이면 함수는 x=k에서 연속이다. 코드k = int(input())a, b, c, d = map(int, input().split())if a*k + b == c*k + d: print('Yes', a*k+b)else: print('No')

문제link: https://www.acmicpc.net/problem/33557두 수 A와 B가 주어졌을 때, A×B 세로식 곱셈에서 받아올림을 하지 않고 바로 결과에 적는 잘못된 방식의 결과가 실제 곱셈 결과와 같은지를 판단하는 문제이다.위 사진과 같이 자릿수가 같은 것끼리 곱한 후 결과를 바로 아래에 적는 식으로 숫자를 나열한다. 이것이 일반 곱셈 결과와 같으면 1, 다르면 0을 출력한다.자릿수가 짧은 수의 자리가 비어 있는 경우(ex: 위 사진에서 천만 자리 수) 수를 그대로 적는다. 접근두 수를 int가 아닌 str 형식으로 받아 한 자리씩 읽으며 곱하는 식으로 잘못된 곱셈 결과를 도출했다. 자릿수가 짧은 수는 자릿수가 긴 수와 길이가 같아지도록 앞을 1로 채워 준 후 사용한다.자릿수가 짧은 수..

문제link: https://www.acmicpc.net/problem/1268학생의 수와 학생들이 1학년부터 5학년까지 몇 반이었는지가 제시된다. 한 번이라도 같은 반이 된 적 있는 학생 수가 가장 많은 학생을 임시 반장으로 선출하려 할 때, 임시 반장이 될 학생의 번호를 출력하는 문제이다.임시 반장이 될 수 있는 학생 수가 여러 명인 경우 가장 작은 번호를 출력한다. 접근한 번이라도 같은 반이 된 적 있는 학생 수를 세야 하므로, 한 사람과 1학년부터 5학년까지 쭉 같은 반이었든 1학년 때만 같은 반이었든 동일하게 취급한다.또, 임시 반장이 될 수 있는 학생 수가 여러 명인 경우 가장 작은 번호를 출력해야 한다. (모든 학생의 한 번이라도 같은 반이 된 적 있는 학생 수가 같을 때는 1번을 출력해야 ..