Algorithm

고득점 키트 깊이/너비 우선 탐색(DFS/BFS)에서 가장 난이도가 쉬운 '타겟 넘버' 문제이다.DFS로 푸는 문제인데, DFS와 BFS의 기본 구조를 모르면 헤맬 수 있다.

가볍게 사내 코테 준비하던 중 못풀어봤던 레벨 1 문제가 있어서 풀어봤다!내가 생각하기에.. 1레벨은 아닌거같고 2레벨에서 조금 쉬운문제? 같다..왜냐하면 너무 생각없이 풀면 시간초과가 뜰 수 있기 때문이다.

q에 지나갈 수 있는 경로가 쌓이는데 결국 중간의 'maps\[newx]\[newy] == 1'조건으로 인해 최단 경로만 남고 나머지는 소멸된다. 해당 경로로 지나가면 그 경로에 지나왔던 칸 수를 저장해놓기 때문이다.

딱봐도 DFS가 생각나는 문제!언젠가 BFS로 풀어보고 싶긴 하다.<내 답안><답안 해석>연결된 노드의 갯수를 구하는 것이 아니라, 연결된 노드끼리 한 묶음(한 개)임을 유의해서 풀면 된다.

bfs로 풀었다.defaultdict이랑 deque를 사용하는 걸 좋아해서(ㅋㅋ) 자주 사용하는데, 굳이 안써도 풀릴 것 같다.visit이라는 유사 dictionary에서 방문과 동시에 쌓인 변환 갯수를 담아주었다. key = 단어(word), value = count

이분탐색을 사용하는 문제!오랜만에 풀어봤더니 생각하느라 조금 시간이 걸렸다..이분탐색은 간단하게 설명하면 중간부터 답을 찾아가는 기법이다.

DP 중에서도 Top down 방법인 memoization(메모이라이제이션)으로 풀어야 풀리는 문제

시뮬레이션 문제!풀어본 프로그래머스 문제 중에 가장 삼성전자 코딩테스트 유형이랑 비슷해보인다.아이디어는 간단하지만 구현이 까다롭다.

1에서부터 각 노드까지(2,3,4,...n)의 최단 거리들을 구해주고, 그 최단거리 중에 최댓값을 가지는 노드의 수를 구하는 문제이다.최단거리가 최대값인 것을 구하라? == 다익스트라를 사용해라 특정한 하나의 지점에서 모든 지점까지의 최단 거리를 알아낼 수 있는 알고리

처음에 슬라이싱 사용해서 풀었는데 역시나 레벨 3라 그런지 효율성 테스트 1에서 실패했다..

처음에 아무 생각 없이 while문 돌려서 stones 모든 Inde에 -1씩 해주고 k번 이상 뛰어넘게 되면 while문 탈출해서 답을 구하도록 짰는데, 역시나 효율성 테스트에서 통과하지 못했다.한 번 통과 못하니까 바로 이진 탐색 써야겠다는 생각이 들었다..정확성

처음에 다익스트라 알고리즘으로 풀었다가 테스트케이스 1,2,6번 뻬고 통과를 못해서 계속 고민하다가 결국 구글링의 힘을 빌렸다.알고보니 그리디 알고리즘 중 하나인 Kruskal 알고리즘 을 사용하면 쉽게 풀리는 문제였다..!굵직한 알고리즘은 얼추 다 풀어봤다고 생각했는

최대값을 찾아 최대값을 하나씩 감소 시켜줌으로써 쉽게 풀 수 있는 문제!우선순위큐만 알고 있으면 쉽게 풀 수 있다.나는 heapq를 최대 힙으로 구현해서 풀었다!

처음에 문제 잘못 읽고 이해해서 한참 헤맸다..문제를 잘 읽어보니 왜 내가 실행했을 때 틀리는지 깨달은..앞으론 문제를 꼼꼼히 읽자!현재 시점에서 처리 가능한 작업목록 우선순위큐(q)에 넣기 (이 때, 처리 시간 기준으로 오름차순 정렬)현재 시점에서 처리 가능하지 않은

다익스트라 + 완전탐색으로 풀었다.처음에는 문제보고 어떻게 풀지 생각이 많았는데.. 잘 정리해서 풀어보니 꽤 풀만했다!효율성 완전 간신히 통과했는데, 구글링해보니 플로이드-워셜로 푸는게 정석 같다.

bfs로 최소비용 업데이트해주면서 풀면 되겠다! 해서 풀었다가 마지막 테스트케이스를 통과 못해서 정말 애먹었던 문제..구글링을 해보니 3차원 배열을 사용해 각 경로의 저비용을 계속 업데이트해줘야하는 문제였다..처음에는 dp 풀듯이 bfs로 계속 최소 비용 저장해주면서

다익스트라로 풀었었는데, 플로이드-워샬로 풀어보고 싶어서 해당 알고리즘을 공부하고 적용해서 풀어봤다.모든 node 사이의 최단 경로를 찾는 탐색 알고리즘.

문제 설명n명의 권투선수가 권투 대회에 참여했고 각각 1번부터 n번까지 번호를 받았습니다. 권투 경기는 1대1 방식으로 진행이 되고, 만약 A 선수가 B 선수보다 실력이 좋다면 A 선수는 B 선수를 항상 이깁니다. 심판은 주어진 경기 결과를 가지고 선수들의 순위를 매기

문제 설명Finn은 편의점에서 야간 아르바이트를 하고 있습니다. 야간에 손님이 너무 없어 심심한 Finn은 손님들께 거스름돈을 n 원을 줄 때 방법의 경우의 수를 구하기로 하였습니다.예를 들어서 손님께 5원을 거슬러 줘야 하고 1원, 2원, 5원이 있다면 다음과 같이

문제는 복잡해보이지만, 상위 노드만 잘 타고 올라가면 쉽게 해결할 수 있는 문제!이번 주에 푼 문제 중에 가장 수월하게 푼 문제다...다음 알고리즘에 따라 문제를 풀었다.1\. graph 생성하기 : graphseller = 추천인, 인덱스2\. 탐색 및 answer

다익스트라, BFS, BFS 같은 그래프 알고리즘을 사용해야 하는 복잡한 구현 문제가 아니라 단순한 구현 문제지만 시간초과, 효율성 테스트케이스가 빡빡한 문제 모음!

포화 이진트리에 대해 정확하게 이해를 못해서 한창 헤맸는데,그거만 빼면 구현 난이도는 높지 않았던 문제!처음에 헷깔렸던게, 포화 이진트리가 모든 노드에서 높이, 즉 depth가 같아야하는 줄 몰라서 조금 어렵게 생각했다.포화 이진트리는 높이(depth)가 일정하다 는

별 2개짜리 문제라 다소 간단한데, 최대한 효율성 있게 풀고 싶어서 최대힙을 구현해 풀었다!사실 최대힙으로 풀지 않고 리스트와 for문만으로도 구할 수 있는 간단한 문제인데,리스트를 활용하면 O(N), heap을 사용하면 시간복잡도가 O(logN)이어서 차이가 꽤 난다

📌 프로그래머스 Level 3 : 억억단을 외우자 레벨 3 치고는 굉장히 쉬워보이지만 파이썬으로 풀면 시간이 너무 빡빡해서 자바로 풀었다.! 📝 내 답안 세그먼트 트리를 사용하면 더 효율성 있게 풀 수 있다. 조금 더 생각해보고 세그먼트 트리를 잘 활용해서

📌 프로그래머스 Level 1 : 체육복 간단한 그리디 문제. 같은 알고리즘을 사용해서 파이썬, 자바 각각 풀어봤다. 📝 내 답안(with 파이썬) 📝 내 답안(with 자바)

처음에 문제를 이해 못해서 조금 헤맸다..한 뱃길의 양쪽 끝 등대 중 적어도 하나는 켜져 있도록 등대를 켜 두어야 합니다.이 문구를 자세히 기억해 두자..다음 알고리즘에 따라 풀었다.1\. 그래프, 등대 켜짐 유무 판단할 리스트 생성2\. 우선 초기 리프 노드 큐에 담

특정 노드까지 최단 거리를 구하는 문제! 즉 다익스트라 알고리즘 을 활용하는 문제이다.

회사에서 한 달간 장기 해외 출장을 갔다왔더니 알고리즘 풀이 연습을 계속 못하고 있었다.

요즘 회사일이 바빠서 자기개발에 소홀해져 있었다.. 반성 중..! 이번주부터는 다시 힘내기~😤5월 말에는 회사에서 진행하는 코딩테스트도 있다!제일 어려운 레벨을 덜컥 신청했는데.. 열심히 해서 꼭 통과해볼 예정이다브루트 포스를 사용해서 푼 문제다!시간복잡도 측면에서

📌 백준 골드 4 : 뱀 제시된 기본 TestCase만 다 통과하면 무리 없이 풀리는 뱀 게임 구현 문제이다. 📝 내 풀이 🔮 풀이 > ### 알고리즘 뱀의 초기 위치와 방향을 설정하고, 사과의 위치를 입력받아 게임 보드에 표시 뱀의 이동 방향을 저장하는