흐름 제어할때 자주 사용하는 구문들이다. break 반복문을 중단하고 싶을때 사용한다. 반복문 하나만 빠져나온다. 다중 반복문의 경우 전부다 나오는게 아닌 가까운 반복문 에서만 나옴. for i in range(1,6): if i == 3: break print(i) 출력 1 2 continue 해당 반복은 종료하고 다음 반복을 실행한다. 아래와 같이 i가 3인 경우 해당 루프를 종료하고 i = 4로 넘어간다. for i in range(1,6): if i == 3: continue print(i) 출력 1 2 4 5 pass 반복문, 함수, if문에서 비워두고 싶을때 사용한다. if문이나 함수등에 아무것도 작성이 안되어있으면 에러가 발생하므로 pass를 사용한다. 나중에 구현할때 그냥 넘어가는 용도로 ..
파이썬에서 대표적인 자료구조로 list, set, tuple, dictionary가 존재한다. ps에 초점을 맞춰 정리하는 느낌으로 작성했다. list (리스트) 변경 가능(mutable) 순서 존재(iterable) 리스트안에 객체들 중복 가능 arr = [] #리스트 선언 arr2 = list() #리스트 선언2 arr.append(1) # 1 값 추가 가장 오른쪽에 넣는거임 arr.insert(2, 2) # index 2에 2 값 추가 arr.remove(1) # 값이 1인거 삭제 del arr[1] # index 1에 있는 값 삭제 arr.pop() # 가장 왼쪽에 있는 값 삭제 및 return arr.extend(arr2) # 리스트와 리스트 합치기 arr += arr2 # 리스트와 리스트 합치..
https://www.acmicpc.net/problem/1644 1644번: 소수의 연속합 첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 4,000,000) www.acmicpc.net 저번에 푼 부분합 문제의 소수 버전. 비슷한 문제여서 금방 해결 가능했다. 아이디어 1. 소수 찾기 시간 복잡도가 빠른 에라토스테네스의 체 방법으로 소수를 찾았다. 2. 소수의 연속합 부분합 문제와 유사하게 투 포인터를 사용해서 경우의 수를 찾았다. 전체 코드 import math n = int(input()) if n == 1: print(0) exit(0) arr = [True] * (n + 1) arr[0] = False arr[1] = False for i in range(2, int(math.sqrt(n)+..
https://www.acmicpc.net/problem/9466 9466번: 텀 프로젝트 이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 있을 www.acmicpc.net 시간제한 3초로 매우 길지만 너무 복잡하지 않은 문제. 아마 테스트 케이스가 여러 개라서 시간제한을 널널하게 둔 거 같다. 아이디어 1. 그래프 일단 보자마자 그래프를 써야 한다고 생각했다. 문제 조건에서 팀이 되려면 서로가 꼬리를 물듯 사이클이 생겨야 한다. 그럼 이 문제는 그래프에서 '사이클을 어떻게 찾고 판별하냐'에 대해서 생각하면 된다. 2. dfs 방문 유무를 통해 사이클이 생겼는지 안 생겼는..
https://www.acmicpc.net/problem/1806 1806번: 부분합 첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다. www.acmicpc.net 아이디어 1. 부분합 사용 부분합에 대해 간단히 얘기해보면 0 ~ N까지의 합을 미리 구해두고 합의 차((0 ~ b까지 합) - (0 ~ a까지 합))를 통해 a부터 b까지 수의 합을 빠르게 구하는 방법이다. 그래서 for문을 사용해서 길이가 1일 때, 2일 때... N일 때 부분합의 값을 구해보며 S값이 넘는 순간 프로그램을 종료하도록 코드를 짰다. 당연하게도 시간 초과가 떴다. ..
https://www.acmicpc.net/problem/1504 1504번: 특정한 최단 경로 첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존 www.acmicpc.net 아이디어 1. 가중치가 있는 그래프 다익스트라 아니면 플로이드 두 개를 생각했다. 두정점 v1, v2를 지나는 최단경로는 각각의 최단경로들을 더한 것과 같으므로 다익스트라를 여러 번 사용하면 된다. '1 -> N' = '1 -> v1' + 'v1 -> v2' + 'v2 ->N' 같이 계산해서 두 정점을 지나는 최단경로를 구한다. 루트는 1 -> v1 -..
https://www.acmicpc.net/problem/12100 12100번: 2048 (Easy) 첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2 www.acmicpc.net 아이디어 1. 구현이 먼저 문제를 보고 N최대가 20이고 이동도 5번 하므로 문제가 말한 그대로 구현하면 되겠다고 생각. 상, 하, 좌, 우 이동 중에 '좌'로 이동하는 것부터 구현하면 나머지도 쉽게 만들 수 있다. 만들수록 변수나 if문이 많아져 다시 밀고 처음부터 작성했다. 너무 많은 변수는 필요 없다. 이건 다른 구현 문제도 마찬가지라고 생각. '이동시킬 블록'과..
https://www.acmicpc.net/problem/15654 15654번: N과 M (5) N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다. N개의 자연수 중에서 M개를 고른 수열 www.acmicpc.net 아이디어 1. 백트래킹 이미 N과 M 문제를 풀어봐서 바로 떠올랐다. 깊이가 M이 될 때마다 주어진 숫자들을 탐색하면 된다. 이 문제에서는 순열, 중복되지 않은 숫자들을 나열해야 하므로 이미 추가된 숫자가 있으면 continue로 넘겨준다. 전체 코드 N, M = map(int, input().split()) numbers = [int(x) for x in input().split()] ..