반응형

18310

https://www.acmicpc.net/problem/18310

 

18310번: 안테나

첫째 줄에 집의 수 N이 자연수로 주어진다. (1≤N≤200,000) 둘째 줄에 N채의 집에 위치가 공백을 기준으로 구분되어 1이상 100,000이하의 자연수로 주어진다.

www.acmicpc.net

[정답]

1
2
3
4
5
import sys
N = int(sys.stdin.readline())
a = list(map(int, sys.stdin.readline().split()))
a.sort()
print(a[(N-1)//2])
 cs

.

.

.

[풀이]

중앙값을 구하는 문제이다. 중앙값 중에서도 최솟값을 구해야 하기 때문에 (N-1)//2를 해준다

 

처음에는 중앙값이 답인줄 모르고 모든 안테나 에서의 거리 중 최소를 구하는 완전탐색을 했다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
import sys
N = int(sys.stdin.readline())
a = list(map(int, sys.stdin.readline().split()))
a.sort()
for n in range(N-1, -1, -1):
    total = 0
    total += a[n]*n - sum(a[:n]) 
    total += sum(a[n:]) - a[n]*(N-1-n)
    if n == N-1:
        t_result = total
    t_result = min(t_result, total)
    if t_result == total:
        result = a[n]
print(result)
#오답
 cs

그 결과 시간초과가 떴다.

고민하면서 풀며 설마... 했는데

답이 중앙값이라 어이가 없었다.

반응형

'백준 문제풀이' 카테고리의 다른 글

[백준 1735] 파이썬 : 분수 합  (0) 2021.10.11
[백준 10815] 파이썬 : 숫자 카드  (0) 2021.10.10
[백준 15654] 파이썬 : N과 M (5)  (0) 2021.10.09
[백준 5555] 파이썬 : 반지  (0) 2021.10.08
[백준 11652] 파이썬 : 카드  (2) 2021.10.08
반응형

15654

https://www.acmicpc.net/problem/15654

 

15654번: N과 M (5)

N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다. N개의 자연수 중에서 M개를 고른 수열

www.acmicpc.net

[정답]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
import sys
N, M = map(int, sys.stdin.readline().split())
num = list(map(int, sys.stdin.readline().split()))
num.sort()
visited = [False]*N
result = []
 
 
def dfs(depth):
    if depth == M:
        print(' '.join(map(str, result)))
    for i in range(N):
        if not visited[i]:
            result.append(num[i])
            visited[i] = True
            dfs(depth+1)
            result.pop()
            visited[i] = False
 
dfs(0)
 cs

.

.

.

[풀이]

dfs를 이용하는 문제.

수열을 먼저 오름차순으로 정리.

탐색했는지 기록하는 리스트 visited, 출력할 결과를 저장하는 리스트 result를 만들어주고

재귀문을 이용한 dfs탐색을 한다.

dfs에 관한 기초적인 문제.

 

p.s.

까먹고 있어 잠시 해맸다.

반응형

'백준 문제풀이' 카테고리의 다른 글

[백준 10815] 파이썬 : 숫자 카드  (0) 2021.10.10
[백준 18310] 파이썬 : 안테나  (0) 2021.10.09
[백준 5555] 파이썬 : 반지  (0) 2021.10.08
[백준 11652] 파이썬 : 카드  (2) 2021.10.08
[백준 1049] 파이썬 : 기타줄  (0) 2021.10.07
반응형

5555

https://www.acmicpc.net/problem/5555

 

5555번: 반지

당신은 N개의 반지를 가지고 있다. 각각의 반지는 대문자 10 문자로 이루어진 문자열이 새겨져 있다. 반지는 문자열의 시작과 끝이 연결된 형태로 문자가 새겨져 있다. 반지에 각인된 문자열을

www.acmicpc.net

[정답]

1
2
3
4
5
6
7
8
9
10
11
12
import sys
s = sys.stdin.readline().strip()
N = int(sys.stdin.readline())
cnt = 0
for n in range(N):
    a = sys.stdin.readline().strip()
    for i in range(10):
        a = a[1:] + a[0]
        if s in a:
            cnt += 1
            break
print(cnt)
 cs

.

.

.

[풀이]

반지에 적혀있는 문자열이기에 순환이 가능하다.

따라서 a = a[1:] + a[0]로 문자열 첫글자를 제일 뒤로 계속 보내준다.

이렇게 푸는 것이 문제의 의도일 것이다.

 

하지만 간단한 방법이 있었다.

문자열을 두번 써서 순환하는 경우까지 한번에 계산하는 것이다.

1
2
3
4
5
6
for n in range(N):
    a = sys.stdin.readline().strip()
    a *= 2
    if s in a:
        cnt += 1
print(cnt)
 cs

 

p.s.

생각을 유연하게 하자.

반응형

'백준 문제풀이' 카테고리의 다른 글

[백준 18310] 파이썬 : 안테나  (0) 2021.10.09
[백준 15654] 파이썬 : N과 M (5)  (0) 2021.10.09
[백준 11652] 파이썬 : 카드  (2) 2021.10.08
[백준 1049] 파이썬 : 기타줄  (0) 2021.10.07
[백준 4796] 파이썬 : 캠핑  (0) 2021.10.04
반응형

11652

https://www.acmicpc.net/problem/11652

 

11652번: 카드

준규는 숫자 카드 N장을 가지고 있다. 숫자 카드에는 정수가 하나 적혀있는데, 적혀있는 수는 -262보다 크거나 같고, 262보다 작거나 같다. 준규가 가지고 있는 카드가 주어졌을 때, 가장 많이 가지

www.acmicpc.net

[정답1]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
import sys
dic = {}
N = int(sys.stdin.readline())
for n in range(N):
    a = int(sys.stdin.readline())
    if a in dic.keys():
        dic[a] += 1
    else:
        dic[a] = 1
 
    if n == 0:
        temp = a
    if dic[temp] == dic[a]:
        temp = min(temp, a)
    elif dic[temp] < dic[a]:
        temp = a
print(temp)
 cs

.

.

.

[정답2]

1
2
3
4
5
6
7
8
9
10
11
import sys
dic = {}
N = int(sys.stdin.readline())
for n in range(N):
    a = int(sys.stdin.readline())
    if a in dic.keys():
        dic[a] += 1
    else:
        dic[a] = 1

dic = sorted(dic.items(), key = lambda x: (-x[1], x[0]))
print(dic[0][0])
 cs

.

.

.

[풀이]

최대 최소 비교하는 쉬운 문제다. [정답1]로 후딱 풀었다.

후에 [정답2]처럼 sorted()를 이용해서 간략화할 수 있다는 것을 알게 되었다.

 

dictionary, sorted(), key, lambda 등에 익숙하지 못해 조금 해맸다.

dictionary도 sorted()를 이용하여 정렬을 할 수 있다.

items를 입력값으로 받고, 정렬 기준 key를 lamda를 이용하여-x[1], x[0]순으로 한다.

즉, x[1] (카드의 개수)의 -(내림차순)으로 정렬하고

x[0] (카드 숫자)의 오름차순으로 정렬한다.

 

하단부터 [정답1], [정답2]

각각의 방법마다 메모리 효율, 시간 효율 장점이 있다.

 

p.s.

쉬운 문제로 기본을 다지는게 도움이 된다.

반응형

'백준 문제풀이' 카테고리의 다른 글

[백준 15654] 파이썬 : N과 M (5)  (0) 2021.10.09
[백준 5555] 파이썬 : 반지  (0) 2021.10.08
[백준 1049] 파이썬 : 기타줄  (0) 2021.10.07
[백준 4796] 파이썬 : 캠핑  (0) 2021.10.04
[백준 2960] 파이썬 : 에라토스테네스의 체  (0) 2021.10.03
반응형

1049

https://www.acmicpc.net/problem/1049

 

1049번: 기타줄

첫째 줄에 N과 M이 주어진다. N은 100보다 작거나 같은 자연수이고, M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 M개의 줄에는 각 브랜드의 패키지 가격과 낱개의 가격이 공백으로 구분하여 주

www.acmicpc.net

[정답]

1
2
3
4
5
6
7
8
import sys
N, M = map(int, sys.stdin.readline().split())
g_set, g_ind = 1000, 1000
for i in range(M):
    a, b = map(int, sys.stdin.readline().split())
    g_set = min(a, g_set)
    g_ind = min(b, g_ind)
print(min(min(g_set*(N//6+1), g_set*(N//6) + g_ind*(N%6)), g_ind*N))
 cs

.

.

.

[풀이]

min() 함수를 이용하는 간단한 문제다.

라고 생각해서 틀렸다.

간단한 척하면서 조금 꼬여있는 문제다.

 

2번의 오답을 냈다. 2가지 포인트를 조심하자.

첫째, 브랜드를 혼용하여 살 수 있다. 즉, 브랜드1의 세트를 사고 브랜드 2의 낱개를 살 수 있다.

따라서 g_set와 g_ind의 최솟값을 각각 저장해두고 min()계산은 마지막에 한다.

 

둘째, 줄을 구입하는 방법은 총 3가지 경우의 수가 있다.

세트만 사는 경우, 세트를 사고 낱개를 사는 경우, 낱개로만 사는 경우.

세 방법 중 최소를 구해 출력하자.

 

p.s.

틀렸을땐 반례를 생각해보고 빠뜨린 경우의 수를 생각해내자.

반응형

'백준 문제풀이' 카테고리의 다른 글

[백준 5555] 파이썬 : 반지  (0) 2021.10.08
[백준 11652] 파이썬 : 카드  (2) 2021.10.08
[백준 4796] 파이썬 : 캠핑  (0) 2021.10.04
[백준 2960] 파이썬 : 에라토스테네스의 체  (0) 2021.10.03
[백준 8974] 파이썬 : 희주의 수학시험  (0) 2021.10.02
반응형

백준알고리즘 배너에 NHN 신입 개발자 공채가 떠서 조건들을 살펴보았다.

요즘들어 배너가 뜰때마다 간간이 확인해 보고 있다. 카카오, 삼성 그런 대기업들의 공채를 말이다.

들어갈때마다 항상 느끼는 것은 내가 너무나도 부족하다라는 것이다. 코딩 공부를 얼마 하지 않았기에 부족한 것은 당연하다.

그런데 꿈을 이루기 위해서, 입사조건들을 맞추기 위해서 엄청난 노력이 필요하다는 것을 체감하게 되니 오늘따라 좌절감이 조금 든다.

원래 공부할 길이 보이고 목표가 보일 때 동기부여를 받곤 했지만 오늘따라 힘이 든다.

목표가 까마득하게 멀어서 길은 알지만 끝이 보이지 않는 느낌이다.

 

내가 과연 해낼 수 있을까.

내가 도달할 수 있을까.

내 시간들을 투자해서 이뤄낼 수 있는 것일까.

도달했더니 나랑 안 맞으면 어떻게 해야할까.

내가 흥미를 잃지 않고 끝까지 해나갈 수 있을까.

 

나의 능력에 의구심이 들고 중간에 포기하지 않을 수 있을지 불안이 생긴다.
공부할 것이 너무 많다. 

반응형
반응형

4796

https://www.acmicpc.net/problem/4796

 

4796번: 캠핑

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, L, P, V를 순서대로 포함하고 있다. 모든 입력 정수는 int범위이다. 마지막 줄에는 0이 3개 주어진다.

www.acmicpc.net

[정답]

1
2
3
4
5
6
7
8
9
import sys
cnt = 0
while True:
    L, P, V = map(int, sys.stdin.readline().split())
    if L == 0 and P == 0 and V == 0:
        break
    else:
        cnt += 1
        print('Case {0}: {1}'.format(cnt, L*(V//P)+ min(L, V%P)))
 cs

 

.

.

.

[풀이]

단순 사칙연산 문제.

V를 P로 나눈  나머지를 어떻게 사용하느냐가 관건이다.

min()을 사용하여 간략하게 나타내자.

반응형

'백준 문제풀이' 카테고리의 다른 글

[백준 11652] 파이썬 : 카드  (2) 2021.10.08
[백준 1049] 파이썬 : 기타줄  (0) 2021.10.07
[백준 2960] 파이썬 : 에라토스테네스의 체  (0) 2021.10.03
[백준 8974] 파이썬 : 희주의 수학시험  (0) 2021.10.02
[백준 2503] 파이썬 : 숫자 야구  (0) 2021.10.02
반응형

2960 에라토스테네스의 체

https://www.acmicpc.net/problem/2960

 

2960번: 에라토스테네스의 체

2, 4, 6, 8, 10, 3, 9, 5, 7 순서대로 지워진다. 7번째 지워진 수는 9이다.

www.acmicpc.net

[정답]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
import sys
N, K = map(int, sys.stdin.readline().split())
e = [True for i in range(N+1)]
e[0], e[1] = False, False
cnt = 2
c = 0
while(c<K):
    if e[cnt]:
        for j in range(cnt, N+1, cnt):
            if e[j]:
                e[j] = False
                c += 1
                if c == K:
                    print(j)
    cnt += 1
 cs

.

.

.

[풀이]

에라토스테네스의 체

그리스 수학자가 발견한 소수 찾는법이라 한다.

 

N까지 수의 리스트를 만들어 준 후,

cnt의 배수를 False로 바꾸며 진행한다.

바꿀 때마다 증가하는 c가 K와 같아지면 답을 출력하고 종료한다.

 

무식하게 N번까지 다 하지 않으려고 for()가 아닌 while()을 사용해봤다.

반응형

'백준 문제풀이' 카테고리의 다른 글

[백준 1049] 파이썬 : 기타줄  (0) 2021.10.07
[백준 4796] 파이썬 : 캠핑  (0) 2021.10.04
[백준 8974] 파이썬 : 희주의 수학시험  (0) 2021.10.02
[백준 2503] 파이썬 : 숫자 야구  (0) 2021.10.02
[백준 11004] 파이썬 : K번째 수  (0) 2021.10.02

+ Recent posts

티스토리툴바