BOJ
-
[BOJ] 2096번 - 내려가기BOJ 2021. 3. 9. 01:30
solved.ac 에서 클래스 관련해서 새롭게 업데이트 되면서, 단계별로 문제를 풀어보는 중이다. 마땅히 좋은 문제들이 없고, 대부분 포스트 했던 문제이거나 쉬운 구현 문제들 이었기 때문에 오늘에야 블로그를 쓰게 된다. 이번에 풀어볼 문제는 간단한 dp 문제였고, 메모리만 잘 해결하면 되는 문제였다. 메모리에 관해서 블로그 글을 쓴 적이 없다고 생각해서 이번 글을 적게 되었다. www.acmicpc.net/problem/2096 2096번: 내려가기 첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중의 하나가 된다. www.acmicpc.net 프로그래머스에서 비슷한 문제를 풀어 봤던 것 같..
-
[BOJ] 1766번 - 문제집BOJ 2021. 3. 4. 17:36
최근 코테를 본 SW마에스트로에서 위상정렬 관련 문제가 나와서 알고리즘을 공부한 뒤 여러 문제들을 풀어봤다. 위상정렬에서는 충분한 조건이 주어지지 않으면 답이 여러가지가 나올 수가 있는데 이 과정에서 (항상 ~ 가 작은 순서로 한다) 등의 조건이 주어졌을 때 어떻게 해야할 지 잘 알려주는 문제이다 예를 들어 사람 3명이 옆의 조건을 만족하여 출력한다고 해보자. 2번이 1번보다 앞에 나와야 한다. 이 조건을 만족하도록 줄을 세울 때, 정답은 [ 2, 3, 1 ], [ 2, 1, 3 ], [ 3, 2, 1] 이런식으로 여러가지 답이 나올 수 있다. 하지만 여기서 위의 조건을 만족하고 가능한 나이가 많은 순서대로 출력한다고 생각하면 ( 가정 1 < 2 < 3 ) 답: [ 3, 2, 1 ] 이 될것이다. 이와 ..
-
[BOJ] 9466번 - 텀 프로젝트BOJ 2021. 3. 1. 04:17
어제 SW마에스트로 코딩 테스트를 보면서 다시 한 번 좀 더 많은 문제를 풀어봐야겠다고 생각했다. 자바 문법도 공부하고 있고, 창업 활동에서 했던 프로젝트 디자인 수정도 해야해서 정신이 없기도 하지만 알고리즘은 꼬박꼬박 푸는 중이다.. SW마에스트로도 몇 문제 더 풀었지만 알고리즘을 쓸 것 없이 완전 구현 문제였기 때문에 포스트를 굳이 하지 않기로 했다. 물론 구현 중 어려웠던 부분이 있더라면 쓰게 될 것 같다. 이번 문제에서는 dfs 부분(약한 부분이라 생각)의 문제를 한 번 풀어봤다. 70% 에서 시간 초과 계속 나서 결국 블로그들을 찾아 해결했다.. 아직까지 어떤 부분에서 답지를 보며 스킬을 익히는것이 더 이득이고, 그렇지 않은 지 정확히 모르겠다. 어떤 사람은 답지를 보는게 좋다고 말하곤 한다. ..
-
[BOJ] 2579번 - 계단오르기BOJ 2021. 2. 25. 21:41
요즘 부족한 유형(dp, 백트래킹, 구현 등) 위주로 공부를 하고 있다. 물론 맨날 부족한 부분만 하는건 아니고 재밌어 보이는 문제를 풀 때도 있다. 문제가 잘 안 풀리는 것들은 고민 좀 하다가 다른 문제를 푼다. 답지를 봐 버리면 뭔가 스스로 좀 그래서,,, (진짜 안 될 때는 보기도 한다. ㅋ.ㅋ) 이번에는 저번에 풀어보려다가 풀지 못했던 DP문제를 오늘 드디어 해결했다. 자꾸 1차원 배열로 하려고 했던 생각을 고치고 2차원 배열을 만든 다음 해결 했다. 아직 많은 문제를 풀어보지 못해 점화식 세우는 것이 익숙하지 않아 오래걸렸다. 그렇게 어려운 문제는 아닌데 확실히 해당 유형을 많이 풀어봐야 됨을 느낄 수 있었다. www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오..
-
[BOJ] 17779번 - 게리맨더링2(삼성 SW 기출)BOJ 2021. 2. 24. 04:55
하루에 한 문제씩 계속해서 풀고있지만, 여전히 문제 하나하나가 어렵게 느껴진다. 좀 낮은 단계씩 차근차근 다시 풀어볼까.. 생각중이다. 친구들도 한 번 씩 보니 나만 그렇게 어렵다고 느낀게 아니라 다행이기도 하다. ㅋ.ㅋ 무엇보다 어떤 문제들을 봤을 때 어떤 알고리즘을 적용하는지, 어떻게 구현 할지 이 두가지를 동시에 길러내기 위해서 여러 문제를 풀어보고 부족한 유형을 풀어보면서 실력을 키워나가야 한다. 항상 얘기했지만, 문제를 잘 못 이해하는순간 1시간은 기본으로 날아간다고 보면 된다. 이 문제를 꼼꼼히 읽어보지 않고, 좌표 값 대충 잡아서 디버깅 하는 데만 진짜 1시간 넘게 걸렸던 것 같다. 아직 행렬에 관해서 편하게 자유자재로 다룰 수 있는 능력이 되지 않는 것 같아 몇 문제 더 풀어 볼 예정이다...
-
[BOJ] 13023번 - ABCDEBOJ 2021. 2. 21. 23:55
이 문제를 첫 시도 때 풀었다가 몇 일동안 고민에 빠졌다.. 내가 아는 dfs가 정확히 뭔지 고민을 많이 했던 문제였다. bfs 와 dfs가 비슷한 개념으로 알고 있었고, 그에 따라서 어떤 노드들을 한 번만 탐색하는 것이라 생각했는데 백트래킹을 dfs로 구현한다. 해서 헷갈렸던 것 같다. 아직까지 완벽하게 이해는 못했지만 어느 정도 개념이 잡히는 것 같다. 내가 아는 bfs, dfs는 노드들의 정점을 한 번만 순회하는 그래프에서의 그런 알고리즘이라 생각했다. 예를 들어 모든 노드들을 한 번 씩 탐색하는 것이다. 여기서 내가 알고싶었던 사실이 이런식으로의 dfs로 풀어버리면 1->3->2->4->5 이런 순으로 탐색은 못하지 않는가? 라는 것이다. 계속되는 고민끝에 하나 생각한 것은 일단 백트래킹은 완전탐..
-
[BOJ] 1939번 - 중량제한BOJ 2021. 2. 16. 16:22
삼성 문제 몇 개를 풀다가 시간초과 때문에 안 되던 것들 때문에 기분 전환 하고자, 이분탐색 문제를 풀었다. 파이썬 시간도 충분히 고려해 주기 때문에 내 로직이 틀렸다고 생각했고, 다른 문제들을 풀어봄으로써 다시 실력을 쌓아야할 것 같았다. 이번 문제에서는 단순 BFS 와 이분탐색 두 가지를 합쳐놓은 것을 바탕으로 문제가 출제 되었다. 보통 이분탐색 문제는 구하고자 하는 것의 참과 거짓을 판별해서 항상 답을 구해왔던 것 같다. 역시 이 문제도 마찬가지로 탐색하고자 하는 중량이 끝점까지 도달하냐 못하냐를 중심으로 구했다. 맨 처음 봤을 때 " 어떤식으로 이분탐색을 할까? " 이 생각까지 시간이 좀 걸렸다. 역시 많이 풀어봐야하나.. 느꼈다. 방법을 알고나니 코드 짜는 것은 그리 어렵지 않아 금방 짰다. w..
-
[BOJ] 17142번 - 연구소 3 (삼성 SW 기출)BOJ 2021. 2. 15. 16:50
단순 BFS 문제라 로직은 쉽게 짰는데 문제를 꼼꼼히 읽지 않아서 계속 83%에서 틀렸다.. 문제를 꼼꼼히 읽겠다는 다짐은 매번하는데 잘 바뀌어지지 않는다. 앞으로는 확실히 이해한 뒤 키보드에 손을 얹는걸로.. www.acmicpc.net/problem/17142 17142번: 연구소 3 인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 바이러스는 활성 상태와 비활성 상태가 있다. 가장 처음에 모든 바이러스는 비활성 상태이고 www.acmicpc.net 바이러스 퍼지는 연구소 문제는 몇 번 나와서 몇번 풀어본 사람이라면 비슷하게 풀었을 것이다. 바이러스 조건을 자세히 봐야한다. 만약 바이러스가 총 6개 중에 2개만 이용했을 때 최솟값을 고르라 하면, 6C2만큼 ..