본문 바로가기

분류 전체보기150

1043 거짓말 (C++) 문제를 보고 Union-Find 알고리즘을 사용해야겠다는 것은 어렵지 않게 떠올렸다. 풀이 "거짓말쟁이로 알려지지 않으면서, 과장된 이야기를 할 수 있는 파티 개수의 최댓값을 구하는 프로그램을 작성하시오." 이 문장은 "진실을 아는 사람과 전혀 관련 없는 사람들만 모인 파티 개수를 구하는 프로그램을 작성하시오."라고 바꿀 수 있다고 생각한다. N명의 사람들을 두 가지 부류, [진실을 아는 사람과 관련 있는 사람들]과 [진실을 아는 사람과 관련 없는 사람들]로 나눌 수 있다. [진실을 아는 사람과 관련 있는 사람들]인지 어떻게 판단할 수 있을까? 다음의 문장들은 문제를 읽고 나서 얻을 수 있는 정보이다. 1. 지민이는 진실을 아는 사람이 함께하는 파티에서 거짓말을 할 수 없다. 2. 진실을 모르는 사람이 .. 2022. 10. 1.
12880 그래프 차이 최소 (C++) 보다시피.. 계속해 놓치던 반례가 있어 많은 WA를 받게 되었다. 문제 접근 과정 처음 읽었을 때 고등학교 기숙사에서 지내는데 12시 이후 소등이 되고 나서 갑자기 아무 문제나 하나 읽고 잠들기 전까지 고민하고 싶어 겨우겨우 와이파이 신호를 잡고 문제를 로딩하고 읽어 고민을 시작하게 되었다. 임의의 간선 집합을 알고 있을 때 해당 간선 집합으로 모든 정점 중 A와 B를 아무거나 선택하고 A -> B, B -> A 두 가지 경로가 모두 존재하는지 판별하는 방법도 잘 모르고 있었다. N = 50 밖에 안되었지만 전체적인 문제에 대한 접근 방법이 도저히 감이 잡히지 않아 문제에 대한 가벼운 고민을 2시간 정도 한 이후 해답을 참고하게 되었다. Justice Hui님의 tistory를 참고하게 되었다. 간선들을.. 2022. 9. 30.
2473 세 용액 (C++) 세 용액 중 두 가지 용액만 특정해주면 나머지 한 가지는 logn만에 알아서 선택된다는 사실을 이용하였다. 문제 접근 과정 처음 읽었을 때(언제였는지 잘 기억 안 남) : 알 것 같은데 어떻게 푸는지 모르겠다. 갑자기 떠오른 풀이 : n^2이 가능하니 두 개를 정해주고 하나는 알아서 정해지게 하자(n = 5000) 구현 10분정도 걸림 이분 탐색 잘못 적어줘서 두 번 WA 코드 한번 쭉 다시 읽으며 오류 잡음 수정 후 기쁨의 AC 시간 복잡도 : O(n*n*log(n)) 소요 시간 : 측정 불가 아쉬운 점 이분 탐색을 짤 때 해당 조건문에서 m을 커지게 해야 할지 작아지게 해야 할지 일단 적고 틀리면 바꾸는 경향이 있다. 고치게 되면 좋겠다. 전체적인 감상 지난 주 쯤 이 문제를 읽고 넘어간 적이 있는데.. 2022. 9. 29.
16724 피리 부는 사나이 (C++) Floyd's Tortoise and Hare Algorithm을 사용하여 문제를 해결하였다. 문제 접근 과정 1분 문제의 이차원 배열이 Functional Graph의 형태를 띤다는 사실을 알게 되었다. 사이클 판별 알고리즘을 활용하여 발생하는 사이클의 개수를 세어주면 된다는 것을 알았다. 6분 이차원 배열에서 직접 하려던 사이클 판별을 하기 위해 rev 배열을 구현하는데 어려움을 겪었다. 7분 이차원 배열의 노드에 새 id를 각각 부여해서 일반적인 형태의 그래프로 치환하였다. 14분 코드 첫 실행 while문에서 문제가 생긴다는 것을 return 0;을 써보며 알게 되었다. 15분 수정 후 첫 제출 기쁨의 AC 소요 시간 : 15분 아쉬운 점 : 노드에 새 id를 부여하는 것을 처음부터 했으면 더 빨.. 2022. 9. 28.
백준 1318문제 풀며 느낀점(과정) 최근 맞은 문제 1300문제를 넘기게 되어 이 글을 통해 나의 현 상황과 감상을 기록해보려고 한다. 알고리즘 문제 해결을 시작한 지 벌써 1년 반이 다 되어간다. 지난 시간 동안 계속해 느낀 거는 알고리즘 계속 열심히 공부하면 잘해지기는 할까?라는 생각이었다. 두 번의 KOI 예선 탈락, 두 번의 NYPC 예선 탈락, PS를 시작한 이후로 가장 기억에 남는 일들이다.. 지난 시간 동안 청심국제중학교에서 청심국제고등학교로 진학하고 SAT, AP와 처음 고등학생이 되어 생활하게 된다는 다른 여러 가지 이유들로 나름의 정체기를 맞이하기도 하고 얼마 전부터는 성장하는 방법에 대한 감을 찾은 것 같다가도 다시 내가 알고리즘을 잘하게 되려면 무엇을 어떻게 해야 할지 감이 안 잡히기도 한다. 내가 느낀 가장 핵심적인.. 2022. 9. 27.

티스토리툴바