tech.log tech.log

최단 경로 알고리즘 - 가장 짧은 경로를 찾는 알고리즘이다. '길 찾기' 문제라고도 불린다. - 대표적으로는1. '한 지점에서 다른 특정 지점까지 최단 경로를 구해야 하는' 다익스트라 알고리즘2. '모든 지점에서 다른 모든 지점까지 최단 경로를 모두 구해야 하는' 플로이드 워셜 알고리즘이 있다. - 보통 '그래프' 를 이용해 표현된다.1. 각 지점은 '노드'로 , 연결된 도로는 '간선'으로 표현된다 다익스트라 알고리즘- 특정 노드에서 다른 특정 노드로 가는 각각의 최단 경로를 구해주는 알고리즘- 음의 간선(0보다 작은 값을 가지는 간선) 이 없을 때 사용- 현실 세계의 gps 알고리즘으로 채택된다 -> 현실세계에서는 음의 간선이 없으므로 가능- 매 단계 가장 비용이 적은 노드를 선택해서 과정을 반복하므로..

접근 방식 1. 완전 탐색 문제를 읽고 가장 먼저 생각나는 것은 완전 탐색일 것이다. 리스트의 원소 1개를 기준으로 전체를 탐색하며 접두어가 되는지 확인하는 것이다. 이 방식을 사용한다면 1) 리스트 원소 마다 2) 전체를 탐색하며 접두어가 되는지 확인 하는 과정이 필요하고 2중 Loop 으로 구현이 가능하다. 하지만, 문제의 제약조건 [phone_book의 길이는 1 이상 1,000,000 이하입니다.] 을 확인하면 이 방식은 1,000,000 x 1,000,000 의 시간이 걸리는... 관계로 제외하였다. 2. sort/Loop 2중 Loop를 1중 Loop으로 변환 할 방법을 고안하다 생각해낸 것이 정렬이다. 문제를 잘 살펴보면 결국 접두어가 된 다는 것은 앞 숫자가 뒷 숫자의 가장 큰 자리 부터 ..

시도_1 def solution(participant, completion): answer = '' # 주의: 참가자 중에는 동명이인이 있을 수 있습니다. for p in completion: if p in participant: participant[participant.index(p)] = '0' for z in participant: if z != '0': answer = z break return answer 시도2 #풀이2_dic 이용 # get(i,x) => i 없으면 x return def solution(participant, completion): answer = '' d = {} # 참가자들을 삽입 for p in participant: if p not in d.keys(): d.upd..

문제 나만의 카카오 성격 유형 검사지를 만들려고 합니다. 성격 유형 검사는 다음과 같은 4개 지표로 성격 유형을 구분합니다. 성격은 각 지표에서 두 유형 중 하나로 결정됩니다. 지표 번호성격 유형 1번 지표 라이언형(R), 튜브형(T) 2번 지표 콘형(C), 프로도형(F) 3번 지표 제이지형(J), 무지형(M) 4번 지표 어피치형(A), 네오형(N) 4개의 지표가 있으므로 성격 유형은 총 16(=2 x 2 x 2 x 2)가지가 나올 수 있습니다. 예를 들어, "RFMN"이나 "TCMA"와 같은 성격 유형이 있습니다. 검사지에는 총 n개의 질문이 있고, 각 질문에는 아래와 같은 7개의 선택지가 있습니다. 매우 비동의 비동의 약간 비동의 모르겠음 약간 동의 동의 매우 동의 각 질문은 1가지 지표로 성격 유형..

문제 ANIMAL_INS 테이블은 동물 보호소에 들어온 동물의 정보를 담은 테이블입니다. ANIMAL_INS 테이블 구조는 다음과 같으며, ANIMAL_ID, ANIMAL_TYPE, DATETIME, INTAKE_CONDITION, NAME, SEX_UPON_INTAKE는 각각 동물의 아이디, 생물 종, 보호 시작일, 보호 시작 시 상태, 이름, 성별 및 중성화 여부를 나타냅니다. NAME TYPE NULLABLE ANIMAL_ID VARCHAR(N) FALSE ANIMAL_TYPE VARCHAR(N) FALSE DATETIME DATETIME FALSE INTAKE_CONDITION VARCHAR(N) FALSE NAME VARCHAR(N) TRUE SEX_UPON_INTAKE VARCHAR(N) FA..

문제 ROR 게임은 두 팀으로 나누어서 진행하며, 상대 팀 진영을 먼저 파괴하면 이기는 게임입니다. 따라서, 각 팀은 상대 팀 진영에 최대한 빨리 도착하는 것이 유리합니다. 지금부터 당신은 한 팀의 팀원이 되어 게임을 진행하려고 합니다. 다음은 5 x 5 크기의 맵에, 당신의 캐릭터가 (행: 1, 열: 1) 위치에 있고, 상대 팀 진영은 (행: 5, 열: 5) 위치에 있는 경우의 예시입니다. 위 그림에서 검은색 부분은 벽으로 막혀있어 갈 수 없는 길이며, 흰색 부분은 갈 수 있는 길입니다. 캐릭터가 움직일 때는 동, 서, 남, 북 방향으로 한 칸씩 이동하며, 게임 맵을 벗어난 길은 갈 수 없습니다. 아래 예시는 캐릭터가 상대 팀 진영으로 가는 두 가지 방법을 나타내고 있습니다. 첫 번째 방법은 11개의 ..

문제 ANIMAL_INS 테이블은 동물 보호소에 들어온 동물의 정보를 담은 테이블입니다. ANIMAL_INS 테이블 구조는 다음과 같으며, ANIMAL_ID, ANIMAL_TYPE, DATETIME, INTAKE_CONDITION, NAME, SEX_UPON_INTAKE는 각각 동물의 아이디, 생물 종, 보호 시작일, 보호 시작 시 상태, 이름, 성별 및 중성화 여부를 나타냅니다. NAME TYPE NULLABLE ANIMAL_ID VARCHAR(N) FALSE ANIMAL_TYPE VARCHAR(N) FALSE DATETIME DATETIME FALSE INTAKE_CONDITION VARCHAR(N) FALSE NAME VARCHAR(N) TRUE SEX_UPON_INTAKE VARCHAR(N) FA..

문제 설명 H-Index는 과학자의 생산성과 영향력을 나타내는 지표입니다. 어느 과학자의 H-Index를 나타내는 값인 h를 구하려고 합니다. 위키백과1에 따르면, H-Index는 다음과 같이 구합니다. 어떤 과학자가 발표한 논문 n편 중, h번 이상 인용된 논문이 h편 이상이고 나머지 논문이 h번 이하 인용되었다면 h의 최댓값이 이 과학자의 H-Index입니다. 어떤 과학자가 발표한 논문의 인용 횟수를 담은 배열 citations가 매개변수로 주어질 때, 이 과학자의 H-Index를 return 하도록 solution 함수를 작성해주세요. 제한사항 과학자가 발표한 논문의 수는 1편 이상 1,000편 이하입니다. 논문별 인용 횟수는 0회 이상 10,000회 이하입니다. 입출력 예 citations ret..