[항해99 취업 리부트 코스 학습일지] 자신감 만땅으로 채웠다

가보자고 ~!

3일 차 알고리즘 데이~

하루종일 알고리즘만 푸니까 생각보다 재밌다...

예전에는 매일 2~3문제만 풀고 끝냈는데 강제적인 시간이 알고리즘을 풀라고 등 떠미니까 자연스레 녹아든 느낌..?

근데 계속 머리쓰는 거 같아서 배고프다 ㅜ

오늘 저녁도 먹을까 잘까 고민하다 잤는데 그래서 그런가 배에 레드존 떨어지는 중이다.

아무튼 오늘 하루도 고생했다!

---

0. TIL (2024.05.31)

📚오늘 진행한 문제 리스트

1. 백준 24313 알고리즘 수업 - 점근적 표기 1 (실버 5) ✔️

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

풀이⬇️

3일차 - 5번
# 백준 24313 알고리즘 수업-점근적 표기 1 - 실버 5

# n >= n0 일때, f(n) <= c * g(n)을 만족하는가?
import sys


a1, a0 = map(int, sys.stdin.readline().split())
c = int(sys.stdin.readline())
n0 = int(sys.stdin.readline())

flag = False
for n in range(n0, 100):
    if a1 * n + a0 >= c * n:
        print(0)
        flag = True
        break

if not flag:
    print(1)

주어진 규칙대로 식만 구현하면 해결하는 문제

 

2. 백준 15650 N과 M (2) (실버 3) ✔️

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

풀이⬇️

3일차 - 6번
# 백준 15650 N과 M (2) - 실버 3

# 조건을 만족하는 길이 M인 수열 모두 구하기
# 1. 1~N 까지 자연수 중, 중복 없이 M개 고른 수열 -> 순서는 상관없이 고르기만 하면 되니까 조합
# 2. 오름차순
import sys
from itertools import combinations


N, M = map(int, sys.stdin.readline().split())
print('\n'.join(sorted([' '.join(map(str, x)) for x in combinations(range(1, N+1), M)])))

똑같이 주어진 조건만 잘 구현하면 되는 문제.

중복 없이 고른다는 부분에서 combinations 사용했다!

 

3. 백준 25192 인사성 밝은 곰곰이 (실버 4) ✔️

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

풀이⬇️

3일차 - 7번
# 백준 25192 인사성 밝은 곰곰이 - 실버 4

# 입장하고 난 뒤 처음 채팅은 반드시 이모티콘
# 그 외에 채팅은 일반 채팅이므로 count X -> set으로 처리
# 다음 엔터 나오기 전까지 set에 이름 담아둠
# ENTER 가 입력되면 set의 길이만큼 answer에 더해주고 set.clear
# 마지막까지 진행하면 set에 남은 것들 기록하고 종료
import sys


N = int(sys.stdin.readline())
answer = 0
log = set()
for i in range(N):
    s = sys.stdin.readline().strip()
    if s != 'ENTER':
        log.add(s)
    else:
        answer += len(log)
        log.clear()
answer += len(log)
print(answer)

쉽게 구현 가능했던 문제

ENTER 라는 문자열이 뜬 이후에 처음으로 친 채팅만 이모티콘이고 나머지는 아니다.

그럼 모든 채팅에 set을 사용해서 처리하면 중복을 제거하고 이모티콘 채팅만 모아볼 수 있다.

그리고 다음 ENTER 문자열이 뜨기 전까지 삽입하다가 뜨면 개수 저장하고 set 초기화하는 방식으로 구현했다.

 

4. 백준 1764 듣보잡 (실버 4) ✔️

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

풀이⬇️

3일차 - 8번
# 백준 1764 듣보잡 - 실버 4

# 각각의 집합의 교집합의 개수와 사전순으로 정렬된 원소 출력
import sys


N, M = map(int, sys.stdin.readline().split())
A = set(sys.stdin.readline().strip() for _ in range(N))
B = set(sys.stdin.readline().strip() for _ in range(M))
print(len(A & B))
print('\n'.join(sorted(A & B)))

설명부터 교집합 쓰라는 문제여서 바로 교집합 사용해서 해결

근데 다른 팀원분들 푼거 보니까 set 하나 쓰는 게 속도적인 측면에서 낫다고 했다.

근데 4ms 차이 정도라 유의미한 속도는 아닌 것 같아서 일단 보류!

 

5. 백준 4374 지프의 법칙 (실버 2) ✔️

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

풀이⬇️

3일차 - 9번
# 백준 4374 지프의 법칙 - 실버 2

# n번 등장하는 단어 사전순 나열 -> 소문자 출력
# 그러한 단어가 없다면 "There is no such word." 출력
import sys
import re
from collections import Counter

flag1 = True
while flag1:
    inp = sys.stdin.readline().strip()
    # 종료조건: 입력이 없으면 종료
    if not inp:
        flag1 = False
        continue

    new_words = []
    n = int(inp)

    flag2 = True
    while flag2:
        sentence = sys.stdin.readline().strip()

        if sentence == 'EndOfText':
            flag2 = False
            continue

        # 입력 받은 문자열을 정규표현식을 이용해 알파벳만 남김
        words = re.findall(r'\b[a-z]+\b', sentence.lower())
        new_words += words

    # Counter로 개수 세서 개수 == v인 k 값만 리스트로 만든다.
    answer = [k for k, v in sorted(Counter(new_words).items(), key=lambda x: x[0]) if v == n]
    # 만약 리스트에 값이 있다면 출력하면 되고 없다면 지정 문구 출력
    if answer:
        print('\n'.join(a for a in answer))
    else:
        print('There is no such word.')
    print()

설명 보면서 천천히 구현했는데 아무리 봐도 틀리게 한 부분이 없었지만 25%에서 틀린다고 뜬 문제

뭐가 문제인지 고민만 2시간 한 거 같은데 답답해서 문제 푼 팀원분께 여쭤보니 정규 표현식 사용해 보라고 하셔서 찾아보니 re라는 정규 표현식 라이브러리가 있었다.

사용해서 순수 알파벳만 남기고 문제 푸니까 바로 정답 처리됐다 ;;;;

도대체 뭐 때문인지 아직까지 모르겠다.

분명 알파벳 제외하고 남은 특수문자를 처리하는 함수도 제대로 만든 것 같은데 ㅜ

 

6. 백준 5107 마니또 (실버 1) ✔️

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

풀이⬇️

3일차 - 10번
# 백준 5107 마니또 - 실버 1

# 연결고리가 생기는지 확인
# dictionary 사용해서 연결 정보 저장(start -> end 형식으로 진행)
# 그 후 연결 정보 기반으로 bfs 진행해서 시작 정점을 다시 만났을 때 return 1
# return 한 1을 카운트에 저장하고 계속 bfs 진행
import sys
from collections import defaultdict, deque


def bfs(begin):
    q = deque()
    q.append(begin)
    while q:
        target = q.popleft()
        if not target:
            return 0

        visited[target] = True
        if visited[linked[target]]:
            return 1
        else:
            q.append(linked[target])


case_num = 1

while True:
    linked = defaultdict(str)
    visited = defaultdict(bool)
    member = list()
    count = 0
    N = int(sys.stdin.readline())
    if N == 0:
        break

    for i in range(N):
        start, end = sys.stdin.readline().strip().split()
        linked[start] = end
        visited[start] = False
        member.append(start)

    for m in member:
        if not visited[m]:
            count += bfs(m)

    print(case_num, count)
    case_num += 1

마니또가 선물을 주고 이게 사이클이 형성이 되는지 찾는 문제

단방향 그래프 문제와 동일하고 특이하게 문자열 가지고 푸는 문제라 dictionary 사용해서 단방향 노드 처리를 진행했다.

이후에는 그래프 탐색 문제랑 일치하기 때문에 bfs 진행하면서 만약에 현재 target의 목적지인 member가 이미 방문 처리가 된 노드라면 사이클이 형성된 것이므로 count에 1 증가해 주면 쉽게 문제를 풀 수 있다.

 

7. 백준 5588 별자리 찾기 (골드5) ✔️

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

풀이⬇️

3일차 - 11번
# 백준 5588 별자리 찾기 - 골드 5

# 찾고 싶은 별자리를 set에 x좌표 오름차순으로 저장 -> x가 제일 작은 좌표 기준으로 상대 좌표 재저장
# 사진에 있는 별자리들 중에서 len(set) 만큼 조합해서 x가 제일 작은 좌표 기준으로 상대 좌표 저장
# 두 좌표 비교후 일치하면 원래 좌표와 사진 속 좌표가 얼마나 차이나는지 확인
# 시간 초과 -> 조합 하는 과정에서 느려진거 같은데 다른 방법 시도

# 찾고 싶은 별자리에서 아무 좌표 하나 지정 -> 그 좌표로 부터 사진 속 좌표들마다 이동량 계산
# 계산한 다음에 찾고 싶은 별자리의 좌표마다 이동량 적용해서 이동한 좌표들이 전부 사진 속 좌표에 있는지 확인
# 있다면 이동량만 리턴
import sys


m = int(sys.stdin.readline())
target_star = list(tuple(map(int, sys.stdin.readline().split())) for _ in range(m))
n = int(sys.stdin.readline())
picture_star = set(tuple(map(int, sys.stdin.readline().split())) for _ in range(n))
x0, y0 = target_star[0]
for star in picture_star:
    flag = True
    move_x, move_y = star[0] - x0, star[1] - y0
    for target in target_star[1:]:
        t_move_x, t_move_y = target[0] + move_x, target[1] + move_y
        if (t_move_x, t_move_y) not in picture_star:
            flag = False
            break
    if flag:
        print(move_x, move_y)
        break

처음 문제를 진행할 때는 상대좌표를 이용해서 사진 속 찾는 별자리의 좌표들을 조합으로 골라 비교하려고 했다.

근데 구현하고 보니까 시간초과가 떴다.

그럴 수 밖에 없는 게 최대 경우의 수가 1000 C 200인데 이러면 무조건 시간 초과 뜰 거였는데 아무 생각 없이 풀어버렸다.

그래서 생각한게 찾고자 하는 별자리의 좌표 하나를 고정하고 그 지정한 좌표를 사진 속 별자리의 좌표 하나씩 비교해 가면서 각각의 평행이동한 이동량을 구한다.

그 후에 다시 찾고자 하는 별자리를 탐색하면서 이동량만큼 더해준 좌표가 사진 속 좌표 목록에 하나라도 없다면 다음 좌표를 찾고 모두 존재한다면 그 해당 이동량을 반영해서 print 해주면 된다.

 

8. 백준 3421 이상한 규정 (다이아몬드 2) ❌

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

풀이⬇️

아직 시도조차 안 해봤다.

풀어봐야지~

---

📝오늘자 질문

1. 오늘 진행된 강의에서 학습한 내용은 무엇인가요

• 파이썬 기초 문법(입출력, 반복문, 조건문, 자료형, 시간 복잡도 등)

 

2. 이번 주 진행된 팀 스터디에서 얻은 인사이트는 무엇인가요?

• 정규 표현식 라이브러리 - re

---

* 항해99 취업 리부트 코스를 수강하고 작성한 콘텐츠 입니다.

https://hanghae99.spartacodingclub.kr/reboot

IT 커리어 성장 코스 항해99, 개발자 취업부터 현직자 코스까지