문제 1182번: 부분수열의 합 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net 문제 요약 N개의 정수로 된 수열에서 부분 수열을 뽑아낸 뒤, 부분 수열의 원소를 모두 더한 값이 입력값과 같은 경우의 수를 구하는 문제 문제 풀이 algorithm 헤더에 있는 prev_permutation() 함수를 사용했다. 이 함수를 사용한 이유는 다음과 같다. 중복 없이 N개의 정수로 된 수열을 조합하기 위해서 부분 수열의 원소 개수를 (1 ~ N)개까지 두고 조합하기 위해 먼저 N개의 정수로 된 수열을 벡터에 ..
전체 글
항공대 알고리즘 동아리 Koala 🥰
15657번: N과 M (8) (acmicpc.net) 15657번: N과 M (8) N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다. N개의 자연수 중에서 M개를 고른 수열 www.acmicpc.net 소스코드 문제풀이 자연수의 수 n과 n개의 자연수 중 고르게 될 자연수의 수 m을 입력 받음 n개의 자연수를 리스트로 입력 받음 고른 수열은 비내림차순이어야 하므로 리스트를 오름차순으로 정렬 자연수를 하나씩 append 또는 pop 할 것이므로 정답이 될 수열을 가지고 있을 빈 배열 생성 조건을 만족하는 수열을 생성해줄 fun() 함수 입력 받은 자연수 리스트 내에서 반복 정답인 수열을 가지고 있을 ..
https://www.acmicpc.net/problem/1942 1942번: 디지털시계 디지털시계는 일반적으로 시각을 “hh:mm:ss”의 형태로 표현한다. hh는 00 이상 23 이하의 값을, mm과 ss는 00 이상 59 이하의 값을 가질 수 있다. 이러한 형태의 시각에서 콜론(“:”)을 제거하면 “hhm www.acmicpc.net 문제 디지털시계는 일반적으로 시각을 “hh:mm:ss”의 형태로 표현한다. hh는 00 이상 23 이하의 값을, mm과 ss는 00 이상 59 이하의 값을 가질 수 있다. 이러한 형태의 시각에서 콜론(“:”)을 제거하면 “hhmmss”라는 정수를 얻을 수 있는데, 이러한 정수를 시계 정수라고 한다. 예를 들어, 오후 5시 5분 13초, 즉 17:05:13의 시계 정수는..
다익스트라를 사용해 푸는 문제 평범한 골드 5 문제라고 생각했다가 시간 초과 2번 맞고 다익스트라를 잘못 이해하고 있었단 걸 알았다. 시간 초과의 원인 https://www.acmicpc.net/board/view/34516 7번 항목을 고려하지 않고 코드를 작성했기 때문에 시간 초과를 받았다. 평소에는 저 부분을 고려하지 않고 풀어도 잘 통과했다. 하지만, 정점이 10만개가 되니, 불필요하게 탐색되는 정점의 수가 누적돼 시간 초과로 이어졌다. 어떻게 해결했나? 매우 간단하다. 기존 코드에 2줄만 추가하면 됐다. 문제의 코드 while q: hereC, here = heapq.heappop(q) for there, thereC in graph[here]: cost = thereC + hereC if di..
https://www.acmicpc.net/problem/16955 16955번: 오목, 이길 수 있을까? 구사과와 큐브러버는 10×10 크기의 바둑판에서 오목을 하고 있다. 턴은 구사과가 먼저 갖는다. 바둑판의 상태가 주어진다. 구사과가 턴을 한 번 더 가졌을 때, 이길 수 있는지 구하는 프로그램을 www.acmicpc.net 문제 코드 문제 풀이 함수를 사용하여 1) 좌측 위 + 우측 아래, 2) 가운데 위 + 가운데 아래, 3) 우측 위 + 좌측 아래, 4) 좌 + 우 의 좌표를 비교함. 반복문을 실행, x,y = 0,0 부터 x,y = 10,10 까지 '.' 인 좌표를 찾아서 그 좌표를 'X' 로 바꿔주고, 그 좌표를 포함하여 연속된 'X' 5개가 완성되는지 확인함. 한 좌표에서 모든 함수를 돌았..
문제 씬디는 애너그램(anagram) 프로그램을 만들어 줄 수 있는 남자를 좋아한다. 참고로 씬디는 매우 예쁘다. 애너그램 프로그램이란, 입력받은 영단어의 철자들로 만들 수 있는 모든 단어를 출력하는 것이다. 가령 "abc" 를 입력받았다면, "abc", "acb", "bac", "bca", "cab", "cba" 를 출력해야 한다. 입력받은 단어내에 몇몇 철자가 중복될 수 있다. 이 경우 같은 단어가 여러 번 만들어 질 수 있는데, 한 번만 출력해야 한다. 또한 출력할 때에 알파벳 순서로 출력해야 한다. 입력 첫째 줄에 단어의 개수 N 이, 둘째 줄부터 N개의 영단어가 들어온다. 영단어는 소문자로 이루어져 있다. 단어의 길이는 20보다 작거나 같고, 애너그램의 수가 100,000개 이하인 단어만 입력으..
https://www.acmicpc.net/problem/1182 1182번: 부분수열의 합 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net 문제 코드 코드해설 이 문제는 숫자들을 입력 받은 후 조합을 이용해 나올 수 있는 경우들의 합을 구해준다. 그 후 그 합이 우리가 원하는 숫자와 같다면 cnt변수를 하나씩 증가시키면서 마지막에 일치하는 경우를 출려해주면 된다.
문제 코드 p=list(input()) for i in range(len(p)): if ord(p[i])=65: #대문자 p[i]=chr((ord(p[i])-65+13)%26+65) elif ord(p[i])=97: #소문자 p[i]=chr((ord(p[i])-97+13)%26+97) else: p[i]=p[i] print(''.join(p)) 풀이 문자열을 입력받고 조건에 따라 13을 더해주기 위해 아스키코드로 바꿔주고 13 더해주고 26 나머지로 보고 다시 알파벳으로 바꾼다
문제 https://www.acmicpc.net/problem/1718 코드
https://www.acmicpc.net/problem/10026 10026번: 적록색약 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록) www.acmicpc.net 문제 분석 그림을 2차원 배열에 RGB값을 넣어서 주고, 배열 내에서 상하좌우에 같은 값이 있다면 하나의 구역으로 본다. 적록색약이 아닌 사람이 봤을 때 구역의 개수와 적록색약인 사람이 봤을 때의 구역의 개수를 구하는 문제이다. 코드 #include using namespace std; typedef long long ll; int N; char picture[100][100]; bool ..
https://www.acmicpc.net/problem/11655 문제 ROT13은 카이사르 암호의 일종으로 영어 알파벳을 13글자씩 밀어서 만든다. 예를 들어, "Baekjoon Online Judge"를 ROT13으로 암호화하면 "Onrxwbba Bayvar Whqtr"가 된다. ROT13으로 암호화한 내용을 원래 내용으로 바꾸려면 암호화한 문자열을 다시 ROT13하면 된다. 앞에서 암호화한 문자열 "Onrxwbba Bayvar Whqtr"에 다시 ROT13을 적용하면 "Baekjoon Online Judge"가 된다. ROT13은 알파벳 대문자와 소문자에만 적용할 수 있다. 알파벳이 아닌 글자는 원래 글자 그대로 남아 있어야 한다. 예를 들어, "One is 1"을 ROT13으로 암호화하면 "Ba..
https://www.acmicpc.net/problem/11575 11575번: Affine Cipher 서쪽나라에서 특수훈련을 받은 정은이는 동쪽나라로 침투를 하게 되었다. 뛰어난 스파이였던 정은이는 동쪽나라의 정보를 입수하게 되었고 정보를 안전하게 서쪽나라로 전달하기 위해 아핀 암 www.acmicpc.net 문제분석 주어진 문자열을 다음 규칙에 따라 암호화 한다. a * (문자의 아스키코드) + b z의 아스키코드값을 넘어가면 넘긴만큼 a부터 더한다. 문제풀이 각각의 아스키코드값을 변경해주고 26으로 나눠서 나머지 값을 계산하면 되는 간단한 문제이지만, 시간초과가 걸렸다. 다음은 시간초과가 나온 코드이다. input = __import__('sys').stdin.readline T = int(in..