본문 바로가기

전체 글1068

읽은 책 소감 - 비전공자를 위한 이해할 수 있는 IT 지식 최근 친한 동생이 개발쪽으로 전향하고싶어해서 국비지원 교육을 듣는다고 한다. 개발적인 부분이야 따로 묶어두고 강제로(?) 알려주면 되니, 당장 배경 지식을 쌓아줄겸 추천해줄만한 책을 살펴보다가 발견한 책이다. 난 전공자긴 하지만 일단 목차가 너무 재밌을 것 같기도 하고, 200페이지 좀 넘는 얇은 책이라 부담없이 볼 수 있을 것 같아 나도 하나 샀다. 확실히 재밌어서 한 2일만에 다 읽었다. 책의 목표는 기획자나 디자이너 등 개발자와 같이 일하는 사람에게 배경지식을 쌓아줘서 개발자와 얘기가 통하게 하는걸 목표로 한 책으로 보인다. 사실 개발자라면 대강 다 알고있는 내용들이긴 할테지만, 막 개발자를 시작한 사람들에게도 강력하게 추천할만하다. 솔직히 이정도면 신입 개발자 필독서는 물론이고 영업팀, 기획팀 등.. 2021. 11. 6.
읽은 책 소감 - 수학귀신 알고리즘 풀 때, 알고리즘 해설을 블로그에 작성할 때 증명적인 면이 너무 부족한 것 같다. 특히 수학 관련 알고리즘 문제를 푸는데 어려움이 있다. 뭐 기업 코테같은 것에선 큰 수학적 지식을 요구하진 않으니 현재의 수준으로도 딱히 상관없는 부분이지만, 애초에 알고리즘은 취미로 하고있었고 앞으로도 꾸준히 할테니 수학적 지식이 필요하다(개인만족을 위해!). 물론 코드를 외워서 따라하는건 할 수 있다. 하지만 난 암기보단 이해를 하고싶다. 예를들어 이런거다. 에라토스테네스의 체를 구현할 때 최적화를 위해 입력 숫자(n)의 제곱근(sqrt(n)) 까지만 확인한다. 이걸 이해해서 사용하기 전까지는 암기해서 사용하게 된, 어쩌다가 발견한 시간복잡도를 줄일 수 있는 정보였다. 하지만 중간에 한번 증명과정을 이해했고, .. 2021. 11. 6.
백준 17469 자바 - 트리의 색깔과 쿼리 (BOJ 17469 JAVA) [ 백준 17469 ] [ 코드 (깃헙) ] 트리의 부모를 알려주고, 주어진 쿼리를 해결해야 한다. 쿼리는 '1 a'와 같이 들어오면 간선 제거, '2 a'와 같이 들어오면 a에서 갈 수 있는 정점들에 포함된 색깔 종류의 개수를 출력해야 한다. 당연히 매번 쿼리를 진행하고 bfs나 dfs로 갈 수 있는 경로를 찾고 또 해당 노드들에 존재하는 색깔 종류를 셀 순 없다(시간초과). 그럼 일단 각 부분들을 뭘 이용해 구할 수 있을지 확인해보자. 1. 갈 수 있는 정점들 확인 : union-find를 사용한 그룹짓기 2. 각 그룹에 포함된 색깔 종류의 개수 : HashSet을 사용하면 애초에 동일한 색깔이 중복해서 안들어가니, 해당 set의 size()만 확인하면 해당 그룹에 포함된 색깔 종류의 개수를 알 수 .. 2021. 11. 4.
백준 13306 자바 - 트리 (BOJ 13306 JAVA) [ 백준 13306 ] [ 코드 (깃헙) ] 트리의 부모를 알려주고, 주어진 쿼리를 해결하는 문제이다. 쿼리는 '0 b'와 같이 들어오면 b번째 edge 제거하는 쿼리와, '1 c d'와 같이 들어오면 c와 d 사이에 연결경로가 있는지 묻는 쿼리가 있다. 일단 거리 자체를 묻지 않고, 연결 경로가 있는지만 파악하면 된다. 그럼 이거엔 union-find 알고리즘을 쓰면 될 것임을 알 수 있다. 다만 해당 알고리즘의 경우 그룹간의 관계를 맺는것은 쉽지만, 연결을 끊는건 힘들다. 그럼 쿼리를 반대순서로 보면 어떻게 될까? 원래 순서대로라면 '간선들이 존재하는 그래프에서 edge를 제거하면서 중간중간 특정 노드간에 연결경로가 있는지 묻는 쿼리' 이지만, 반대로 미리 쿼리상에 존재하는 모든 간선을 제거한 후 역.. 2021. 11. 4.
백준 1138 자바 - 한 줄로 서기 (BOJ 1138 JAVA) [ 문제보기 ] [ 코드보기(깃헙) ] N이 최대 10이다. 따라서 모든 경우를 보려면 10! 번을 봐야한다. 이 경우 362880번으로, 사실 모든 경우를 봐도 가능하긴 하다! 다해봐야 O(N! * N) 정도이다. 사실 시간복잡도, 메모리복잡도 면에서 모두 이득인 방법이 더 있다. 어차피 입력이 키가 1인 사람부터 차례대로 들어오기 때문에, 키가 큰 사람부터 순서대로 입력을 만족하는 위치에 넣어버리면 된다. (따라서 그리디 알고리즘 분류다.) 4 2 1 1 0 의 입력을 확인해보자. 이 경우 키가 1인 사람은 좌측에 2명, 2인 사람은 좌측에 1명, 3인 사람은 좌측에 1명, 4인 사람은 좌측에 아무도 없다는 입력이다. 키가 작은 사람부터 보자면 어려운 문제가 확실하지만, 키가 큰 사람부터 보면 엄청 .. 2021. 11. 3.
백준 1485 자바 - 정사각형 (BOJ 1485 JAVA) [ 문제 보기 ] [ 코드 보기(깃헙) ] [ 틀린 경우 ] 처음엔 아래와 같이 축에 평핸한 정사각형을 찾는줄 알았다. 그래서 예를들어 입력이 1 1 1 1 2 2 1 2 2 와 같다면, 사실 좌측이 x축인지 우측이 x축인지는 안알려줬지만 상관없이 좌측이 2종류고, 우측이 2종류이며 각각 2번씩 나왔고, 좌측의 2종류의 차이와 우측의 2종류의 차이가 동일하다면 정사각형으로 판단하도록 했다. 이 코드는 틀렸다. [ 해설 ] 그렇다면 아래와 같이 정사각형이 기울어 있는 경우까지 찾을 수 있어야 한다. 1. 그래도 딱히 어려울건 없는데, 그냥 4개의 점을 입력받고 나올 수 있는 모든 경우의 길이를 구해본다. 4개에서 2개를 순서없이 골라야하니, 4C2 = 4P2 / 2! = 4*3/2 = 6가지만 구해보면 된.. 2021. 11. 3.
백준 1195 자바 - 킥다운 (BOJ 1195 JAVA) 문제 : https://www.acmicpc.net/problem/1195 코드 : https://github.com/NaHwaSa/BOJ_BaekjunOnlineJudge/blob/master/01100/BOJ_1195.java 순전히 구현력에 따라 풀 수 있고 없고가 갈리는 문제이다. 길이가 최대 100이므로 그냥 brute force로 모든 경우를 시뮬레이션 돌려도 전혀 문제가 없다. 1. 일단 최대로 나올 수 있는 경우는 예를들어 모든 부분이 '이'로 되어 있다면 서로 겹칠 수 없으니 두 문자열의 합이 일단 최대치이다. 그 후에, 이런 모양부터 시작해서 하나하나 직접 비교해보는 것이다. 이 때 '이'와 '이'가 만나는 경우는 맞물릴 수 없는 경우이므로 무시한다. ... --(A)-- ... 이런식.. 2021. 11. 2.
백준 1111 자바 - IQ Test (BOJ 1111 JAVA) 문제 : https://www.acmicpc.net/problem/1111 코드 : https://github.com/NaHwaSa/BOJ_BaekjunOnlineJudge/blob/master/01100/BOJ_1111.java 쉽게봤더니 생각보다 예외처리할게 많았다. 그래도 이정도면 무난한 편인듯. 'A'와 'B'가 언제 발생할지만 잘 생각해보면 된다. 1. 우선 n이 2 이상일 때 첫번째 수와 두번째 수가 동일한 경우를 생각해봐야 한다. 이게 찾기 제일 어려웠다. [1 1 1 1 ...] 이런 경우이다. 처음엔 2차방정식이 안풀리니 당연히 'A'일꺼라 생각했는데, 2x-1 과 같은 경우 가능하다. 그러니 동일한게 이어진다면 동일한 값을 출력만 해주면 된다. 다만 [1 1 2 ..] 이렇게 갑자기 숫.. 2021. 11. 2.
백준 23334 자바 - Olympic Ranking (BOJ 23334 JAVA) 문제 : https://www.acmicpc.net/problem/23334 코드 : https://github.com/NaHwaSa/BOJ_BaekjunOnlineJudge/blob/master/23300/BOJ_23334.java 브론즈 티어지만 자바 한정으로 시간초과 날 위험이 큰 문제라 남겨봅니다. 자바에 시간 어드밴티지 없이 모든 언어 동일하게 1초 제한인 문제입니다. 이 문제의 경우 일반적으로 생각할 수 있는, 입력받은걸 배열에 넣고 정렬하는 방식으로 하게 되면 시간초과가 날 확률이 있습니다. g,s,b가 최대 999이고, g,s,b 순서대로 비교가 되면 되므로 g*1000000 + s*1000 + b 로 처리를 하게되면 최대 10억-1 이므로 int형으로 한방에 표현 가능합니다. 예를들어 g.. 2021. 11. 2.
백준 22728 자바 - Amida, the City of Miracle (BOJ 22728 JAVA) 문제 : https://www.acmicpc.net/problem/22728 코드 : https://github.com/NaHwaSa/BOJ_BaekjunOnlineJudge/blob/master/22700/BOJ_22728.java 일본어로 된 문제라 번역기 돌려야 한다는 점을 빼면 그냥 문제에 제시된 대로 구현만 하면 된다. 내 경우엔 arr[a][b] = c를 a높이에서 b번 수직선에서 c번 수직선으로 넘어갈 수 있다로 정의했다. 따라서 h, p, q를 입력받을 시 arr[h][p] = q, arr[h][q] = p가 된다. 그리고 높이 1001(가로선이 높이 1000부터 있을 수 있으므로)부터 높이를 1씩 감소시키면서 해당 높이에서 이동할 가로선이 있으면 무조건 이동하는 방식으로 짰다. 최종적으로.. 2021. 10. 30.

티스토리툴바