그냥 코딩하는 사람의 블로그

https://github.com/nbalance97/java-pairmatching-precourse

와.. 기능 구현하는데 시간이 부족하게 느껴져서 머리가 새하얘졌었다..ㅜ 앞서 테스트들과 마찬가지로 기능 목록부터 작성하고 기능을 구현하면서 필요한 내용은 추가적으로 목록에 덧붙이는 방식으로 개발을 진행하였다.  이 때 커밋을 신경쓰면서 개발을 하다보니 커밋할 내용보다 개발을 더 많이 하게 되거나 하는 문제도 있었다. 비록 모든 기능을 구현하지는 못했지만 나름 핵심 기능인 매칭 기능 / 조회 기능까지는 개발을 진행하였다.

부족했던 점

1. 자바 문법이 어색하다.
   • 파이썬으로만 개발을 하다가 최근에야 자바를 다시 시작하다 보니 기능을 구현하는데는 문제가 없지만 중간중간 모르는 방식들은 따로 찾아봐야 하는 문제점이 있었다.
2. 문제를 자세히 보지 않았다.
   • 크루 인원을 2명으로만 할 수 있는줄 알고 2명으로만 구현했으나 맨 마지막에 3명이 될수도 있었음.. 
   • 문제 힌트에 미리 만들어 둔 클래스가 있었는데 이를 참고하였으면 더 좋게 코드를 작성할 수도 있었을 것 같다.
3. 로직 자체를 너무 복잡하게 짠 것 같다.
   • 단순하게 작성하였으면 훨씬 좋았을 것 같다.. 각각의 크루에 레벨에서 매칭된 다른 크루 정보를 가지고 있는데, 이것보다는 <크루, 크루> 형식으로 따로 보관해 두었으면 더 효율적으로 작성할 수 있었을 것 같음
4. 패키지화 하지 않음..
   • 패키지화 하는 연습을 했는데 실전에서 시간에 쫓기다보니 구현을 다 하고 리팩토링 하겠다는 계획대로 되지 않았다.. 미리 패키지화 해서 코딩하는 습관이 필요한 것 같다.  

전체적으로 후련하지 않게 시간에 떠밀려서 제출하게 되어 조금 아쉬웠지만 최선을 다해서 시험을 봤으니 후회는 없었다. 또한 핵심적인 기능은 그래도 구현을 했다고 생각하여 그나마 다행이라고 생각한다ㅎㅎ

결과

최종 합격했습니다 ㅎㅎ 2022년엔 우아한 테크코스에서 열심히 배우겠습니다!!

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

풀이 과정

1. 그룹의 맞은 문제의 합의 최솟값을 기준으로 이분탐색을 진행한다.
2. 초기 left를 1, right를 10**5 * 20 + 1로 둔다. 이유는 최소 점수는 1점이고 최대 점수는 그룹이 1개이면서 시험지의 개수가 10**5개이며 각 시험지에서 맞은 문제가 모두 20개일 수 있기 때문이다.
3. 중간값((left + right) // 2)에 대해서 몇개의 그룹이 나오는지 확인한다.
   • 맞은 개수를 더해가면서 중간값보다 커진다면 그룹의 개수를 하나 늘려주고 맞은 개수 초기화
4. 전체 그룹의 개수가 K개보다 많다면 해당 점수로 나눌 수 있는 것이므로 따로 저장 후 오른쪽 구간 진행
5. 전체 그룹의 개수가 K개보다 적다면 해당 점수로 나눌 수 없는 것이므로 왼쪽 구간 진행
6. 따로 저장해둔 정답을 출력시켜 준다. 

소스 코드

import sys

input = lambda: sys.stdin.readline().rstrip()
N, K = map(int, input().split())
paper = list(map(int, input().split()))

left = 1
right = (10 ** 5 * 20) + 1

answer = 0
while left <= right:
    mid = (left + right) // 2
    group_count = 0
    score = 0
    for p in paper:
        score += p
        if score >= mid:
            group_count += 1
            score = 0

    if group_count < K:
        right = mid - 1
    else:
        answer = mid
        left = mid + 1

print(answer)

상황

• DELETE API를 호출하여 게시글을 삭제하려고 하는데 계속해서 오류가 발생함..
• 문제점의 원인을 찾아보니 하나의 db 세션이 사용중인 경우에는 사용할수 없다고 함.. 그런데 애초에 여러개의 db 세션을 만든 적이 없는데..?? 해서 찾아봄

문제 원인

• Market.py와 Models.py에서 서로 import해주는 이유로 생기는 문제로 확인
  • Market.py에 app와 db가 있고 url 라우팅 존재
  • Models.py에 db.model을 상속받는 모델들 존재
• 따라서, 따로 config.py를 두어서 config에 db와 app를 두고 Models.py와 Market.py가 config에 있는 db와 app를 사용하도록 하면 서로 import해주지 않으므로 문제 해결

Config.py

from flask import Flask
from flask_sqlalchemy import SQLAlchemy

app = Flask(__name__)
app.config['SQLALCHEMY_DATABASE_URI'] = 'sqlite:///Market.sqlite3'
app.config['SQLALCHEMY_TRACK_MODIFICATIONS'] = True
db = SQLAlchemy(app)

결론

• 순환 구조로 import하는걸 지양하자

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

풀이 과정

1. 시간이 오래 걸리는 전자 기기부터 충전시키는 방식으로 진행
2. 시간을 계산하기 위해서는 최소 히프를 사용해 준다.
   1. 히프에 현재 충전중인 전자 기기가 걸리는 시간을 넣어 준다.
   2. 히프가 가득 차지 않은 경우에는 충전기 자리가 남아있는 것이므로 전자기기의 충전 시간을 그대로 넣어준다.
   3. 히프가 가득 찬 경우는 충전기가 꽉 찬 경우이므로 기기를 하나 빼준 다음에 넣어주어야 한다. 따라서 히프에서요소 하나를 빼준 후, 해당 요소의 값에 현재 전자기기의 충전 시간을 더해서 다시 히프에 넣어준다.
3. 히프 내의 최댓값을 구해서 출력시켜 준다. 
   • 히프 내의 최댓값이 의미하는 것은 마지막으로 충전이 완료되는 시간이다.

소스 코드

import sys
import heapq

N, M = map(int, input().split())
elec = list(map(int, input().split()))
elec.sort(reverse=True)
heap = []

for e in elec:
    if len(heap) < M:
        heapq.heappush(heap, e)
    else:
        outcome = heapq.heappop(heap)
        heapq.heappush(heap, outcome + e)

print(max(heap))

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

풀이 과정

1. 이름과 연결된 자식들의 정보를 저장해 둔다.
   • 자식-(부모 or 조상)이 연결되어 있다면, 자식의 진입차수를 1 증가시켜 준다.
   • 단, 여기서 부모가 조상일수도 있음.
2. 초기 큐에는 각 가문의 시조들을 저장해 둔다.
   
   • 진입차수가 0인 이름들이 각 가문의 시조들이다.
3. 큐에서 한명씩 빼주면서 연결된 자식들의 진입차수를 1씩 감소시킨다.
   1. 진입차수가 0이 된다면, 해당 자식은 직전에 큐에서 빼준 인원의 자식이기 때문에 따로 저장해 두고, 해당 자식은 큐에 삽입하여 준다.
4. 출력 형식에 맞추어서 출력시켜주면 된다.

소스 코드

import sys
from collections import deque

input = lambda: sys.stdin.readline().rstrip()
N = int(input())
people = set(input().split())
child = {person:[] for person in people}
edge = {person:[] for person in people}
indegree = {person:0 for person in people}
father = []

M = int(input())
for _ in range(M):
    a, b = input().split()
    indegree[a] += 1
    edge[b].append(a)
    
queue = deque()
for person in people:
    if indegree[person] == 0:
        queue.append(person)
        father.append(person)
        
while queue:
    node = queue.popleft()
    for next_node in edge[node]:
        indegree[next_node] -= 1
        if indegree[next_node] == 0:
            queue.append(next_node)
            child[node].append(next_node)

print(len(father))
print(*sorted(father))
for name in sorted(list(people)):
    print_str = name + " " + str(len(child[name]))
    if len(child[name]) != 0:
        print_str += (" " + " ".join(sorted(child[name])))
    print(print_str)

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

풀이 과정

1. 문제를 푸는 순서가 있으므로 위상정렬 방식으로 풀이하는것이 좋음. 단, 문제 난이도가 낮은 것(번호가 작은 것)부터 풀어야 하므로 최소 히프를 사용하여서 구현함.
2. 문제들의 연결 정보와 각 문제의 진입 차수를 따로 저장한다.
3. 초기에 진입 차수가 0인 문제들을 히프에 넣는다.
4. 히프에서 문제 하나를 꺼내고, 문제에 연결된 다른 문제들(해당 문제를 푼 다음에 풀 문제들)의 진입차수를 하나 낮추어 준다.
   1. 이 때, 진입차수가 0이 된다면 해당 문제 번호를 히프에 넣어준다.
   2. 히프에서 문제를 꺼낼 때 따로 리스트에 문제 번호를 저장해주어야 함.(정답에서 출력)

소스 코드

import heapq
import sys

input = lambda: sys.stdin.readline().rstrip()
n, m = map(int, input().split())

graph = [[] for _ in range(n+1)]
indegree = [0] * (n+1)
for _ in range(m):
    a, b = map(int, input().split())
    graph[a].append(b)
    indegree[b] += 1

solve = []
heap = []

for i in range(1, n+1):
    if indegree[i] == 0:
        heapq.heappush(heap, i)

while heap:
    problem_number = heapq.heappop(heap)
    solve.append(problem_number)
    for next_problem in graph[problem_number]:
        indegree[next_problem] -= 1
        if indegree[next_problem] == 0:
            heapq.heappush(heap, next_problem)

print(*solve)

https://programmers.co.kr/learn/courses/30/lessons/86053?language=python3 

풀이 과정

1. 걸리는 시간의 범위가 크기 때문에 전체 범위가 너무 커질것 같아 이분탐색을 고려하였으나 이분 탐색 시 시뮬레이션 하는 파트 생각이 안나서 게시된 문제 풀이를 참조함.
2. 현재 시간을 t분이라고 할 때
   1. t분동안 물건을 나르는 횟수는 크게 mid // (걸리는 시간 * 2)이고, 맨 마지막에 편도로 이동 가능하므로 mid % (걸리는 시간 * 2)가 걸리는 시간보다 큰 경우는 횟수를 하나 늘려준다.
   2. t분동안 각각의 도시에서 옮길 수 있는 최대 금, 최대 은 개수를 각각 더해준다.
   3. 동시에 각각의 도시에서 옮길 수 있는 광물의 수의 총합도 구해준다.
   4. 다음 조건이 만족하면 정답을 저장하고 왼쪽 구간을, 아니라면 오른쪽 구간을 진행한다.
      1. 옮길수 있는 최대 금의 개수가 a보다 큰지
      2. 옮길수 있는 최대 은의 개수가 b보다 큰지
      3. 각각의 도시에서 옮길수 있는 광물의 수의 합이 a+b보다 큰지
   5. 잘 생각해 보면, 옮길 수 있는 광물의 수의 합이 a+b보다 크고, 최대 금과 최대 은의 개수가 a, b보다 크다면 금과 은의 개수를 적절하게 맞추어 준다면 금 a kg 이상, 은 b kg 이상을 나를 수 있다.
3. 시뮬레이션 파트를 잘 생각하지 못해서 풀지 못했던 문제임.. 고민 많이 해볼것.

소스 코드

def solution(a, b, g, s, w, t):
    answer = int(10**16)
    left, right = 0, int(10**16)
    
    while left <= right:
        mid = (left + right) // 2
        gold = 0
        silver = 0
        total = 0
        for i in range(len(g)):
            movement_count = mid // (t[i] * 2)
            if mid % (t[i] * 2) >= t[i]:
                movement_count += 1
            city_gold = w[i] * movement_count if w[i] * movement_count <= g[i] else g[i]
            city_silver = w[i] * movement_count if w[i] * movement_count <= s[i] else s[i]
            gold += city_gold
            silver += city_silver
            total += w[i] * movement_count if s[i] + g[i] >= w[i] * movement_count else s[i] + g[i]

        if gold >= a and silver >= b and total >= a + b:
            right = mid - 1
            answer = min(answer, mid)
        else:
            left = mid + 1
        
    return answer

https://leetcode.com/problems/longest-palindromic-substring/submissions/

풀이 과정

1. DP로 풀이하는게 정석이라고 하지만 문자열 최대 길이가 1000이므로 브루트포스로 풀수 있을것이라고 생각함.
2. 현재 위치가 i라고 하면, i 기준으로 문자를 하나씩 늘려가면서 펠린드롬이라면 문자열을 갱신하는 방식으로 코드 작성
   1. 시간 초과가 발생. 시간을 조금 절약하기 위해 정답 문자열의 길이 + 1부터 문자를 하나씩 늘려가도록 변경
   2. 위 방식으로 코드를 작성하니 시간 초과가 해결됨. 

소스 코드

class Solution:
    def longestPalindrome(self, s: str) -> str:
        answer = ""
        def checkPalindrome(s):
            return s == s[::-1]
        
        for i in range(len(s)):
            for j in range(len(answer)+1, len(s)-i+1):
                if checkPalindrome(s[i:i+j]):
                    answer = s[i:i+j] if len(answer) < j else answer
                    
        return answer

유저가 업로드한 프로필 이미지를 사용해야 하는데, 업로드된 이미지을 불러오는 기능을 어떻게 구현해야 할 까 해서 찾아보게 된 방식임. 대부분 정적 파일을 관리하는 또다른 서버를 둔다고 하지만 개발 단계에서의 이미지 업로드 / 이미지 표시를 해보아야 하므로 이미지 표시 기능을 따로 구현

1. 업로드 된 파일을 가져오는 파트

- Flask의 send_from_directory 메서드 사용

- 첫번째 인자는 폴더, 두번째 인자는 파일 이름

- 해당 리소스를 전송시켜준다.

@app.route('/uploads/<filename>')
def uploaded_file(filename):
    return send_from_directory('uploaded', filename)

2. HTML에서 이미지를 불러오는 파트

- url_for 메서드를 사용하면 첫번째 인자인 함수 이름을 가진 url을 리턴받을 수 있음.

- 두번째 인자부터는 키워드 인자로 변수 규칙에 맞추어서 대입된 url을 받아올 수 있음.

- 따라서, 아래 코드에서의 url_for의 결괏값은 uploads/eagle.jpg이다.

<image class="itemimage" src="{{ url_for('uploaded_file', filename='eagle.jpg') }}"></image>

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

풀이 과정

1. 아무 점이나 루트로 잡아서 진행한다.
2. 현재 점에 연결된 방문하지 않은 모든 점들을 방문하면서 DP테이블을 갱신한다.
   1. 초기 모든 DP테이블은 점마다 [0, 1]로 설정한다.  
   2. DP[i][0]은 루트가 i점인 부분 트리에서 i점이 얼리어답터가 아닐 때의 전체 얼리어답터 최소 개수
   3. DP[i][1]은 루트가 i점인 부분 트리에서 i점이 얼리어답터일 때의 전체 얼리어답터 최소 개수
   4. 따라서, DP[i][0]은 다음 점에서는 얼리어답터가 나와야 하므로 DP[다음 점][1]을 더해준다.
   5. DP[i][1]은 다음 점에서 얼리어답터가 나올수도 있고 나오지 않을수도 있으므로 DP[다음 점][0]과 DP[다음 점][1]의 최솟값을 더해 준다.
3. 루트 노드에서의 DP 테이블의 최솟값을 출력시켜준다.

소스 코드

import sys

sys.setrecursionlimit(10**6)

input = lambda: sys.stdin.readline().rstrip()

n = int(input())
tree = [[] for _ in range(n+1)]

for _ in range(n-1):
    src, dest = map(int, input().split())
    tree[src].append(dest)
    tree[dest].append(src)

root = 1

dp = [[0, 1] for _ in range(n+1)]
visited = [False] * (n+1)

def solve(node):
    visited[node] = True
    for next_node in tree[node]:
        if not visited[next_node]:
            solve(next_node)
            dp[node][0] += dp[next_node][1]
            dp[node][1] += min(dp[next_node][0], dp[next_node][1])
        

solve(root)
print(min(dp[root]))