그 순간에 최적이라고 생각되는 것을 선택해 나가는 방식크게 DFS, BFS가 존재DFS(Depth First Search)깊이 우선 탐색, 일반적으로 BFS에 비해 더 많이 쓰인다.주로 스택 OR 재귀로 구현한다.그래프의 최단 경로를 구하는 문제 등에 사용된다.BFS(
그 순간에 최적이라고 생각되는 것을 선택해 나가는 방식ex) 다익스트라 알고리즘(최단 경로 문제), 허프만 코딩 알고리즘(허프만 트리를 빌드할 때 그리디 알고리즘을 사용)각 단계마다 로컬 최적해를 찾는 문제로 접근해 문제를 더 작게 줄여나가는 형태하위 문제에 대한 최적
DFS, 스택 이용입력으로 들어오는 그래프 연결 정보를 인접 리스트로 만든다.1번 컴퓨터와 연결된 컴퓨터들의 개수만 찾으면 된다.
DFS, 스택 이용 테스트케이스는 맞았는데 틀렸다고 표시된 풀이 \* 틀린 이유: 아파트의 개수를 카운트하는 cnt 변수를 0으로 시작하게 되면 아파트가 하나밖에 없는 단지의 경우 0으로 카운트 되어짐. (0, 0)부터 시작해서 아파트가 존재하는지 판단한다.현재 노
현재 위치에서 곱하기 연산을 했을 때 target값과 가장 가까운 경우 곱하기 선택같은 값이 없을 경우 연산(+, -, \*)을 했을 때 target 값과 가장 가까운 값을 선택target 값과 같아질 때까지 loop 반복1차 풀이: BFS로 안품..ㅋ2차 풀이: BF
연결된 그래프 개수 찾기dfs, stack으로 구현배추가 심어져 있는 index를 찾고 dfs 시작4 방향으로 인덱스가 넘지 않고, 배추가 심어져 있는지(인접 행렬이 1인지) 확인맞다면 인접 행렬의 요소를 0으로 바꾸고, 스택에 푸시dfs를 마치고 왔다면 그래프 개수를
백준 - 신규 아이디 추천
연결 리스트, DFS, 스택으로 구현백준 재귀 제한 때문에 sys.setrecursionlimit(10000) 추가
n이 3보다 큰 경우 계속 반복문을 돌아주며 3으로 나눠준다.숫자 n을 3으로 나눴을 때 나머지가 0인 경우 4, 1인 경우 1, 2인 경우 2를 answer에 문자를 추가해준다.그리고 나머지가 0인 경우 n에 1을 빼준다.반복문을 빠져 나왔을 때 3인 경우는 4로 나
리트코드 - 로그파일 재정렬 람다식
dfs로 푼 근거는? -> 순열은 가능한 모든 경우의 수를 그래프 형태로 나열한 결과라 할 수 있다.재귀로 푼 근거는? -> 입력이 1, 2, 3로 주어졌을 때 1, 2, 3을 한번에 풀지 않고 1, 2, 3으로 작게 나누어 해결하기 위해서 재귀 사용.자기 자신을 호출
순열은 가능한 모든 경우의 수를 모두 포함하지만 조합은 중복된 요소들은 제거한다.시간 초과(순열 풀이로 중복만 제거하려고 함.)시간 통과파이썬 알고리즘 인터뷰
원소들을 문자형으로 형변환을 한 뒤 ASCII 코드 기준 오름차순으로 정렬한다. \[10, 4]인 배열이 있을 때 "10"과 "4"로 변환되고 "1"이 "4"보다 작은 ASCII 값을 가지게 되므로 \[10, 4]가 된다.배열 요소는 compareFunction의 반환
여벌옷이 있지만(reserve) 도난(lost) 당한 사람은 여벌옷이 없는 것과 마찬가지가 된다. 따라서, 이 경우를 먼저 처리해주어야 모든 테스트 케이스에 통과할 수 있다.
정확성 테스트 5/5, 효율성 테스트 0/5
수포자는 수학을 포기한 사람의 준말입니다. 수포자 삼인방은 모의고사에 수학 문제를 전부 찍으려 합니다. 수포자는 1번 문제부터 마지막 문제까지 다음과 같이 찍습니다.1번 수포자가 찍는 방식: 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, ...2번 수포자가 찍는
당신은 폰켓몬을 잡기 위한 오랜 여행 끝에, 홍 박사님의 연구실에 도착했습니다. 홍 박사님은 당신에게 자신의 연구실에 있는 총 N 마리의 폰켓몬 중에서 N/2마리를 가져가도 좋다고 했습니다.홍 박사님 연구실의 폰켓몬은 종류에 따라 번호를 붙여 구분합니다. 따라서 같은
테스트케이스 2개만 통과하고 나머지는 런타임 에러와 시간초과가 떴다.
두 점 사이의 거리를 구하면 되는 문제이다.처음에는 두 점 사이의 거리 공식 Math.sqrt(Math.pow(c1\[0] - c2\[0],2) + Math.pow(c1\[1] - c2\[1],2)) 을 이용해서 풀었더니 13번 ~ 20번 테스트 케이스가 실패로 떴다.
데이터 처리 전문가가 되고 싶은 "어피치"는 문자열을 압축하는 방법에 대해 공부를 하고 있습니다. 최근에 대량의 데이터 처리를 위한 간단한 비손실 압축 방법에 대해 공부를 하고 있는데, 문자열에서 같은 값이 연속해서 나타나는 것을 그 문자의 개수와 반복되는 값으로 표현
셀수있는 수량의 순서있는 열거 또는 어떤 순서를 따르는 요소들의 모음을 튜플(tuple)이라고 합니다. n개의 요소를 가진 튜플을 n-튜플(n-tuple)이라고 하며, 다음과 같이 표현할 수 있습니다.(a1, a2, a3, ..., an)튜플은 다음과 같은 성질을 가지
슈퍼 게임 개발자 오렐리는 큰 고민에 빠졌다. 그녀가 만든 프랜즈 오천성이 대성공을 거뒀지만, 요즘 신규 사용자의 수가 급감한 것이다. 원인은 신규 사용자와 기존 사용자 사이에 스테이지 차이가 너무 큰 것이 문제였다.이 문제를 어떻게 할까 고민 한 그녀는 동적으로 게임
카카오에 신입 개발자로 입사한 "콘"은 선배 개발자로부터 개발역량 강화를 위해 다른 개발자가 작성한 소스 코드를 분석하여 문제점을 발견하고 수정하라는 업무 과제를 받았습니다. 소스를 컴파일하여 로그를 보니 대부분 소스 코드 내 작성된 괄호가 개수는 맞지만 짝이 맞지 않
게임개발자인 "죠르디"는 크레인 인형뽑기 기계를 모바일 게임으로 만들려고 합니다."죠르디"는 게임의 재미를 높이기 위해 화면 구성과 규칙을 다음과 같이 게임 로직에 반영하려고 합니다.게임 화면은 "1 x 1" 크기의 칸들로 이루어진 "N x N" 크기의 정사각 격자이며
레스토랑을 운영하던 스카피는 코로나19로 인한 불경기를 극복하고자 메뉴를 새로 구성하려고 고민하고 있습니다.기존에는 단품으로만 제공하던 메뉴를 조합해서 코스요리 형태로 재구성해서 새로운 메뉴를 제공하기로 결정했습니다. 어떤 단품메뉴들을 조합해서 코스요리 메뉴로 구성하면
Leo는 카펫을 사러 갔다가 아래 그림과 같이 중앙에는 노란색으로 칠해져 있고 테두리 1줄은 갈색으로 칠해져 있는 격자 모양 카펫을 봤습니다.Leo가 본 카펫에서 갈색 격자의 수 brown, 노란색 격자의 수 yellow가 매개변수로 주어질 때 카펫의 가로, 세로 크기
두 개의 단어 begin, target과 단어의 집합 words가 있습니다. 아래와 같은 규칙을 이용하여 begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾으려고 합니다.예를 들어 begin이 "hit", target가 "cog", words가 "hot"
프로그래머스 - 뉴스 클러스터링 풀이
십진수를 이진수로 만드는 num.toString(2)를 이용해서 이진수로 만든 다음 지도 길이에 맞게 0을 추가해주는 코드를 짰었다.n(지도의 크기) = 5일 때, num = 1 이면 1.toString(2) = 1로 바껴서 지도 크기에 맞게 앞 부분에 0을 4개를 추
프렌즈대학교 컴퓨터공학과 조교인 제이지는 네오 학과장님의 지시로, 학생들의 인적사항을 정리하는 업무를 담당하게 되었다.그의 학부 시절 프로그래밍 경험을 되살려, 모든 인적사항을 데이터베이스에 넣기로 하였고, 이를 위해 정리를 하던 중에 후보키(Candidate Key)
1로 만들기
개발자를 희망하는 죠르디가 카카오에 면접을 보러 왔습니다.코로나 바이러스 감염 예방을 위해 응시자들은 거리를 둬서 대기를 해야하는데 개발 직군 면접인 만큼아래와 같은 규칙으로 대기실에 거리를 두고 앉도록 안내하고 있습니다.대기실은 5개이며, 각 대기실은 5x5 크기입니
문자 로그 -> 숫자 로그 순서로 정렬문자 로그들은 사전 순으로 정렬 \- 로그들이 모두 같을 경우 id로 판별 \- let3 art zero, let1 art zero can인 경우, 길이가 짧은 로그가 앞에 온다.숫자 로그는 입력 순서 유지
프로그래머스 - 가장 큰 수(자바스크립트, javascript)
다음 규칙을 지키는 문자열을 올바른 괄호 문자열이라고 정의합니다.(), \[], {} 는 모두 올바른 괄호 문자열입니다.만약 A가 올바른 괄호 문자열이라면, (A), A, {A} 도 올바른 괄호 문자열입니다. 예를 들어, \[] 가 올바른 괄호 문자열이므로, (\[])