본문 바로가기

[Algorithms]

 (38)
BOJ.2931번.가스관 BFS로 양끝에서 탐색하고, 가스파이프가 끝나는 지점을 정한다. 정한 지점에서 어떤 파이프가 적절한지를 골라넣으면 된다. Java, Python 두가지 모두 풀어보았다. 2931번: 가스관 www.acmicpc.net in Java import java.util.*; import java.io.*; class BOJ2931gaspipe { static int r, c, my, mx, zy, zx, fy, fx; static int[] dy = { -1, 1, 0, 0 }; static int[] dx = { 0, 0, -1, 1 }; static char[][] europe; static boolean[][] check; static ArrayList ans = new ArrayList(); public..
BOJ. 1766번.문제집 간단한 위상정렬 문제다. 알고리즘 문제는 역시 꾸준히 느낌을 가지고 가는 것이 중요한 것 같다. 요즘 보면 데이터 엔지니어링 분야에서 자바와 파이선(+스칼라)는 거의 필수언어가 되어가고 있는 느낌이다. 두가지 언어를 모두 쵸큼 다뤄본(?) 내가 할 일은, 까먹지 않고 꾸준히 사용하면서 기본기를 계속 챙기는 것이지 않을까 싶다ㅎㅎ . 사실 N사와 K사 모두 면접을 거치면서 괴로운 시간이였지만 많이 배웠다고 생각한다. 누군가는 한번에 합격하기도 하지만, 또 누군가는 여러 시행착오를 겪으면서 가기도 한다. 아직은 방향이 중요하지 않을까. 1766번: 문제집 첫째 줄에 문제의 수 N(1 ≤ N ≤ 32,000)과 먼저 푸는 것이 좋은 문제에 대한 정보의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 둘째 ..
BOJ. 21610번. 마법사 상어와 비바라기 시간이 조금 남아서 삼성에서 낸 구현문제를 풀어보았다. 매일같이 풀던 알고리즘 문제를 한 2주 쉬었더니 또 그렇게 낯설다ㅎㅎ. 문제는 어렵지 않고, 요구하는 내용을 그대로 구현하기만 하면 된다. 다양하게, 또 습관처럼 사용하지 않으면 금새 낯설어지는게 프로그래밍 언어인것 같다. 나만 그런가 했는데, 근래에 본 면접장에서 면접관님들께서도 그렇다 하셨다. 현업 최정상급 고수분들이시지만(물론 긴장을 풀어주시려는 의도일 것이다^^) 그렇게 겸손하게 말씀하시는 걸 보고 많은 것을 느꼈다. 꾸준하게 사용하고, 갈고 닦아야 그 언어를 그 언어'답게' 사용할 수 있는 것 같다. 21610번: 마법사 상어와 비바라기 마법사 상어는 파이어볼, 토네이도, 파이어스톰, 물복사버그 마법을 할 수 있다. 오늘 새로 배운 마법은 ..
BOJ. 2042번. 구간합 구하기 구간합 구하기 문제는 세그먼트 트리라는 자료구조를 사용해서 푸는 문제이다. 정해진 조건에 따라 구간합을 구하고 싶은 구간을 특정지어 주는데, 구간이 주어질때마다 계산을 하게되면 결국 완전탐색법으로 푸는것과 다를바가 없다. 그러면 최소 n^4의 복잡도가 나오게 되고 당연히 시간초과가 발생한다. 세그먼트 트리를 활용하면 이 복잡도를 nlogn에까지 줄일수 가 있어 굉장히 유리하다. 세그먼트 트리에 대한 자세한 내용은 아래 블로그를 참고하면 좋다. https://blog.naver.com/ndb796/221282210534 41. 세그먼트 트리(Segment Tree) 이번 시간에 다룰 내용은 여러 개의 데이터가 연속적으로 존재할 때 특정한 범위의 데이터의 합을 구하는 ... blog.naver.com 이번 ..
PGM. 신규아이디 추천 programmers.co.kr/learn/courses/30/lessons/72410?language=java 코딩테스트 연습 - 신규 아이디 추천 카카오에 입사한 신입 개발자 네오는 "카카오계정개발팀"에 배치되어, 카카오 서비스에 가입하는 유저들의 아이디를 생성하는 업무를 담당하게 되었습니다. "네오"에게 주어진 첫 업무는 새로 programmers.co.kr N사 면접에서 떨어지고 나서, 다시 초심으로 돌아가 기초부터 꼼꼼하게 다지기로 마음먹었다. 떨어진 아쉬움도 컸지만, 부족한 부분을 다듬고 채워야 할 부분을 알게된 소중한 시간이였다. 앞으로 인턴 및 정규직 시험도 몇개 남았는데, 급하게 욕심내기보단, 여유를 가지고 차근차근 밟아나가자! 이 문제는 전혀 까다롭지 않는 문제지만, 정규표현식을 연습하..
BOJ. 1194번. 달이 차오른다 가자 BFS + 비트마스킹 문제다. BFS탐색을 체크할 boolean 배열을 3차원으로 만드는 것에 주의하면 그렇게 어렵지 않다. 왜냐면 각 상황에서 들고있는 키의 상황(몇개를 가지고 있는지, key-state) 가 다를 수 있기 때문이다. 따라서 3차원 체크배열을 선언하고, 각 키를 가지고 있을 때 문 여는 상황을 비트마스크로 비교한다면 꽤 빠른 수행시간으로 문제를 풀 수 있다. www.acmicpc.net/problem/1194 1194번: 달이 차오른다, 가자. 첫째 줄에 미로의 세로 크기 N과 가로 크기 M이 주어진다. (1 ≤ N, M ≤ 50) 둘째 줄부터 N개의 줄에 미로의 모양이 주어진다. 같은 타입의 열쇠가 여러 개 있을 수 있고, 문도 마찬가지이다. 그리고, www.acmicpc.net im..
SWEA. 5607. 조합(페르마의 소정리) 그냥 풀면 터진다. 조합의 경우의 수가 매우 커지기 때문이다. 결과값은 모듈러 연산 후의 값을 출력하고, 연산하는 모듈러 값은 소수이므로 페르마의 소정리를 이용해서 구현하면 된다. 모듈러 연산을 제곱형식으로 바꿀 수 있다는게 아이디어의 핵심이다. 이후의 거듭제곱 함수는 분할정복 방식으로 바꿔서 복잡도를 logn으로 낮춰주는것도 중요하다. 이어서 뤼카의 정리도 알아두면 좋다. 페르마의 소정리 - 나무위키 먼저, 페르마의 소정리는 다음과 동치이다. ppp가 소수라면, np≡n(mod p) n^{p} \equiv n \left(\text{mod}\ p \right) np≡n(mod p) n=0n=0n=0일 경우는 자명하다. 이항정리에 의하면 (n+1)p=np+∑n=1p−1(pn)+1\displaystyle n..
BOJ. 16562번. 친구비 평범한 disjoint-set문제. 나는 적용하기 쉬운 union-find로 해결했다. 다만 실수가 있었는데, parent배열을 다 구해놓고, 부모를 찾을 때, parent의 값을 그대로 사용했다;;; 최종적으로 루트값을 찾을때는 find함수를 사용하도록 하자! www.acmicpc.net/problem/16562 16562번: 친구비 첫 줄에 학생 수 N (1 ≤ N ≤ 10,000)과 친구관계 수 M (0 ≤ M ≤ 10,000), 가지고 있는 돈 k (1 ≤ k ≤ 10,000,000)가 주어진다. 두번째 줄에 N개의 각각의 학생이 원하는 친구비 Ai가 주어진다. ( www.acmicpc.net package week_13; import java.io.BufferedReader; import jav..
BOJ. 2933번. 미네랄,미네랄2 문제는 미네랄과 미네랄2가 동일하며, 같은소스로 시간차 거의 없이 통과된다. 구현(시뮬레이션) + BFS 조합의 문제이다. 클러스터가 다른 클러스터 더미에 매달리는(?) 예외를 잘 해석하면 풀 수 있다. 예외케이스를 처리하는데 생각보다 시간이 엄청 오래 걸렸다. 1. 막대기를 쏘는 방향을 좌,우 번갈아가며 선택한다. 2. 방향에 맞춰 미네랄을 파괴한다 3. 파괴한 상태에서 BFS탐색으로 공중에 떠있는 클러스터와, 아닌 클러스터를 구분한다. 4. 공중에 떠있는 클러스터만을 아래로 최대한 하강시킨다. 1,2,3번은 금방 처리했으나 4번에서 시간이 좀 걸렸다. 그냥 클러스터를 한칸씩 내려보며 안겹칠때까지 확인해보는 방법이 편하다. 각 라인마다 가능한 움직임을 계산하고, 그 최소값을 다시 계산하려다보니 복잡해졌..
BOJ. 11437번. LCA LCA 알고리즘은 누가 처음 생각했을지,,, 정말 세상은 넓고 똑똑한 사람들은 많다^^. Lowest Common Ancestor의 약자로, 최소 공통조상을 찾는 알고리즘이다. 핵심은 다음과 같다. 1. 각 노드의 깊이와 부모 노드를 저장해둔다. 2. 비교하고자 하는 두 정점이 주어지면, 두 정점의 같은 레벨에 있는 부모 노드를 최소로 움직여 찾는다. -> 어느 한쪽에 맞추는게 아마 최소! 3. 이렇게 레벨을 맞추고 나면, 한단계씩 위로 올라가면서 각자의 부모노드가 일치할 때까지 반복한다. www.acmicpc.net/problem/11437 11437번: LCA 첫째 줄에 노드의 개수 N이 주어지고, 다음 N-1개 줄에는 트리 상에서 연결된 두 정점이 주어진다. 그 다음 줄에는 가장 가까운 공통 조상을..

티스토리툴바