티스토리

jieun log

검색하기

블로그 홈

jieun log

kimmjieun.tistory.com/m

징늬2 님의 블로그입니다.

구독자: 2

방명록 방문하기

반응형

주요 글 목록

[python 파이썬] 백준 4963번 섬의 개수 https://www.acmicpc.net/problem/4963 4963번: 섬의 개수 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다. 둘째 줄부터 h개 줄에는 지도 www.acmicpc.net 처음 딱 접했을 때 문제는 "이것이 취업을 위한 코딩테스트다"에 실린 음료수얼려먹기 문제와 유사했다. 하지만 조금 다른 점이 있다. 핵심 1. 덩어리 개수를 구할 것 2. 상하좌우로 움직일 수 있을 뿐만 아니라 대각선 방향으로도 움직일 수 있다. 음료수얼려먹기 문제가 dfs로 풀려서 나도 dfs로 처음에 구현했다. 근데 여론을 보니 dfs와 bfs 모두 가능하다고 한다. 따라서 두가지 방법으.. 공감수 2 댓글수 0 2021. 5. 13.
[python 파이썬] 백준 2312번 수 복원하기 www.acmicpc.net/problem/2312 2312번: 수 복원하기 첫째 줄에 테스트 케이스의 수가 주어진다. 각 테스트 케이스마다 양의 정수 N (2 ≤ N ≤ 100,000)이 주어진다. www.acmicpc.net 문제풀이법 1) 소인수분해하는 코드 num = int(sys.stdin.readline()) su = 2 # 검사할 첫 값 so = [] # 소인수 저장할 리스트 변수 while su collections 라이브러리의 Counter 함수 사용하여 dictionary 형태로 값을 받고 반복문으로 출력한다. dict = collections.Counter(so) for key in dict: print(key, dict[key]) 참고자료 1. 소인수분해 blog.daum.net/s.. 공감수 0 댓글수 0 2021. 5. 8.
[python 파이썬] 백준 5347번 LCM www.acmicpc.net/problem/5347 5347번: LCM 첫째 줄에 테스트 케이스의 개수 n이 주어진다. 다음 n개 줄에는 a와 b가 주어진다. a와 b사이에는 공백이 하나 이상 있다. 두 수는 백만보다 작거나 같은 자연수이다. www.acmicpc.net 최소공배수 구하는 문제이다 라이브러리를 사용하면 쉽게 풀 수 있는 문제다 from math import gcd def lcm(x,y): return x*y // gcd(x,y) # 최대공약수 n = int(input()) for _ in range(n): a,b = map(int,input().split()) print(lcm(a,b)) brownbears.tistory.com/454 [Python] 최대공약수, 최소공배수, N개의 최소.. 공감수 0 댓글수 0 2021. 5. 8.
[python 파이썬] 백준 2010번 플러그 www.acmicpc.net/problem/2010 2010번: 플러그 첫째 줄에 멀티탭의 개수 N이 주어진다. (1 ≤ N ≤ 500,000) 이어서 둘째 줄부터 N개의 줄에 걸쳐 각 멀티탭이 몇 개의 플러그를 꽂을 수 있도록 되어 있는지를 나타내는 자연수가 주어진다. 이 자연 www.acmicpc.net 입력을 input() 으로 받으면 시간초과가 난다. 따라서 입력을 sys.stdin.readline() 공감수 0 댓글수 0 2021. 5. 8.
[python 파이썬] 백준 10610번 30 www.acmicpc.net/problem/10610 10610번: 30 어느 날, 미르코는 우연히 길거리에서 양수 N을 보았다. 미르코는 30이란 수를 존경하기 때문에, 그는 길거리에서 찾은 수에 포함된 숫자들을 섞어 30의 배수가 되는 가장 큰 수를 만들고 싶어한 www.acmicpc.net 30의 배수이려면 1) 일의 자리수가 무조건 0이어야함 2) 각 자리수의 합이 3으로 나누어 떨어져야함 n = list(input()) n.sort(reverse=True) sum =0 for i in n: sum += int(i) if sum%3!=0 or "0" not in n: print(-1) else: print("".join(n)) 새로운 개념) n = list(input()) 입력받은 문자열을 한자리.. 공감수 0 댓글수 0 2021. 5. 8.
[python 파이썬] 백준 2875번 대회 or 인턴 www.acmicpc.net/problem/2875 2875번: 대회 or 인턴 첫째 줄에 N, M, K가 순서대로 주어진다. (0 ≤ M ≤ 100, 0 ≤ N ≤ 100, 0 ≤ K ≤ M+N), www.acmicpc.net 수학문제 여자가 2명이상일 때 남자가 1명이상일 때 팀에 참여할 3명을 제외하고 남는 인원이 k명 이상일 때 팀을 꾸리는 방법을 반복문을 사용해서 구현하면 된다. n,m,k = map(int,input().split()) team = 0 while n >=2 and m >=1 and n+m-3>=k : n -=2 m -=1 team +=1 print(team) blog.naver.com/baek2sm/221861500911 공감수 0 댓글수 0 2021. 5. 8.
[python 파이썬] 백준 6996번 애너그램 www.acmicpc.net/problem/6996 6996번: 애너그램 첫째 줄에 테스트 케이스의 개수( list(a) - 리스트형태로 바꾼 listA와 listB가 동일한지 따지기 위해 정렬후에 비교함 ghdwn0217.tistory.com/58 문자열(string)을 한 글자씩 끊어서 리스트로 바꾸기 1 2 str="2019년은 기해년. Happy New Year!" print(list(str)) cs 실행 결과 >>['2', '0', '1', '9', '년', '은', ' ', '기', '해', '년', '.', ' ', 'H', 'a', 'p', 'p', 'y', ' ', 'N', 'e', 'w', ' ', 'Y'.. ghdwn0217.tistory.com 공감수 0 댓글수 0 2021. 5. 4.
[python 파이썬] 백준 1427번 소트인사이드 www.acmicpc.net/problem/1427 1427번: 소트인사이드 첫째 줄에 정렬하고자하는 수 N이 주어진다. N은 1,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net n = int(input()) lists = [] while True: lists.append(n%10) n = n // 10 if n ==0: break lists.sort(reverse=True) result="".join(map(str,lists)) print(result) 간단한 문제 "".join(map(str, a)) 을 활용하면 금방 풀 수 있다. www.delftstack.com/ko/howto/python/how-to-convert-a-list-to-string/ 파이썬에서리스트를 .. 공감수 0 댓글수 0 2021. 5. 4.
[python 파이썬] 백준 10814번 나이순 정렬 www.acmicpc.net/problem/10814 10814번: 나이순 정렬 온라인 저지에 가입한 사람들의 나이와 이름이 가입한 순서대로 주어진다. 이때, 회원들을 나이가 증가하는 순으로, 나이가 같으면 먼저 가입한 사람이 앞에 오는 순서로 정렬하는 프로그램을 www.acmicpc.net n = int(input()) lists = [] for _ in range(n): a,b = input().split() a=int(a) lists.append([a,b]) lists.sort(key=lambda x : x[0]) for i in range(n): print(lists[i][0],lists[i][1]) 오랜만에 짜니까 헷갈렸다. 딕셔너리를 사용해서 key, value로 처리할까 했는데 2차원리스트를.. 공감수 0 댓글수 0 2021. 5. 4.
[python 파이썬] 백준 2869번 달팽이는 올라가고 싶다 www.acmicpc.net/problem/2869 2869번: 달팽이는 올라가고 싶다 첫째 줄에 세 정수 A, B, V가 공백으로 구분되어서 주어진다. (1 ≤ B =v: break sum -= b print(count) 하지만 시간초과에 걸릴 것 같음을 암시했고 역시 시간초과가 나왔다. 다른 방법을 생각해봤다. import math a,b,v = map(int,input().split()) count = (v-b)/(.. 공감수 0 댓글수 0 2021. 4. 22.
[python 파이썬] 백준 7569번 토마토 www.acmicpc.net/problem/7569 7569번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, www.acmicpc.net 7576번 토마토와 비슷한문젠데 z축을 추가해서 풀면된다. from collections import deque m, n, h = map(int, input().split()) a = [[list(map(int, input().split())) for i in range(n)] for depth in range(h)] dx = [-1, 0, 1, 0, 0, 0] dy = [0, 1, 0,.. 공감수 0 댓글수 0 2021. 3. 15.
[python 파이썬] 백준 7576번 토마토 www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net from collections import deque m, n = map(int, input().split()) a = [list(map(int, input().split())) for i in range(n)] dx = [-1, 1, 0, 0] # 좌 우 상 하 dy = [0, 0, 1, -1] # 좌 우 상 하 de = deque() def bfs(): while len(de) != 0: x.. 공감수 0 댓글수 0 2021. 3. 15.
[python 파이썬] 백준 2583번 영역 구하기 www.acmicpc.net/problem/2583 2583번: 영역 구하기 첫째 줄에 M과 N, 그리고 K가 빈칸을 사이에 두고 차례로 주어진다. M, N, K는 모두 100 이하의 자연수이다. 둘째 줄부터 K개의 줄에는 한 줄에 하나씩 직사각형의 왼쪽 아래 꼭짓점의 x, y좌표값과 오 www.acmicpc.net 이 문제는 2667번 단지번호 붙이기 문제와 비슷하다고 생각했다. 2차원배열을 만들어주는 방식만 다르고 탐색하고 덩어리갯수와 덩어리 크기를 구하는 문제였기 때문이다. 좌표를 입력받으면 이차원배열 채우기가 애매하다고 생각이 들 수 있는데 영역을 거꾸로 돌린채로 풀어도 된다. 그래서 풀어봤는데 틀렸습니다가 떴당.. m,n,k = map(int,input().split()) graph = [[0].. 공감수 0 댓글수 0 2021. 3. 14.
[python 파이썬] 백준 2644번 촌수계산 www.acmicpc.net/problem/2644 2644번: 촌수계산 사람들은 1, 2, 3, …, n (1≤n≤100)의 연속된 번호로 각각 표시된다. 입력 파일의 첫째 줄에는 전체 사람의 수 n이 주어지고, 둘째 줄에는 촌수를 계산해야 하는 서로 다른 두 사람의 번호가 주어진 www.acmicpc.net 처음에 이 문제를 봤을 때 트리구조를 생각했다. 트리구조로 푸려고 하니 도저히 아이디어가 안떠올랐다. 찾아보니 이 문제는 시작지점부터 목표지점까지 몇번 거쳐야하는지 생각하는 단순 탐색 문제였다. bfs로 입력받은 값 기준으로 시작해서 연결되어있는 곳을 찾아 +1씩 더해나가면 문제를 풀 수 있다. 이 문제에서는 인접리스트를 적용하여 풀었다. from collections import deque im.. 공감수 0 댓글수 0 2021. 3. 10.
[python 파이썬] 백준 1012번 유기농배추 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net 이 문제는 보아하니 2667번 단지번호붙이기할 때 참고했던 음료수 얼려먹기문제(DFS)와 유사했다. 2667번 문제풀이링크를 참고하겠다. 공감수 0 댓글수 0 2021. 3. 9.
[python 파이썬] 백준 12813번 이진수연산 12813번: 이진수 연산 총 100,000 비트로 이루어진 이진수 A와 B가 주어진다. 이때, A & B, A | B, A ^ B, ~A, ~B를 한 값을 출력하는 프로그램을 작성하시오. www.acmicpc.net 이문제는 비트마스크 문제이다. 기본적인 비트연산자를 이용한 문제인데 not 연산자를 파악하는 데 시간이 걸렸다. 일반적인 not 연산자(~)를 쓰면 결과가 0b0100 -> -0b0101 이런식으로 나와서 not연산자를 사용하지 못했다. 그래서 1의 보수쓰는 법으로 풀었다. ~a를 구하기 위해서 (a가 세자리라면) a^111(mask) 이렇게 xor 연산을 사용해 구하면 된다. ex) a=101 101^111=010 mask값을 구하기 위해서는 이진수가 길이를 알아야하는데 문제에서 1000.. 공감수 0 댓글수 1 2021. 3. 2.
[python 파이썬] 백준 11723번 집합 11723번: 집합 첫째 줄에 수행해야 하는 연산의 수 M (1 ≤ M ≤ 3,000,000)이 주어진다. 둘째 줄부터 M개의 줄에 수행해야 하는 연산이 한 줄에 하나씩 주어진다. www.acmicpc.net 이 문제는 비트마스크를 이용한 문제라고 하는데 어디에 어떻게 적용해야할지 감이 안잡혀서 생각나는대로 풀어봤다. 비트마스크 문제들도 여러개 접해보자. 풀이1 - 시간초과 이렇게 푸니까 시간초과가 나왔다 m = int(input()) S=set() #집합자료형 for _ in range(m): tmp = input().split() if len(tmp)==1: if tmp[0]=='all': s=set([i for i in range(1,21)]) else: s=set() continue a,b=tmp.. 공감수 0 댓글수 0 2021. 3. 2.
[python 파이썬] 백준 2667번 단지번호붙이기 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net 나는 코딩테스트 이론 공부를 '이것이 취업을 위한 코딩테스트다' 라는 책으로 하고 있다. 이 2667번 문제는 DFS/BFS 챕터에 있던 음료수 얼려먹기문제(DFS)와 유사했다. (검색하면 나옴) (음료수얼려먹기 문제 답) n=int(input()) graph=[] for i in range(n): graph.append(list(map(int,input()))) def dfs(x,y): #주어진 범위를 벗어나는 경우에 즉시 종료 if x = n or y = n:.. 공감수 0 댓글수 0 2021. 2. 25.
[python 파이썬] 백준 2606번 바이러스 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어 www.acmicpc.net 이 문제는 대표적인 BFS 문제이다. 앞서 푼 1260번에서 사용한 BFS함수를 응용해서 풀었더니 쉽게 풀렸다! n = int(input()) m = int(input()) matrix=[[0]*(n+1) for i in range(n+1)] for i in range(m): a,b = map(int,input().split()) matrix[a][b]=matrix[b][a]=1 visit_list=[1]*(n+1) def bfs(v): count=0 queue=[v.. 공감수 0 댓글수 0 2021. 2. 25.
[python 파이썬] 백준 1260번 DFS와 BFS 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 이문제는 DFS와 BFS를 이용해서 탐색하는 문제이다. DFS는 깊이탐색, 이어달리기, 한 정점에서 다른 정점 그리고 그 정점에 이어진 정점에 연결하는 느낌 BFS는 너비탐색, 한정점과 이어진 모든 정점을 들른 후에 다음 연결된 정점도 마찬가지로 한다. DFS에서는 재귀를 사용한다. 코드는 다음과 같다 n,m,v=map(int,input().split()) matrix=[[0]*(n+1) for i in range(n+1)].. 공감수 0 댓글수 0 2021. 2. 23.
[python 파이썬] 백준 2178번 미로탐색 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 이 문제는 BFS로 풀어야하는 문제이다. 설명은 코드와 함께 하겠다! from collections import deque n,m=map(int,input().split()) graph=[] for i in range(n): graph.append(list(map(int,input()))) dx=[-1,1,0,0] dy=[0,0,-1,1] def bfs(x,y): #큐 구현위해 deque라이브러리 사용 queue = deque() queue.append((x,y)) #queue가 빌때까지 반복.. 공감수 0 댓글수 0 2021. 2. 23.
[python 파이썬] 백준 2003번 수들의 합2 2003번: 수들의 합 2 첫째 줄에 N(1 ≤ N ≤ 10,000), M(1 ≤ M ≤ 300,000,000)이 주어진다. 다음 줄에는 A[1], A[2], …, A[N]이 공백으로 분리되어 주어진다. 각각의 A[x]는 30,000을 넘지 않는 자연수이다. www.acmicpc.net 이 문제는 투포인터 개념과 관련된 문제이다. 투포인터의 개념을 알고 적용하는것이 중요하다! n,m = map(int, input().split()) A=list(map(int, input().split())) start=0 answer=0 end=0 while start 공감수 0 댓글수 0 2021. 2. 15.
[python 파이썬] 백준 11660번 구간합구하기5 11659번: 구간 합 구하기 4 첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j www.acmicpc.net 이 문제 또한 구간합을 이용한 문제고 2차원 배열에 적용한 것이었다. import sys input = sys.stdin.readline n, m = map(int, input().split()) graph = [list(map(int, input().split())) for _ in range(n)] dp = [[0] * n for _ in range(n)] dp[0][0] = graph[0][0] for i in range(1, n): .. 공감수 0 댓글수 0 2021. 2. 15.
[python 파이썬] 백준 11659번 구간합구하기 4 11659번: 구간 합 구하기 4 첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j www.acmicpc.net 풀이1 - 시간초과 import sys n,m = map(int,input().split()) nlist = list(map(int,sys.stdin.readline().split())) for _ in range(m): i,j = map(int,input().split()) sum=0 for i in range(i-1,j): sum+=nlist[i] print(sum) #시간초과 풀이2 - 정답 단순 sum으로 구하면 시간초과가 나와 왤까.. 공감수 0 댓글수 0 2021. 2. 15.
[python 파이썬] 백준 12865번 평범한 배낭 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net N,K = map(int, input().split()) weight = [0] gold =[0] for _ in range(N): w, g= map(int, input().split()) weight.append(w) gold.append(g) dp=[[0 for i in range(K+1)] for k in range(N+1)] for w in range(1, N+1): for i in rang.. 공감수 0 댓글수 0 2021. 2. 9.
[python 파이썬] 백준 1535번 안녕 1535번: 안녕 첫째 줄에 사람의 수 N( 공감수 0 댓글수 0 2021. 2. 9.
[python 파이썬] 백준 1739번 타일링 1793번: 타일링 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있으며, 숫자 0 ≤ n ≤ 250이 주어진다. www.acmicpc.net 얼핏보면 피보나치지만 문제의 조건에서 2*1 , 2*2 두가지 타일로 채울 수 있다고하여 수기로 채우는 방법을 적어보고 규칙을 찾아 풀었다 def cnt(n): fib=[0 for _ in range(n+1)] if n ==0 or n==1: return 1 fib[0]=1 fib[1]=1 for i in range(2,n+1): fib[i]=fib[i-1]+2*fib[i-2] return fib[n] while True: try: print(cnt(int(input()))) except: break 공감수 0 댓글수 0 2021. 2. 5.
[python 파이썬] 백준 2565번 파이썬 2565번: 전깃줄 첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결되는 www.acmicpc.net 이 문제는 정렬부터 했어야했는데 정렬을 생각해내지 못했다. 풀이법 1. A의 위치번호로 정렬하기 2. A에 연결된 B의 위치번호가 현재 가리키는 위치번호보다 위에 위치한 전깃줄의 최대 갯수에 +1 3. 전체에서 최대개수빼기 n = int(input()) line=[list(map(int,input().split())) for _ in range(n)] line.sort(key=lambda x :x[0]) dp=[0]*501 for s, d in line: dp[d]=m.. 공감수 0 댓글수 0 2021. 2. 5.
[python 파이썬] 백준 1965번 상자넣기 1965번: 상자넣기 정육면체 모양의 상자가 일렬로 늘어서 있다. 상자마다 크기가 주어져 있는데, 앞에 있는 상자의 크기가 뒤에 있는 상자의 크기보다 작으면, 앞에 있는 상자를 뒤에 있는 상자 안에 넣을 수가 www.acmicpc.net 메모이제이션과 점화식 그리고 max를 사용하면 되겠거니 했는데 max를 어떻게 적용해야할지 떠올리지못했다. 그리고 for문은 왜 하나만 쓰는거에 꽂혀서 이중포문으로 생각을 안했다. 첫번째 풀이 - 틀림 dp를 초기화하고 상자에 들어갈수있다면 1씩 늘려줬는데 1씩 늘려서 그런지 느릴 것이고 그래서 틀린 것 같다. n = int(input()) box = list(map(int,input().split())) dp=[0]*1001 for i in range(n): for j.. 공감수 0 댓글수 0 2021. 2. 2.
[python 파이썬] 백준 13301번 타일장식물 www.acmicpc.net/problem/13301 13301번: 타일 장식물 대구 달성공원에 놀러 온 지수는 최근에 새로 만든 타일 장식물을 보게 되었다. 타일 장식물은 정사각형 타일을 붙여 만든 형태였는데, 한 변이 1인 정사각형 타일부터 시작하여 마치 앵무조개 www.acmicpc.net dp=[0]*n 으로 하면 런타임에러 n = int(input()) dp = [0]*81 dp[0]=1 dp[1]=1 for i in range(2,n): dp[i] = dp[i-1]+dp[i-2] r = dp[n-1] + dp[n-1] + dp[n-2] print( r+r ) 근거 있는 이유를 만들자 공감수 0 댓글수 0 2021. 2. 2.

반응형

문의안내

티스토리
로그인
고객센터

티스토리는 카카오에서 사랑을 담아 만듭니다.