BOJ
-
[BOJ] 16236번 - 아기 상어 (삼성 SW 기출 + deque 고찰2)BOJ 2021. 4. 23. 16:11
이번주 삼성 SW역량 테스트를 준비하면서 풀어 봤던 문제들을 풀어보는 중이었다. 그래서 문제들 중 상어 관련 문제인 아기 상어를 다시 풀어봤다. bfs() 알고리즘은 첫번째 원소 pop()과정을 매번 하므로 당연히 deque를 쓰는 것이 시간을 줄인다고 생각했다. 그런식으로 쭉 문제들을 풀어보다가 이번 문제에서 의문점을 하나 품게 되었고, 오늘 몇 가지 실험을 한 뒤 알게 되었다. 우선 문제에 대한 풀이를 해보자. 저번에 풀었던 코드와 이번에 풀었던 코드와의 차이점은 오직 자료구조 하나이다. bfs() 에서 list() 를 쓰느냐 deque()을 쓰느냐 인데... 왜 deque()이 느릴까? 답은 풀이 이후 설명하겠다. www.acmicpc.net/problem/16236 16236번: 아기 상어 N×N..
-
[BOJ] 19237번 - 어른상어 (삼성 SW 기출)BOJ 2021. 3. 23. 02:10
최근에 다시 삼성 SW 역량 테스트 관련 문제들을 풀어 보았다. 포스팅 한 것 외에 톱니바퀴 문제 등의 문제들을 풀어 보았다. 그 중에서도 어른 상어... 진짜 상어 관련 문제들은 항상 구현할 때마다 머리가 터질것 같았다. 아직 실력이 부족한 것 같다. 별 다른 알고리즘은 필요없고, 말 그대로 구현, 시뮬레이션 문제들이다. 보통 삼성의 문제들은 구현문제들이 많이 출제되었던 것같다. 구현과 완전탐색이 주된 문제로 나왔다. 카카오의 경우도 구현문제가 적지않게 출제되곤 한다. 하지만 이런식의 구현문제와는 느낌이 살짝 다르다. 예를들어 자료구조를 활용하여 N^2을 NlogN 이나 N 방법으로 계산이 가능하게 하는 이런 방법들을 카카오에서는 많이 봤던 것 같다. 이번 문제도 역시 구현 문제이다. 앞으로 어떤 것을..
-
[BOJ] 1043번 - 거짓말 (Union - Find 정리)BOJ 2021. 3. 19. 15:40
최근에 서로소의 집합에 대해서 공부를 해봤다. 뭔가 새로운 것을 배운다는게 마냥 싫지 만은 않았고, 생각보다 신기했다. 첫번째 문제는 백준사이트의 1717번 문제이고 이 문제를 풀기 전에 풀어본다면 좋을 것 같다. 기본적인 문제로 Union - Find 자료구조를 이해하는데 도움이 많이 됐다. (백준의 알고리즘 분류에서 Union - Find는 서로소의 집합으로 표기 되어있었다.) www.acmicpc.net/problem/1717 1717번: 집합의 표현 첫째 줄에 n(1 ≤ n ≤ 1,000,000), m(1 ≤ m ≤ 100,000)이 주어진다. m은 입력으로 주어지는 연산의 개수이다. 다음 m개의 줄에는 각각의 연산이 주어진다. 합집합은 0 a b의 형태로 입력이 주어진다. 이는 www.acmic..
-
[BOJ] 16932번 - 모양 만들기BOJ 2021. 3. 17. 13:57
이전 글의 포스팅에서 시간초과를 다루었고 이번에도 시간초과에 관해 포스팅 할 것이다. 글쓴이는 문제들을 풀면서 새로운 방법이라던지, 내가 새로 알게된 것들에 대해서 주로 글쓰는 편이다. 개발에 관한것들도 써내려가야 할 것들이 많은데.. 현재는 알고리즘 문제 푸는 것이 좀 더 재밌는것 같다. 저번과 같이 직관적으로 모든 경우의 수를 빠른 시간 내 짜봤다. 테스트 케이스는 돌아가나 문제가 노린것이 그건 아니였나보다. 첫번째 시도 : 모든 경우에서의 bfs를 돌려봤기 때문에 실패했다. 두번째 시도 : bfs를 만들 때 항상 check배열을 만들었으므로, check배열의 횟수를 줄이기 위하여 해당하는 조건만 bfs를 돌리게 했다. 역시나 둘다 시간초과이다.. 답을 노린것이 아니라 어떻게 효율적으로 할 것이냐가 ..
-
[BOJ] 17089번 - 세 친구BOJ 2021. 3. 17. 11:33
완전탐색 문제들을 볼 때마다 시간초과로 고생했던 것 같다. 2020년도 카카오 '외벽점검'이란 문제 역시 완전탐색 문제로 풀었을 때, 시간을 어떻게 줄여야 하는 지 몰라 해설을 봤던 것 같다. 카카오 문제 만큼은 그냥 풀고싶었는데,, 더 이상 시간 뺏길 순 없어 봤다. 시간이 날 때마다 문제들을 하나씩 풀어보는데, 여전히 감도 안 잡히는 문제들이 많고 어떻게 접근해야할 지 모르는 문제들이많다. 많은 유형들을 여러번 풀어보고, 숙달이 된다면 문제를 보는 눈이 조금은 달라지지 않을까 생각이든다. www.acmicpc.net/problem/17089 17089번: 세 친구 첫째 줄에 사람의 수 N(3 ≤ N ≤ 4,000), 친구 관계의 수 M(0 ≤ M ≤ 4,000)이 주어진다. 둘째 줄부터 M개의 줄에는..
-
[BOJ] 1325번 - 효율적인 해킹(deque, list 고찰)BOJ 2021. 3. 16. 11:18
요즘 알고리즘들이 잘 안 풀리곤해서 몇 번 끄적이다 만 문제들이 많았다. 다시 마음먹고 천천히 쉬운문제부터 풀어볼까 하다가 이 문제에서부터 막혔다.. ㅋ.ㅋ 하지만, 이 문제에서 deque의 효율성을 알 수 있는 계기가 되었다. 글쓴이는 항상 bfs 구현 때마다 대수롭지 않게 queue를 list로 구현하곤 했다. 그 이유는 list역시 deque구조와 비슷하게 원형 큐로 이루어 졌다고 생각했다. 이 문제를 풀기 전까지는.... 조만간 깃에 각 리스트와 스트링 method의 Big-O 개념을 정리해야 될 것 같다. 단순한 bfs문제인 줄 알았던 문제에서 시간초과나는 이유를 알아버렸으니 deque를 이용해서 푸는 건 금방이였다. 나는 얼마나 시간초과가 나는지 계산해보고 싶어 time 함수를 이용해 제일 앞..
-
[BOJ] 14725번 - 개미굴 (Trie 자료구조 )BOJ 2021. 3. 11. 22:49
이번에 포스팅 하게 된 것은 바로 문자열 알고리즘 중 하나인 Trie 자료구조 이다. 맨 처음에 뭔지 모르고 있다가 한 번 알게 된 뒤로 신기하고 기억해두면 좋을 것 같아 한 번 글로써 정리 해보았다. 간단하게 말하자면 문자열 검색시 시간복잡도를 문자열의 길이인 M 즉 O(M)만큼 줄여주는 자료구조이다. 예를들어 여러개의 단어들이 있다고 가정하자. ["ABC", "ABCD", "ABD", "ACBD", "ACD"] 의 단어들이 있다고 보겠다. 트라이 자료구조에서는 이 문자열들의 저장 형태는 아래의 그림처럼 저장이 된다. (하위 코드도 참조) 먼저 첫번째 원소인 "ABC" 를 대입 해보자. 파이썬의 경우에는 dictionary를 이용하여 구현 할 수 있게 되고, C언어의 경우 포인터를 활용해서 구현 해놓은..
-
[BOJ] 1238번 - 파티BOJ 2021. 3. 9. 22:00
아는 형과 같이 알고리즘을 풀다가 이 문제에서 좋은 것을 배워 포스팅 해보려고 한다. 배운 만큼 블로그도 한 번 홍보해보겠다. (좋은글 많아요~!) degurii.tistory.com/ 데구리 블로그 웹 개발과 알고리즘을 공부합니다. degurii.tistory.com 다시 본론으로 돌아가 보자. 단순히 문제만 봤을 때는 다익스트라 혹은 플로이드 와샬 알고리즘으로 풀 수 있을 것 같아 안 풀고 넘어가려고 했지만, 아는 형 말을 듣고 얼른 기억 해놨다가 오늘 풀게 되었다. 물론 실제로 다익스트라로 이 문제를 풀 수 있을 것 같지만, 점의 제한 개수가 많아지거나 한다면 시간이 좀 빠듯할 수 있다. 플로이드로 풀기엔 O(N^3) 이기 때문에 시간 초과가 날 것이다. www.acmicpc.net/problem/..