전체 글 (53) 썸네일형 리스트형 백준 17140 이차원 배열과 연산 파이썬 *추가* https://www.acmicpc.net/problem/17140 17140번: 이차원 배열과 연산 첫째 줄에 r, c, k가 주어진다. (1 ≤ r, c, k ≤ 100) 둘째 줄부터 3개의 줄에 배열 A에 들어있는 수가 주어진다. 배열 A에 들어있는 수는 100보다 작거나 같은 자연수이다. www.acmicpc.net 전 포스팅에서 R연산하고 C연산을 둘다 구현했는데 인터넷 서칭을 해보니 굳이 그럴 필요없이 zip(*s)를 통해 행과 열을 바꿀 수 있다는 것을 알았다... 이 방법을 사용하니 시간도 줄어들고 코드가 매우 간단해졌다. 오늘도 배워간다..(나중에 써먹어야겠다.) def R(s): #R연산을 해주는 함수 maxs=-1#행의 길이의 최댓값 for i in range(len(s)): s2=[.. 백준 17140 이차원 배열과 연산 파이썬 https://www.acmicpc.net/problem/17140 17140번: 이차원 배열과 연산 첫째 줄에 r, c, k가 주어진다. (1 ≤ r, c, k ≤ 100) 둘째 줄부터 3개의 줄에 배열 A에 들어있는 수가 주어진다. 배열 A에 들어있는 수는 100보다 작거나 같은 자연수이다. www.acmicpc.net 처음 이 문제를 봤을때 dic를 쓸까 생각했지만 사용하기 어려워 list와 set을 사용해 풀었다. 시간초과나 메모리초과가 나오는 것인지 떨리면서 제출했는데 생각보다 시간이 별로 안 걸려서 놀랐다. 여러 시행착오가 있었지만 AC받았다. 실수 1. dp배열에 크기를 작게 해줘서 index에러가 났다. K 백준 1068 트리 파이썬 https://www.acmicpc.net/problem/1068 1068번: 트리 첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다. 만약 부모가 없다면 (루트) -1이 주어진다 www.acmicpc.net 일반적인 dfs탐색으로 문제를 풀어봤다. def dfs(y): global re if g[y]==[-1]:#삭제 노드로 접근하면 return return for i in g[y]: if not vist[i]:#g[y]에 있는 노드로 접근 vist[i]=True if g[i]==[]:#i 노드가 리프 노드이니 re+=1 re+=1 dfs(i)#리프 노드가 아닐 수 있으니 dfs(i)를 해줌으로.. 백준 2417 정수 제곱근 파이썬 https://www.acmicpc.net/problem/2417 2417번: 정수 제곱근 정수가 주어지면, 그 수의 정수 제곱근을 구하는 프로그램을 작성하시오. www.acmicpc.net 처음 이 문제를 봤을때 그냥 제곱근을 사용하면 되겠다라고 생각해 math.sqrt 와 math.isqrt를 사용해 아래와 같이 코드를 만들었다. import math n=int(input()) if float(math.isqrt(n))== math.sqrt(n): #isqrt는 정수형을 내보낸다. print(math.isqrt(n))#math.isqrt(n)**2==n이라는 소리니(제곱수) 그대로 출력 else: print(math.isqrt(n)+1)#제곱수가 아닌 제곱근이 소수를 가지므로 +1해준 뒤 출력 하지만.. 백준 10986 나머지 합 파이썬 https://www.acmicpc.net/problem/10986 10986번: 나머지 합 수 N개 A1, A2, ..., AN이 주어진다. 이때, 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 구하는 프로그램을 작성하시오. 즉, Ai + ... + Aj (i ≤ j) 의 합이 M으로 나누어 떨어지는 (i, j) www.acmicpc.net N의 크기가 10**6이라 일반적으로 반복문을 돌려서 찾기에는 무리가 있어 누적합을 이용한 방법을 알아보다. 길이가 M개인 배열을 만든 뒤(DP) 입력 받은 리스트를 누적합을 해주고 M으로 나눈 나머지를 DP에 더해주면 DP[s[i]%M] +1 나머지의 목록이 나오는 것을 확인 할 수 있다. 나머지가 같은 누적합을 빼준다면 나머지가 0이 되기에 나머.. 백준 2573 빙산 파이썬 (DFS) https://www.acmicpc.net/problem/2573 2573번: 빙산 첫 줄에는 이차원 배열의 행의 개수와 열의 개수를 나타내는 두 정수 N과 M이 한 개의 빈칸을 사이에 두고 주어진다. N과 M은 3 이상 300 이하이다. 그 다음 N개의 줄에는 각 줄마다 배열의 각 행을 www.acmicpc.net 전형적인 DFS방법으로 풀 수 있는 방법이다 0이 아닌곳을 발견하면 상하좌우로 0의 개수를 찾고 빼주면 되기 때문이다. 이때 한가지 주의 할점은 빼준 곳이 0이 되서 바로 옆자리가 0을 한번 더 카운트 하는 경우만 조심해주면 된다.(빙산은 하루를 기준으로 녹기때문에 같이 녹는다. 예제 그럼에서 처음 2가 0이 되는데 바로 옆에 있는 4가 2가 되는것을 보면 알 수 있다.) 해결 방법으로 df.. 백준 16139 인간-컴퓨터 상호작용 파이썬 https://www.acmicpc.net/problem/16139 16139번: 인간-컴퓨터 상호작용 첫 줄에 문자열 $S$가 주어진다. 문자열의 길이는 $200,000$자 이하이며 알파벳 소문자로만 구성되었다. 두 번째 줄에는 질문의 수 $q$가 주어지며, 문제의 수는 $1\leq q\leq 200,000$을 만족한다. 세 번째 www.acmicpc.net 처음 이 문제를 봤을 때 범위만큼 문자열을 잘라서 입력받은 문자의 개수를 세주면 되겠다고 생각했지만 실버 1인데 그렇게 간단할 리가 없다고 생각해 누적합을 사용해 보기로 했다. a~z까지 리스트를 처음 문자열의 길이만큼 만드면 i 번째에 있는 a~z까지의 리스트의 숫자는 0~i번째까지 나온 횟수이다. 처음에는 2차원 배열의 크기가 커 메모리 초과 .. 백준 1987 알파벳 파이썬 https://www.acmicpc.net/problem/1987 1987번: 알파벳 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으 www.acmicpc.net 처음 봤을때는 어려워 보였지만 DFS함수가 몇번 돌아갔는지, 현재 문자가 무엇인지만 저장해주고 백트레킹을 첨가해주면 것을 제외하면 간단한 DFS문제였다. 시간 제한을 꽉꽉채워서 AC받았다. 나중에는 다른 풀이법으로 풀어봐야겠다. import sys sys.setrecursionlimit(10**5) def dfs(i,j,c,d): global maxs maxs = max(c,maxs) fo.. 이전 1 ··· 3 4 5 6 7 다음