룰루랄라 알고리즘

https://www.acmicpc.net/problem/6588 6588번: 골드바흐의 추측 각 테스트 케이스에 대해서, n = a + b 형태로 출력한다. 이때, a와 b는 홀수 소수이다. 숫자와 연산자는 공백 하나로 구분되어져 있다. 만약, n을 만들 수 있는 방법이 여러 가지라면, b-a가 가장 큰 www.acmicpc.net 오늘 푼 문제는 코딩테스트 단골 출제 문제인 소수 판정 골드바흐의 추측이다. 1년 전에 파이썬으로 풀었던 문제인데 이번에 재채점 결과 시간초과로 틀렸다고 알림이 와서 자바로 다시 풀어봤다. 소수 판정 문제는 시간초과를 넘지 않는 게 관건인 문제라서 에라토스테네스의 체를 활용하여 Time Complexity를 획기적으로 줄여야만 하는데, 이 문제는 에라토스테네스의 체를 포함해..

인과율 : 모든 일에는 원인과 결과가 존재한다. 원인 없이 결과가 존재할 수 없다. 위와 같은 인과율을 시간의 흐름으로 봤을 때 물리학에서는 원인이 시간적으로 결과보다 이전에 일어나야 한다는 조건을 의미한다. 이러한 인과율의 법칙은 무조건적인 법칙으로 이 세상에서 절대 위배되는 일이 없어야 하고 만약 어떠한 개념이 인과율을 성립하지 못하게 한다면 그 개념은 틀렸다고 볼 수 있을 정도로 자명하다. 인과율의 법칙이 왜 자명한 사실이며 무조건적인 법칙일까? 또 하나의 절대적 법칙인 아인슈타인의 상대성이론은 빛보다 빠른 것은 존재하지 않는다고 한다. 만약 어떠한 정보가 빛보다 빠르다면 인과율이 깨져버리는데, 아래 예를 들어 자세히 살펴보자. 총을 든 남자 A가 무방비 상태의 남자 B를 향해 총을 쐈다고 가정해 ..

https://www.acmicpc.net/problem/11758 11758번: CCW 첫째 줄에 P1의 (x1, y1), 둘째 줄에 P2의 (x2, y2), 셋째 줄에 P3의 (x3, y3)가 주어진다. (-10,000 ≤ x1, y1, x2, y2, x3, y3 ≤ 10,000) 모든 좌표는 정수이다. P1, P2, P3의 좌표는 서로 다르다. www.acmicpc.net 다시 한번 내 머리가 좋지 않다는 것을 깨닫게 해 준 문제. 애초에 종이랑 펜 없이 머리만 굴려서 절대 풀 수 없었다. 여차저차 나름대로 풀이법을 생각해서 돌려봤지만 4연 실패를 안겨주었다. 뭐가 문제였을까 찾아본 결과 아무리 double형이라도 그 수가 크다면 부동 소수점 정밀도 문제가 생겨 틀리는 경우가 있다고 했다. 전공자 ..

알고리즘은 맞았지만 생각지도 못한 이유로 시간초과에 걸려서 고생한 문제다. 다이나믹 프로그래밍을 이용해 누적합을 저장하는 dp 테이블을 생성하고 그 테이블을 이용해 Time Complexity를 줄이는 문제. 처음 문제를 보고 익숙한 누적 합 문제라 바로 dp 테이블을 만들고 문제를 풀었는데 아뿔싸 시간초과가 났다. 내가 푼 방식은 dp 테이블을 열 기준으로 한 줄씩 생성하는 것이다. 아무리 머리를 굴려도 내가 푼 방식보다 더 빠르게 동작하는 방법이 생각나지 않아 해답을 찾아봤는데 나랑 알고리즘이 똑같았다. 다른 점이 하나 있었는데 나는 반복문이 돌 때마다 System.out.print를 하면서 답을 출력했는데 풀이에는 StringBuilder sb에 답을 저장해 놓고 마지막에 sb를 출력하는 형식이었다..

1월 17일 학교에서 열리는 DGB 금융그룹 입사 설명회에 다녀왔다. 자세히는 모르지만 금융학과 교수님의 제자가 대구은행 인사팀에 계셔서 교수님의 부탁으로 오신 것 같았다. IT 직군이 아닌 일반 행원에 대해서만 설명해 주실 것 같아서 가지 말까 고민했는데 다행히 IT 직군 또한 언급해 주셔서 여러모로 도움이 되었다. 작년에 신입 행원 43명 중에 18명이 IT 직군이었다는 소식을 듣고 생각보다 많은 채용자 수에 내심 놀랐다. 의외는 IT 직군 또한 NCS를 본다는 것인데 이거는 차차 생각해 보자.. 내세울 건 학점밖에 없는데 이력서에 학점 적는 빈칸도 없다는 것도 충격이다. 대구은행 다음에 공기업 금융 회사 설명회도 있었는데 관심없으니까 패스하고 바로 집에 왔다. 결론 : 코테 공부랑 금융권 대회 많이..

나름대로 Time Complexity를 생각해서 배열을 정렬하고 첫 번째 인덱스의 나무와 두 번째 인덱스의 나무의 차를 계산하면서 총합을 더해갔는데 계속 틀려서 다른 방법을 생각했다. 배열을 정렬하지 않고 이진탐색을 이용하는 방법인데, 주어진 배열과 수가 커서 알맞은 방법인 것 같다. 나무 중에서 가장 길이가 긴 나무의 높이를 top, 바닥을 down으로 두고 위아래로 이진 탐색을 진행한다. 만약 높이가 middle일 때 모든 (나무 높이-middle)의 합이 구하고자 하는 높이와 같다면 답이 구해진다. 위와 같이 숫자가 정확히 나누어 떨어지지 않는다면 middle이 아니고 middle-1이 답일 것이다. 숫자의 범위가 매우 클 떄 이진탐색을 고려해 보자. https://www.acmicpc.net/pr..

수정본) 양자역학이란. 모든 것이 확률적으로 존재한다는 뜻. 위치와 속도를 알면 미래를 정확히 예측할 수 있다는 고전역학에 정확히 위배된다. 일단 양자역학을 설명하기 위해서는 불확정성의 원리를 알아야 하는데 그것은 다음과 같다. 이 세상에서 모든 물질은 입자와 파동 둘 중에 하나다. 그렇다면 어떠한 물질이 입자인지 파동인지 어떻게 알 수 있을까? 바로 이중슬릿 실험을 통해 확인할 수 있다. 위 그림처럼 이중슬릿에 어떠한 물질을 통과시켰을 때 만약 그 물질이 입자라면 반대편에 두줄현상이 생길 것이고 파동이라면 물결파 현상이 생길 것이다. 입자는 야구공으로 생각하고, 파동은 물결로 생각한다면 이해하기 쉬울 것이다. 이렇게 이중슬릿 실험을 통해 물질을 확인할 수 있는데, 여기서 중요한 문제가 하나 발생한다. ..

문제를 푼 시간의 9/10을 문제를 잘못 이해하고 풀었다. 이러한 좌표 DFS 문제를 좋아하는데 오랜만에 풀어서 감을 잃어서 고생했다. 이 문제의 핵심은 치즈를 기준으로 DFS를 돌리는 것이 아니라 공기를 기준으로 DFS를 돌리는 것이다. 또한 뒤통수를 한 대 맞은듯한 기분이든 fake가 있었는데 좌표의 가장자리 부분에는 치즈가 놓여있지 않는다는 부분이다. 이러한 문장의 의미는 좌표의 (0,0)이 무조건 공기라는 것이다. 예전 c로쓴 자료구조를 공부할 때 미로 찾기 알고리즘을 배웠었는데 해당 문제에서는 일부러 가장자리 좌표, 즉 좌표를 2개씩 늘려서 문제를 풀었다. 하지만 이 문제는 그러한 수고를 덜어주도록 처음부터 좌표에 제한된 부분을 포함시켜 주었다. https://www.acmicpc.net/pro..

한창 타임머신에 관해 연구하고 있던 찰나에 나의 흥미를 돋우는 제목의 문제를 발견했다. 해당 문제를 풀면서 graph를 class Node를 이용해 구성하였다. 특이점은 Node에 출발점, 도착점, 가중치를 모두 선언하지 않고 도착점, 가중치만 구성하여서 해당 Node가 있는 index가 출발점 역할을 하도록 했다. 처음에는 파이썬에서의 버릇 때문에 위와 같이 구성했는데 생각해 보면 만약 한 정점에서만 출발하는 간선이 많을 경우 비효율 적으로 예상됨에 따라 Node에 출발점, 도착점, 가중치를 모두 선언하고 하나의 ArrayList에 선언하는 것도 좋을 것 같다. 또 벨만-포드 알고리즘에서 왜 V-1번만 반복해야 하는지 의문을 해소하지 못했다. https://www.acmicpc.net/problem/1..

진짜 평범한 배낭 문제 중에 한 문제다. 이 문제에서 N의 범위가 20으로 비교적 작은 범위로 제한되어 있어 ArrayList를 사용하지 않고 크기가 22인 배열을 사용해 문제를 풀 수 도 있었지만 그냥 가변배열을 사용하고 싶어서 ArrayList를 선택했다. 배낭 문제에서 [물품의 수 = 사람의 수] 로, [견딜 수 있는 무게 = 체력] 으로 변환하면 쉽게 풀 수 있다. 2차원 배열 선언하는 게 갑자기 생각이 안 나서 헷갈렸다. 행과 열의 구분을 헷갈리지 않도록 확실하게 기억해야 할 필요가 있을 듯 https://www.acmicpc.net/problem/1535 1535번: 안녕 첫째 줄에 사람의 수 N(≤ 20)이 들어온다. 둘째 줄에는 각각의 사람에게 인사를 할 때, 잃는 체력이 1번 사람부터 순..