전체 글
-
[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 이런 순으로 탐색은 못하지 않는가? 라는 것이다. 계속되는 고민끝에 하나 생각한 것은 일단 백트래킹은 완전탐..
-
[KAKAO] 자물쇠와 열쇠 (2020 KAKAO BLIND)KAKAO/level 3 2021. 2. 19. 14:07
몇 주전에 이 문제를 봤을 때 브루트포스 인걸 알았지만, 탐색할 때 백트래킹으로 해야한다고 생각했다. 그래서 삼성 SW 기출문제를 몇 개 풀어보고 최근에 다시 와서 봤다. 문제를 보자마자 아무 생각 없이 백트래킹으로 짜봤는데.. 아직 실력이 부족한 지 시간초과가 계속 뜨긴 했다. 이유는 디버깅을 통해 알았지만, 디버깅을 하면서 이 문제를 백트래킹이 아닌 이중 포문으로 탐색해도 될 것 같다는 느낌이 들었다. 문제를 풀 때마다 느끼는건 어떻게 문제를 접근하냐에 따라서 잘못된 방향으로 빠져버리면 시간을 엄청 잡아먹는다. 어찌보면 수능 수학,과학과 비슷하게 느껴질 순 있다.. 저 시기를 뒤돌아 봤을 때 많은 문제를 푸는것 만큼 좋은게 없던 것 같다. 몰랐던 부분들을 하나 둘, 오답노트를 만들어가며 부족한 것을 ..
-
[KAKAO] 보석쇼핑 (2020 KAKAO 인턴십)KAKAO/level 3 2021. 2. 18. 21:35
어느 순간 level3문제를 풀다가 문득 너무 어렵다고 느껴져 백준 온라인으로 넘어갔다. 거기서 특정 알고리즘 bfs, dfs, 투포인터, greedy, dijkstra, 등 쉬운 몇 문제들을 풀었다. 아직 알고리즘 부분에서 부족한 것들이 많게 느껴져서 기초를 잡고자 함이었다. 다시 돌아와서 확실히 문제들을 풀어보니 문제를 읽다가 어떤 알고리즘으로 풀어야겠다! 라고 생각이 점점 나기 시작했다. 이번문제의 알고리즘은 투포인터 알고리즘으로 풀 수 있었다. 중간에 계속 틀려서 잠시 dp로 풀수도 있을까 생각 했지만 내 로직이 틀렸던 것 같아 계속 수정해서 해봤더니 맞았다. 투포인터 알고리즘 정리할겸 간단하게 요약해봐야겠다. 긴 배열에서 연속된길이를 구할 때 특정조건을 만족시키면서 배열을 O(N)번만 탐색 가능..
-
[KAKAO] 경주로 건설 (2020 KAKAO 인턴십)KAKAO/level 3 2021. 2. 17. 01:30
주로 프로그래머스에서 문제를 풀게되면 카카오 관련 문제들이 많다. level 2부터 계속 풀어 왔지만, 다른 문제들보다 유난히 구현이 어렵고 문제 읽는 양 자체가 많았다. 좋은 문제들이 참 많다고 생각 했고, 어떤 응용 문제들이 많이 나오는지 정리하기 위해 KAKAO 카테고리를 따로 놨다. level2 문제들이 구현에 치중된것이라고 본다면, level3 부터는 기본적인 알고리즘이 동반되어야 풀 수 있고, 어느정도의 센스가 필수적이라 생각한다. (개인적으로 센스는 문제들을 많이 풀어보고 디버깅을 해봄으로써 는다고 생각한다.) 미리 풀었던 문제들도 있기에 그 문제들은 다시 풀어보면서 블로그에 정리할 생각이다. 우선, 경주로 건설을 보자. programmers.co.kr/learn/courses/30/less..
-
[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만큼 ..