본문 바로가기

전체 글83

[알고리즘] 이분 매칭(Bipartite Matching) 1. 이분 매칭 네트워크 플로우(Network Flow) 알고리즘에서 두 정점 사이의 용량이 1이고, 정점이 두 집합으로 구분되는 특수한 경우. 한쪽 그룹을 X, 다른 그룹을 Y라고 할 때, X → Y로의 최대 유량을 구하는 문제. 이때, 각 용량이 1이므로 최대 매칭 수를 찾는 문제로 볼 수 있음. 2. 알고리즘 예시 DFS를 활용하여, 매칭을 하나씩 선택하는 과정을 거친다. 예시는 조금 복잡하지만, 백준 문제의 예시를 가져왔다. 세부적인 예시는 아래와 같다. 다음과 같이 왼쪽 그룹, 오른쪽 그룹에 있는 정점에 대하여 각 선분 중 연결되어 있다. DFS를 응용하여 편하게 최적의 답을 찾을 수 있다. 우선 1번점에서 연결할 수 있는 최적의 점을 찾는다. 그러면, 왼쪽 1번점, 오른쪽 2번점을 연결할 수 .. 2022. 5. 22.
[SSAFY] 특화 프로젝트 회고 0. 프로젝트 소개 및 정리 인공지능을 활용한 일기 애플리케이션, 비화 - 인공지능을 활용하여 업로드한 이미지 기반 꽃 추천 - 일기를 작성하며 꽃을 모아가는 게이미피케이션 - 노인을 위한 기능 (폰트 크기, 색상 등) 사용 기술 스택 - 프론트 : Kotlin - 백 : Django + DRF, Oauth - 인공지능 : TensorFlow, Numpy, Pandas - 기타 : Gitlab CI/CD + Docker, Nginx 기여도 - 백엔드 80% - 대부분은 백엔드 코드를 작성 - 다른 팀원이 작성한 코드 리뷰 및 리팩토링 - 인공지능 20 % - 인공지능에 사용되는 코드 일부 기여 - 백엔드를 통하여 인공지능 제공과 관련한 부분에 대하여 기여 - 인프라 100% - 처음으로 CI/CD 전반적.. 2022. 5. 22.
[Python] 백준 3806 S를 T로 문제 링크 :https://www.acmicpc.net/problem/3806 3806번: S를 T로 첫째 줄에 테스트 케이스의 개수 C (C ≤ 200)가 주어진다. 각 테스트 케이스는 두 줄로 이루어져 있다. 첫째 줄에는 '0', '1', '?'로 이루어진 S, 둘째 줄에는 '0', '1'로 이루어진 T가 주어진다. 두 문자 www.acmicpc.net 1. 접근 방법 접은 방법을 조금 고민했는데, 가능한 조건이 많지는 않지만, BFS나 DP로는 적합하지 않을 것 같아 그리디한 방식을 탐색했다. 2. 풀이 코드 🖥python 코드 링크 :https://github.com/mintropy/PS/blob/master/BAEKJOON/Python/3000/3806.py GitHub - mintropy/PS.. 2022. 4. 17.
22-03-27 KT 2022 1차 신입 개발자 코테 후기 총 3문제 중 1, 2번 정답률 50% 과락 조건이 있어 조금은 긴장하기도 했다. 그리고 KT는 코테를 시행한 것도 오래되지 않았다고 들어 어떤 문제가 제출될지 궁금했다. 1. 구현 배열과 for문 만으로 해결할 수 있는 구현. 조건도 단순하고, 값의 범위도 크지 않아 충분히 해결할 수 있는 문제 백준 실버5 ~ 브론즈 1 2. 다익스트라 응용 아마 값의 범위가 작아서 다른 BFS, DFS 등의 방법도 값 입력만 잘한다면 충분히 할 수 있을 것 같다. 백준 골드 4~5 비슷한 문제 : https://www.acmicpc.net/problem/16137 16137번: 견우와 직녀 견우와 직녀는 여러 섬과 절벽으로 이루어진 지역에서 살고 있다. 이 지역은 격자로 나타낼 수 있으며, 상하좌우로 인접한 칸으로 .. 2022. 3. 27.
22-03-26 라인 2022 상반기 신입 개발자 코테 후기 라인은 지난 2021 하반기 코테 이후 두 번째이다. 지난 코테보다는 조금 쉬웠던 것 같다. 여섯 문제를 전부 제출하긴 했지만, 복기해보니 TLE의 가능성이 있는 문제 몇 개를 발견했고, 최종 4~5 솔 정도일 것 같다. 1. 조건 분기 or 패턴 매칭 나는 그냥 조건 분기로 풀었는데, 패턴 매칭으로 더 수월하게 할 수 있지 않을까라는 생각도 들었다. 백준 실버 4~5 2. 조합 응용 최악의 경우라고 해도 가능할 것 같아서 제출했는데, TLE가 발생할수도 있을 것 같다. 조금 더 조건에 따라 분류 및 정렬을 했으면 안정적으로 해결할 수 있을 것 같다. 백준 실버 1~2 3. 구현 단순한 구현문제, 조건이 몇 가지 붙어 번거로운 작업이 필요할 수 있지만, 어렵지는 않았다. 백준 실버 2~3 4. 그리디 조.. 2022. 3. 27.
[Python] 2212 센서 문제 링크 : https://www.acmicpc.net/problem/2212 2212번: 센서 첫째 줄에 센서의 개수 N(1 ≤ N ≤ 10,000), 둘째 줄에 집중국의 개수 K(1 ≤ K ≤ 1000)가 주어진다. 셋째 줄에는 N개의 센서의 좌표가 한 개의 정수로 N개 주어진다. 각 좌표 사이에는 빈 칸이 하나 있 www.acmicpc.net 1. 접근 방법 각 값이 아니라, 각 값의 차이 중 최솟값을 뽑아내는 그리디 2. 풀이 코드 🖥python 코드 링크 : https://github.com/mintropy/baekjoon_py/blob/master/2000/2200/2212.py GitHub - mintropy/baekjoon_py: BOJ를 Python으로 해결한 코드의 저장소입니다. BO.. 2022. 3. 25.
[Python] 백준 2533 사회망 서비스(SNS) 문제 링크 : https://www.acmicpc.net/problem/2533 2533번: 사회망 서비스(SNS) 페이스북, 트위터, 카카오톡과 같은 사회망 서비스(SNS)가 널리 사용됨에 따라, 사회망을 통하여 사람들이 어떻게 새로운 아이디어를 받아들이게 되는가를 이해하는 문제가 중요해졌다. 사회망 www.acmicpc.net 1. 접근 방법 DP와 DFS를 고민했는데, 나는 둘 다 사용한 방법으로 가닥을 잡았다. 문제를 해결하고 DP로만 해결하는 등의 풀이도 고민했지만, 잘 되지는 않아 시간은 조금 오래 걸렸지만, 해결했다. 2. 풀이 코드 🖥python 코드 링크 : https://github.com/mintropy/baekjoon_py/blob/master/2000/2500/2533.py Git.. 2022. 3. 22.
[Python] 백준 13335 트럭 문제 링크 : https://www.acmicpc.net/problem/13335 13335번: 트럭 입력 데이터는 표준입력을 사용한다. 입력은 두 줄로 이루어진다. 입력의 첫 번째 줄에는 세 개의 정수 n (1 ≤ n ≤ 1,000) , w (1 ≤ w ≤ 100) and L (10 ≤ L ≤ 1,000)이 주어지는데, n은 다리를 건너는 트 www.acmicpc.net 1. 접근 방법 queue를 활용하여 쉽게 해결할 수 있는 문제. 리스트를 활용한다면, 슬라이싱으로 유사하게 구현할 수 있을 것 같다. 2. 풀이 코드 🖥python 코드 링크 : https://github.com/mintropy/baekjoon_py/blob/master/13000/13335.py GitHub - mintropy/ba.. 2022. 3. 21.
22-03-19 프로그래머스 2022 SK ICT Family 개발자 채용 챌린지 2차 후기 1차 후기 : https://mintropy.tistory.com/48 22-03-06 프로그래머스 2022 SK ICT Family 개발자 채용 챌린지 1차 후기 편하게 코딩 테스트 연습도 하자라는 마음으로 시작을 했고, 나름 어렵지 않은 문제가 출제된 것 같았다. 1. 거스름돈 문제 응용과 유사한 그리디 나는 약간의 하드코딩을 더하여 해결했고, 해당 mintropy.tistory.com 1차 코테는 나름 쉽다는 생각을 하면서, 2차가 어려울 수 있겠다고 생각했고, 정말로 어렵게 출제되었다. 1. 나는 완전 탐색으로 해결했는데, 해쉬 구조를 활용하여 더 빠르게 해결할 수 있을 것 같다는 생각도 든다. 2. 복잡한 구현 최소한 힙, 큐, 스택 등의 구조를 2개 이상 활용해야 할 것으로 보인다. 정답 중 .. 2022. 3. 21.

티스토리툴바