Altiora Petamus

OddOccurrencesInArray coding task - Learn to Code - Codility Find value that occurs in odd number of elements. app.codility.com 🤔생각해보기 Arrays 관련 문제다보니 여러 풀이 방법이 있을 것이다. 그 중에 필자가 가장 먼저 떠오른 방법은 문제의 마지막에 적혀있는 조건과 관련이 있다. all but one of the values in A occur an even number of times. "A 의 값 중 하나를 제외한 모든 값은 짝수로만 발생한다" 단 하나를 제외한 모든 값이 짝수로 발생한다면, 홀수로 발생하는 그 하나를 집어낼 수 있으면 되는 것 아닌가? 개수를 세는 알고리즘은 여러가지가 있지만..

1002번: 터렛 각 테스트 케이스마다 류재명이 있을 수 있는 위치의 수를 출력한다. 만약 류재명이 있을 수 있는 위치의 개수가 무한대일 경우에는 -1을 출력한다. www.acmicpc.net 🤔생각해보기 피타고라스 정리 를 활용하여 원의 교점을 구하는 문제다. 생각보다 고려해야할 조건이 많아서 성공할거라고 확신했음에도 7번 정도 실패했다... 하나씩 조건을 해결해가면 금방 풀 수 있는 문제이니 한 번 정리해보자. 우선 distance = 두 터렛 간의 거리 를 구해야 한다. 거리(distance)가 0 보다 커야 두 터렛이 같은 위치가 아니므로 아래 조건(2~4)을 적용한다. 만약 두 터렛이 각자 계산한 거리 r1, r2, 그리고 distance 중 가장 긴 값이 나머지 두 값의 합보다 크다면 만나지 ..

3009번: 네 번째 점 세 점이 주어졌을 때, 축에 평행한 직사각형을 만들기 위해서 필요한 네 번째 점을 찾는 프로그램을 작성하시오. www.acmicpc.net 문제 간단 설명 세 점의 좌표가 주어졌을 때 나머지 점의 좌표를 구하는 문제이다. 🤔생각해보기 축에 평행한 직사각형을 완성하기 위한 좌표의 조건은 무엇인지 생각해보면 된다. x 좌표가 같은 점은 2개씩 있다. y 좌표가 같은 점도 2개씩 있다. 결국 입력으로 들어온 값들을 카운트해서 1개밖에 없는 각 좌표값들을 출력하면 마지막 좌표값이 된다. # 직사각형을 만들기 위해서는 같은 x 좌표가 2개, 같은 y 좌표가 2개 있어야한다. x = [] y = [] for _ in range(3): p1, p2 = map(int, input().split..

1920번: 수 찾기 첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들 www.acmicpc.net 🤔생각해보기 이 문제를 요약하면 다음과 같다. 컨테이너 안에 지정된 값(M)이 존재하는지 검사하라. 평소 파이썬을 자주 사용했다면 in 연산자를 사용해볼 법하다. 실제로도 in 만 사용해도 해결할 수 있다. 하지만 이 문제는 이진탐색에 관한 문제이므로 in 연산자를 아는지 묻는 문제는 아닐 것이라 판단하고, 이진탐색에 초점을 맞춰서 문제를 해결하도록 한다. 이진탐색을 하기 위해서는 보통 3가지 인덱스를 활용한다. ..

4948번: 베르트랑 공준 베르트랑 공준은 임의의 자연수 n에 대하여, n보다 크고, 2n보다 작거나 같은 소수는 적어도 하나 존재한다는 내용을 담고 있다. 이 명제는 조제프 베르트랑이 1845년에 추측했고, 파프누티 체비쇼 www.acmicpc.net 문제 베르트랑 공준은 임의의 자연수 n에 대하여, n보다 크고, 2n보다 작거나 같은 소수는 적어도 하나 존재한다는 내용을 담고 있다. 이 명제는 조제프 베르트랑이 1845년에 추측했고, 파프누티 체비쇼프가 1850년에 증명했다. 예를 들어, 10보다 크고, 20보다 작거나 같은 소수는 4개가 있다. (11, 13, 17, 19) 또, 14보다 크고, 28보다 작거나 같은 소수는 3개가 있다. (17,19, 23) 자연수 n이 주어졌을 때, n보다 크고,..

1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 🤔생각해보기 DFS와 BFS의 기본 개념을 익히기 위한 문제다. 자바에서는 2차원 배열로 edge 들을 설정한 뒤에 해결했었는데 파이썬에서 딕셔너리를 활용하여 풀어보았다. 개인적으로는 2차원 배열이 가독성이 끔찍하다고 느껴져서인지 어려워하는 편인데 딕셔너리를 활용해보니 이해하기도 편하고 훨씬 쉽게 해결 할 수 있는 것 같다. 성공 코드 from collections import deque from collections imp..

BinaryGap coding task - Learn to Code - Codility Find longest sequence of zeros in binary representation of an integer. app.codility.com Q. A binary gap within a positive integer N is any maximal sequence of consecutive zeros that is surrounded by ones at both ends in the binary representation of N. For example, number 9 has binary representation 1001 and contains a binary gap of length 2. The n..

2581번: 소수 M이상 N이하의 자연수 중 소수인 것을 모두 찾아 첫째 줄에 그 합을, 둘째 줄에 그 중 최솟값을 출력한다. 단, M이상 N이하의 자연수 중 소수가 없을 경우는 첫째 줄에 -1을 출력한다. www.acmicpc.net 🤔생각해보기 소수를 찾는 것은 여러가지 방법이 있지만, 평소 애용하는 방법은 제곱근을 통해서 구하는 방법이다. math.sqrt() 의 효율성에 대해 여러 의견이 있긴하던데, 아직까지 느려서 실패한 적은 없는 것 같다. 로직은 다음과 같이 처리하면 된다. 소수인지 검사해서 배열 prime에 담는다. prime이 비어있다면, -1 을 출력하고 값이 있다면 합과 최소값을 각각 출력한다. 성공 코드 # 소수 # 기본수학 2 # 소수를 찾아서 리스트에 넣기 # 배열에서 최소값 m..