본문 바로가기

코딩테스트

 (6)
코딩테스트 알고리즘 - BFS, DFS 그래프 탐색어떤 것들이 연속해서 이어질 때 모두 확인하는 방법Graph : Vertex(어떤것. 노드) + Edge(이어지는 것. 연결선)BFS너비 우선 탐색 : 자기 자식 우선 탐색시작점에 연결된 vertex찾기 -> 찾은 vertex를 queue에 저장DFS깊이 우선 탐색 : 자식의 자식을 우선 탐색 깊이 우선 탐색 : 자식의 자식을 우선 탐색연결된 vertex 찾기 -> 찾은 vertex를 stack에 저장시간복잡도알고리즘이 얼마나 오래 걸리는지Big-OBFS : O(V+E)사용 자료구조BFS검색할 그래프방문 여부 확인(재방문 금지 목적)Queue : BFS 실행
코딩테스트란? 코딩테스트시간 안에 주어진 문제를 푸는 시험적절한 알고리즘을 선택해서 문제 해결각 알고리즘의 이해개념 이해기본 문제, 코드 따라해보기안보고 작성할 정도로 외우기다른 문제 풀어보기(각 10문제씩 정도)실전 노출한문제에 30분 넘지 않게 풀이매일 알고리즘별로 돌아가면서 풀기풀이 방법이 아예 떠오르지도 않을 경우 구글링으로 풀이 검색오답노트 작성어떤 알고리즘을 선택했는지는 중요하지 않다. 선택한 이유, 풀이 방법과의 연결 과정을 설명하자.필수 알고리즘BFSDFS백트래킹시뮬레이션이진탐색GreedyDPMST다익스트라플로이드코딩테스트 풀이 방법풀기전 최대한 구체적 계획 작성다음 세가지 주석으로 써보고 문제 풀이아이디어 : 문제를 어떻게 풀것인지, 어떤 알고리즘을 사용할 것인지시간복잡도 : 내가 설계한 방법이 오래..
프로그래머스 피보나치 수 피보나치 수는 어렸을 때부터 항상 많이 봐왔던 패턴이었습니다. 전에 정처기 공부를 할 때도 재귀함수를 통해 많이 봤었죠. 이번에 문제를 풀 때도 간단하게 재귀함수를 이용하면 쉽겠는데? 라고 생각하고 재귀함수를 통해 간단히 구현하였습니다. public int solution(int n) { int answer = 0; if (n  작은 숫자에 대해선 당연히 시간은 오래 걸리지 않아 테스트를 통과했던 것 같습니다.. 하지만 숫자가 커질수록 재귀함수를 통해 반복되는 연산 횟수가 증가하여 시간초과로 테스트를 통과하지 못했었습니다. 방법이 떠오르지 않아 구글링을 통해 방법을 찾아보니 이전 반복되는 값들을 계속 연산하지 말고, 한번 연산했던 값을 메모리에 저장해서 바로 불러와서 사용하는 동적 계획법(Dy..
프로그래머스 - 명예의 전당(1) 제가 짠 코드는 항상 시간 복잡도가 엉망인 모양이네요.. 알고리즘에 필요한 것들을 공부해야겠습니다. ㅠ 먼저 제가 짠 코드입니다. public int[] solution(int k, int[] score) { List arrList = new ArrayList(); List ansList = new ArrayList(); for (int i = 0; i arrList.get(0)) { arrList.remove(0); arrList.add(score[i]); Collections.sort(arrList); } ansList.add(arrList.get(0)); } int[] answer = new int[ansList.size()]; for (int i = 0; i  ..
프로그래머스 - 모의고사완전탐색 제가 작성한 풀이.. 실력도 없지만 자고 일어나서 딱 풀려고 하니 그냥 기능구현에만 매진한 것이 보이긴 한다..public ArrayList solution(int[] answers) { ArrayList answerList = new ArrayList(); int[] p1 = {1, 2, 3, 4, 5}; int[] p2 = {2, 1, 2, 3, 2, 4, 2, 5}; int[] p3 = {3, 3, 1, 1, 2, 2, 4, 4, 5, 5}; int num1 = 0; int num2 = 0; int num3 = 0; int match1 = 0; int match2 = 0; i..
HashMap을 이용한 빈도수 측정(숫자 짝궁) 프로그래머스 문제를 풀고 다른 사람의 풀이를 보면서 HashMap의 사용을 머리속에 남겨놓기 위해 글을 씁니다. 프로그래머스 해당 문제는 숫자 짝꿍입니다. 제가 풀이했던 방법은public String solution(String X, String Y) { String answer = ""; ArrayList xArray = new ArrayList(); ArrayList yArray = new ArrayList(); String[] xStringArray = X.split(""); String[] yStringArray = Y.split(""); ArrayList arrayList = new ArrayList(); f..

티스토리툴바