전체 글

[백준 1043번] 거짓말 (C++)

https://www.acmicpc.net/problem/1043 1043번: 거짓말 지민이는 파티에 가서 이야기 하는 것을 좋아한다. 파티에 갈 때마다, 지민이는 지민이가 가장 좋아하는 이야기를 한다. 지민이는 그 이야기를 말할 때, 있는 그대로 진실로 말하거나 엄청나게 www.acmicpc.net 거짓말 문제는 그래프를 이용하여 해결할 수 있습니다. 파티에서 거짓말을 하려면 해당 파티에 오는 사람들은 모두 진실을 알지 못해야합니다. 진실을 아는 사람이 존재하지 않는다면, 모든 파티에서 과장을 할 수 있습니다. A는 진실을 아는 사람, B는 진실을 아는 사람과 같이 파티에 참석한 사람일 때, B가 참석한 파티에서도 거짓말을 할 수 없습니다. 먼저, B와 파티에서 거짓말을 한 경우, A와의 파티에서 진실..

[백준 2617번] 구슬 찾기 (C++)

https://www.acmicpc.net/problem/2617 2617번: 구슬 찾기 모양은 같으나, 무게가 모두 다른 N개의 구슬이 있다. N은 홀수이며, 구슬에는 번호가 1,2,...,N으로 붙어 있다. 이 구슬 중에서 무게가 전체의 중간인 (무게 순서로 (N+1)/2번째) 구슬을 찾기 위해서 www.acmicpc.net 구슬 찾기 문제는 그래프로 해결할 수 있습니다. 무게가 중앙값이 될 수 없는 구슬을 찾는 문제입니다. 따라서, 무게가 중앙값인 구슬은 본인보다 가벼운 구슬이 (n - 1) / 2개, 무거운 구슬이 (n - 1) / 2개 있어야 합니다. 따라서, 가벼운 구슬이 (n - 1) / 2개보다 많거나, 무거운 구슬이 (n - 1) / 2개보다 많은 구슬은 무게가 중앙값이 될 수 없습니다..

[백준 1707번] 이분 그래프 (C++)

https://www.acmicpc.net/problem/1707 1707번: 이분 그래프 입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V와 간선의 개수 E가 빈 칸을 사이에 www.acmicpc.net 다음과 같은 조건을 만족시키는 집합의 분할을 가질 수 있다면, K분 그래프라고 합니다. 위키백과 인접한 두 정점은 서로 다른 정점 집합에 속한다. k = 2일 때, 이를 이분 그래프라고 합니다. 따라서 인접한 정점의 색이 서로 다르도록 색을 칠해주어야 하고, 색의 수는 2가 되어야 합니다. 따라서, BFS를 이용하여 각 정점에 색을 부여하되, 이미 방문한 정점의 색이 인접한 정점과 색이 같으면 이..

[백준 19700번] 수업 (C++)

https://www.acmicpc.net/problem/19700 19700번: 수업 키가 188cm, 154cm인 학생들을 한 팀으로, 키가 180cm, 161cm인 학생들을 한 팀으로, 키가 172cm인 학생을 혼자 팀으로 묶으면 총 3개의 팀을 구성할 수 있다. 더 적은 갯수의 팀으로 학생들을 묶을 수 있 www.acmicpc.net 수업 문제는 그리디와 이진검색트리를 이용하여 해결할 수 있습니다. 학생의 키가 중복되지 않기 때문에, 키가 큰 사람부터 그룹에 넣어주면, 먼저 그룹이 할당된 수강생들의 키는 현재 그룹을 할당하려는 수강생보다 키가 큽니다. 따라서, i번째 학생은 그룹의 크기가 Ki보다 작은 그룹 중 하나에 할당시켜주면 됩니다. 하지만, 그룹의 수를 최소로 만들어 주어야하기 때문에, K..

2022.05.29일 서버 개발자 취준생의 성장일지 ✍🏼

05.28일에는 라인 플러스 인턴십 코딩 테스트를, 29일에는 SSAFY 코딩 테스트를 보았다. 라인 코테에서 첫 두 문제는 1시간 이내에 풀었지만, 마지막 문제는 풀지 못했고 종료 시간이 다 되어서 solution이 생각났다.. SSAFY도 첫 문제는 빠르게 풀었지만, 두번째 문제를 한 시간 동안 풀지 못했다. 분명 쉬운 문제인데.. 긴장한 탓에 풀지 못하는게 너무 너무 아쉽다.. 잡힐 듯 잡히지 않는 코딩 테스트가 쉽지 않다.. 테스트가 끝나고, 긴장이 풀린 상태에서는 금방 푸는 것을 보면.. 긴장을 푸는 연습이 필요할 것 같다. 오늘은 동기와 같이 새로운 스터디를 시작했다. 아직은 둘다 부족하지만, 서로 도움이 될 수 있었으면 좋겠다. 그리고 토비의 스프링이라는 책으로 다시 공부를 시작했다. 아직은..

[백준 23326번] 홍대 투어리스트 (C++)

https://www.acmicpc.net/problem/23326 23326번: 홍익 투어리스트 도현이는 홍익 투어리스트가 되어 홍익대학교를 견학하려고 한다. 홍익대학교는 $N$개의 구역이 원형으로 배치된 모습이다. $1$번 구역에서 시계 방향으로 각각 $2$번, ... , $N$번 구역이 존재하고, www.acmicpc.net 홍익 투어리스트 문제는 이진 검색 트리를 이용하여 해결할 수 있습니다. 명소의 위치만 이진 검색 트리에 저장해주면 됩니다. 1번 연산 : 이진 검색 트리에 존재한다면, 제거하고, 존재하지 않는다면, 명소로 추가, 시간 복잡도 : O(logN) 2번 연산 : 도현이의 위치만 이동, 시간 복잡도 : O(1) 3번 연산 : lower_bound()를 이용하여, 가장 가까운 명소의 위..

[백준 21939번] 문제 추천 시스템 Version 1 (C++)

https://www.acmicpc.net/problem/21939 21939번: 문제 추천 시스템 Version 1 tony9402는 최근 깃헙에 코딩테스트 대비 문제를 직접 뽑아서 "문제 번호, 난이도"로 정리해놨다. 깃헙을 이용하여 공부하시는 분들을 위해 새로운 기능을 추가해보려고 한다. 만들려고 하는 명령 www.acmicpc.net 문제 추천 시스템은 이진 검색 트리를 이용하여 해결할 수 있습니다. 이진 검색 트리를 이용하면, 최대/최소값 구하기, 삽입, 삭제을 모두 O(logN)에 수행할 수 있습니다. 또한, 이진 검색 트리에 {l, p}를 삽입하면, 먼저, 난이도를 기준으로 정렬하고, 난이도가 같을 땐 문제 번호로 정렬하므로, 마지막 원소가 난이도가 가장 높으면서, 번호가 가장 큰 번호입니다..

[백준 1202번] 보석 도둑 (C++)

https://www.acmicpc.net/problem/1202 1202번: 보석 도둑 첫째 줄에 N과 K가 주어진다. (1 ≤ N, K ≤ 300,000) 다음 N개 줄에는 각 보석의 정보 Mi와 Vi가 주어진다. (0 ≤ Mi, Vi ≤ 1,000,000) 다음 K개 줄에는 가방에 담을 수 있는 최대 무게 Ci가 주어진다. (1 ≤ Ci www.acmicpc.net 보석 도둑 문제는 이진검색트리를 이용하여 해결할 수 있습니다. 훔칠 수 있는 보석의 가격을 구해야하는데, 가방에는 최대 한 개의 보석만 넣을 수 있습니다. 가방에 넣을 수 있는 보석 중 가장 가치가 큰 것을 선택하면 됩니다. 그럼 어느 가방에 먼저 넣어야할까요? 아래 예에서, 가방에 담을 수 있는 최대 무게가 가장 무거운 가방부터 넣어보..