본문 바로가기

Algoritm/Coding Interview5

[3.스택/큐] stack, queue 1. Stack : 단어의 의미처럼 데이터를 쌓아 올린다는 의미 : 배열 대신에 사용되는 경우가 있음 : LIFO(Last In First Out) > 마치 접시를 쌓아두었다가 맨 위부터 사용하는 것처럼, 가장 최근에 추가한 항목이 가장 먼저 제거될 항목이라는 것. : 미로 찾기, 괄호 유효성 체크, 재귀 알고리즘 등에 활용 : 직접 new연산자로 객체를 생성하여 사용가능 2. Stack의 연산 stack.pop() 가장 최근 원소 반환 후 제거 stack.peek() 가장 최근 원소 호출 (제거X) stack.push(e) 요소 삽입 stack.isEmpty() 스택이 비어있는 경우 true반환, 요소가 있는 경우 false반환 stack.search() 객체가 존재하는 인덱스 반환(마지막 요소로부터 .. 2020. 8. 31.

[2.연결리스트] 중복없애기, 뒤에서 k번째 원소구하기, 중간노드삭제, 분할, 리스트의합, 회문(연결리스트), 교집합, 루프발견 [ Q1. 중복없애기 ] 정렬되어있지 않은 연결리스트가 주어졌을때 이 리스트에서 중복되는 원소를 제거하는 코드를 작성하라. (임시버퍼가 없다면 어떻게 풀까?) - 내 풀이 - 1. 해시맵 활용(연결리스트 저장용도) 2. 연결리스트를 순회하며 n이 키로 존재하는지 체크 => 존재하지 않는 경우 맵에 를 삽입 => 존재하는 경우 n.prev.next=n.next로 변경 (이게 노드 삭제) * 야 내 문제는 노드클래스 구현하는거가 문제야.. class LinkedNode{ int data; LinkedNode prev, next; public LinkedNode() { // TODO Auto-generated constructor stub } public LinkedNode(int d) { data=d; } .. 2020. 8. 30.

[2.연결리스트] LinkedList, 재귀, LinkedListNode 1. 연결리스트란 ? : 차례대로 연결된 노드를 표현해주는 자료구조 1) 단방향 연결리스트 : 노드는 다음 노드를 가르킨다. 2) 양방향 연결리스트 : 노드는 다음 노드와 이전 노드를 가르킨다. : 특정 인덱스 접근시 상수시간에 접근 불가 (처음부터 ~K번까지 루프를 돌려야하기 때문) : 따라서 시작지점에서 아이템 추가/삭제를 상수시간에 할 수 있는 특정 어플리케이션에서 유용하게 사용됨 2. 단방향 연결리스트 만들기 : LinkedList자료구조를 사용하지 않고 구현 > head의 노드주소를 참조하는 방법 사용 : 즉, 노드속 필드로 노드를 연결 class Node{ Node next=null; int data; public Node(int d) { data=d; } void appendToTail(in.. 2020. 8. 25.

[1. 배열/문자열] 중복확인, 순열확인, URLify(대체), 회문순열, 하나빼기, 문자열압축, 행렬회전, 0행렬, 문자열회전 [ Q1. 중복이 없는가 ] 문자열이 주어진 경우, 이 문자열에 같은 문자가 중복되어 등장하는지 확인하는 알고리즘을 작성하라. 추가적으로 자료구조를 사용하지않고 풀 수 있는 알고리즘 역시 작성하라. - 내 풀이 - 1. 문자열을 char배열에 넣기 2. 각배열의 요소를 반복처리 > hashmap에 있다면 중복있음 종료, 없다면 hashmap에 요소로 추가 boolean charDup(String s) { char[] char_set=s.toCharArray(); HashMap map=new HashMap(); for(char c:char_set) { if(map.containsKey(c)) { return true; } else { map.put(c, 0); } } return false; } 더보기 *.. 2020. 8. 25.

이전 1 2 다음

티스토리툴바