링크 : https://www.acmicpc.net/problem/4396 4396번: 지뢰 찾기 지뢰찾기는 n × n 격자 위에서 이루어진다. m개의 지뢰가 각각 서로 다른 격자 위에 숨겨져 있다. 플레이어는 격자판의 어느 지점을 건드리기를 계속한다. 지뢰가 있는 지점을 건드리면 플레이어 www.acmicpc.net 문제 소요시간: 30분 실패 설계하기(접근방법) 1. n, mine_list, check_list 을 입력받는다 2. 한 점 내에서 움직일 8방향의 좌표리스트를 생성한다 0 0 0 0 * 0 이것을 리스트로 표현하면 (0,0)을 제외한 0 0 0 dx = [-1, -1, -1, 0, 0, 1, 1, 1] dy = [-1, 0, 1, -1, 1, -1, 0, 1] 으로 표현된다 3. mine..
링크 : https://www.acmicpc.net/problem/2504 2504번: 괄호의 값 4개의 기호 ‘(’, ‘)’, ‘[’, ‘]’를 이용해서 만들어지는 괄호열 중에서 올바른 괄호열이란 다음과 같이 정의된다. 한 쌍의 괄호로만 이루어진 ‘()’와 ‘[]’는 올바른 괄호열이다. 만일 X www.acmicpc.net 문제 소요시간: 22분, 실패 설계하기(접근방법) 1. 문자열을 입력받는다, 스택을 선언한다 2. 알고리즘 해석 1) 만약 괄호가 열리면, stack에 append하고 괄호 내의 숫자는 후에 2or 3만큼 곱해진다 따라서 tmp 를 선언하여 그 변수를 제어해준다. 2) 괄호가 닫히고, 그 직전 괄호가 그 괄호의 쌍'()' or '[]' 이였다면 지금까지 곱해진 tmp만큼 ans에 더..
링크 : https://www.acmicpc.net/problem/11286 11286번: 절댓값 힙 첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 0이 아니라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net 문제 소요시간: 21분 12초 설계하기(접근방법) 1. n을 입력받는다, heapq를 두 개 선언한다 2. 알고리즘 해석 1) x = int(input()) 을 받는다 x > 0 이면 heap_plus에 (x)를 x < 0 이면 heap_minus에 (-x)를 heappush 한다 x = 0일 때는 i) heap_plus, heap_minus 둘 다 원소가 있을 때 ..
링크 : https://www.acmicpc.net/problem/4358 4358번: 생태학 프로그램은 여러 줄로 이루어져 있으며, 한 줄에 하나의 나무 종 이름이 주어진다. 어떤 종 이름도 30글자를 넘지 않으며, 입력에는 최대 10,000개의 종이 주어지고 최대 1,000,000그루의 나무가 주어 www.acmicpc.net 문제 소요시간: 24분 12초 설계하기(접근방법) 1.더 이상 입력일 없을 때까지 입력을 받는다 tree =sys.stdin.readline()을 입력으로 받은 후, if not tree: 로 조건을 설정하여 비어있다면 break을 해준다 2. tree_list(딕셔너리) 에 입력값이 없다면 트리를 딕셔너리에 추가한 후 1 그루를 value 값으로 정해준다 tree_list 내..
링크 : https://www.acmicpc.net/problem/2075 2075번: N번째 큰 수 첫째 줄에 N(1 ≤ N ≤ 1,500)이 주어진다. 다음 N개의 줄에는 각 줄마다 N개의 수가 주어진다. 표에 적힌 수는 -10억보다 크거나 같고, 10억보다 작거나 같은 정수이다. www.acmicpc.net 문제 소요시간: 22분 17초, heapq 서치 시간 포함 설계하기(접근방법) 1. n을 입력받고 heap을 선언한다 2. 알고리즘 해석 1) 각각의 리스트를 한줄씩 입력받는다 2)각각의 원소를 순회한다. 1: 현재 heap의 크기가 n보다 작을 경우 원소의 크기에 관계없이 heappush 2: heap의 크기가 n 이상일 경우 i. 만약 현재 heap의 최소값보다 현재 원소가 크다면 heapp..
링크 : https://www.acmicpc.net/problem/11279 11279번: 최대 힙 첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net 문제 소요시간: 개념 배우기 설계하기(접근방법) 1. n을 입력받는다, heap을 초기화한다 2. 알고리즘 해석 x를 n번 입력받는다. 0이 아닌 경우 -> heap에 heappush()를 한다. 다만 우리가 필요한 것은 최대 값이니 인자를 -x로 push 해주어야 한다 0인 경우 -> heap에 원소가 없는 경우 0 출력 -> heap에 원소가 있는 경우 heap..
링크 : https://www.acmicpc.net/problem/14425 14425번: 문자열 집합 첫째 줄에 문자열의 개수 N과 M (1 ≤ N ≤ 10,000, 1 ≤ M ≤ 10,000)이 주어진다. 다음 N개의 줄에는 집합 S에 포함되어 있는 문자열들이 주어진다. 다음 M개의 줄에는 검사해야 하는 문자열들이 주어 www.acmicpc.net 문제 소요시간: 15분 실패 설계하기(접근방법) 1. n, m을 입력받는다 2. 집합 s를 입력받고, 단어를 입력받으며 s 내에 있는지 검사한다 있다면 cnt += 1을 해준다 3.print(cnt) (실패 이유) m과 n 을 곱하면 연산량이 1억번이 넘어가므로 일반적인 리스트로는 시간이 초과된다. 파이썬의 딕셔너리 기능을 이용하면 키값을 통해 연산을 O(..
오버로딩(overloading) 4.1 오버로딩이란? 메서드도 변수와 마찬가지로 같은 클래스 내에서 구별될 수 있어야 하기에 다른 이름을 가져야 한다. 4.2 오버로딩의 조건 매서드의 이름이 같아도 매개변수가 다르면 서로 구별될 수 있다는 특징 반환 타입은 오버로딩을 구현하는데 아무런 영향을 주지 못한다 이유: 우리가 코딩을 하고 입력을 하면 컴파일러가 매개변수의 타입, 개수로 함수를 구분하는데, 리턴 타입으로는 우리가 어떤 메서드를 불러오는지 컴퓨터는 알지 못한다. 4.3 오버로딩의 예 가장 대표적인 것은 println 메서드이다. 괄호 안에 값만 지정해주면 출력에 문제가 없어지만, 매개변수로 지정하는 값의 타입에 따라서 호출되는 println 메서드가 달라진다. void println() void p..
