본문 바로가기

알고리즘/프로그래머스

Lv2 문제(간단한거) 1. N개의 최소 공배수 구하기 - a,b의 최소공배수 : a * b // gcd(a,b) 2. [1260] dfs와 bfs (실버2) - bfs는 "함수 시작하자마자, start노드 큐에 넣기 전에3 + 탐색 후 다음 노드 큐에 넣을 때 visited[i] = True로 바꾸기. 큐에서 뽑을 때 true로 바꾸면 중복접근됨 - 두 함수의 결과를 각각 한 줄 단위로 출력하고 싶으면 함수 내에선 print( ~,end = " "), 하고 함수 사이에 print("")넣기 - 맨 처음에 d_visited = b_visited = [False] * (N+1)로 했더니 둘이 같은 메모리 공간을 공유함! 즉 이름만 다르고 같은 배열처럼 됨!! 다른 문제 풀 때도 조심할 것 !!!1 - 헷갈리는 것 : 변수는 a=.. 더보기
(kakao) 메뉴 리뉴얼(python) 1. 문제 https://programmers.co.kr/learn/courses/30/lessons/72411 코딩테스트 연습 - 메뉴 리뉴얼 레스토랑을 운영하던 스카피는 코로나19로 인한 불경기를 극복하고자 메뉴를 새로 구성하려고 고민하고 있습니다. 기존에는 단품으로만 제공하던 메뉴를 조합해서 코스요리 형태로 재구성해서 programmers.co.kr 2. 구현 과정 1) 메뉴 개수를 나타내는 course값이 10 이하이고, 각 단품 메뉴를 나타내는 알파벳이 26개이다. 코스 요리의 메뉴 개수가 2개라 하면, 가능한 경우의 수는 26C2이고, 3개라 하면 가능한 경우의 수는 26C3이다. => 26C1, 26C2, 26C3, 26C4,.... 26C10 2) 26C1 + 26C2 + 26C3 + .... 더보기
[Lv2] 뉴스 클러스터링(python) 1. 문제 https://programmers.co.kr/learn/courses/30/lessons/17677?language=python3 코딩테스트 연습 - [1차] 뉴스 클러스터링 뉴스 클러스터링 여러 언론사에서 쏟아지는 뉴스, 특히 속보성 뉴스를 보면 비슷비슷한 제목의 기사가 많아 정작 필요한 기사를 찾기가 어렵다. Daum 뉴스의 개발 업무를 맡게 된 신입사원 튜브 programmers.co.kr 2. 풀이 과정 - 다른 분들의 풀이를 참고하여 푼 문제. 다중 집합의 개념을 알게 되었다! - 기존 집합 관련 문제는 set을 쓰기만 하면 되었었는데, 이번 문제는 set 자료구조의 기본 함수만을 사용할 수 없었기 때문에 버벅거렸다. set의 기본 구현 방식도 익혀야 할 것 같다! 3. 실수 한 것.. 더보기
[Lv2] 캐시(python) 1. 문제 https://programmers.co.kr/learn/courses/30/lessons/17680 도시들 간 순서가 있어야 함 & 자료구조의 사이즈를 알아야 함 - 초기 접근 방식 딕셔너리를 사용해서 key - 도시 이름, value - 해당 도시가 들어왔던 직전 순서를 저장. i번째 도시를 찾으려고 할 때, 이미 이전에 값이 들어온 적이 있으면 해당 value 값을 보고 value >= i - cacheSize + 1이면 cache hit으로 봤음 - 초기 접근 방식의 반례 cacheSize = 3, A B B B A 라 하면 , 마지막 A를 찾을 때 cache[A] = 0이 되어서 원래는 cache hit임에도 cache miss로 판정됨 => " 절대적인 순서가 필요한 게 아니라 캐시.. 더보기
[Lv2] 짝지어 제거하기(python) 1. 문제 https://programmers.co.kr/learn/courses/30/lessons/12973?language=python3 코딩테스트 연습 - 짝지어 제거하기 짝지어 제거하기는, 알파벳 소문자로 이루어진 문자열을 가지고 시작합니다. 먼저 문자열에서 같은 알파벳이 2개 붙어 있는 짝을 찾습니다. 그다음, 그 둘을 제거한 뒤, 앞뒤로 문자열을 이어 붙 programmers.co.kr 2. 풀이 과정 - stack을 사용해서 stack의 top 문자와 s[i]가 같으면 stack.pop()하고 아니면 stack.append()를 해가다가 최종 stack이 빈 stack이면 1을 리턴. - "붙어있어야 한다 + 붙어있는게 사라졌을 때, 새로운 짝이 생긴다 (b aa b -> bb) " -> .. 더보기
[Lv2] 튜플(python) 1. 문제 https://programmers.co.kr/learn/courses/30/lessons/64065 코딩테스트 연습 - 튜플 "{{2},{2,1},{2,1,3},{2,1,3,4}}" [2, 1, 3, 4] "{{1,2,3},{2,1},{1,2,4,3},{2}}" [2, 1, 3, 4] "{{4,2,3},{3},{2,3,4,1},{2,3}}" [3, 2, 4, 1] programmers.co.kr 2. 구현 과정 1) 문제 내 정의 정리 * 튜플 - 어떤 순서를 따르는 요소들의 모임 - 중복 원소 가능 - 요소끼리의 순서 존재 - 원소 개수는 유한 * {}로 표현할 수 있는 집합 - 중복 원소가 없는 튜플의 원소들을 이용하여 {a1}, {a1,a2}, {a1,a2,a3..} 등으로 표현하는 집.. 더보기
[Lv2] 거리두기 확인하기(python) 1. 문제 https://programmers.co.kr/learn/courses/30/lessons/81302 코딩테스트 연습 - 거리두기 확인하기 [["POOOP", "OXXOX", "OPXPX", "OOXOX", "POXXP"], ["POOPX", "OXPXP", "PXXXO", "OXXXO", "OOOPP"], ["PXOPX", "OXOXP", "OXPOX", "OXXOP", "PXPOX"], ["OOOXX", "XOOOX", "OOOXX", "OXOOX", "OOOOO"], ["PXPXP", "XPXPX", "PXPXP", "XPXPX", "PXPXP"]] [1, 0, 1, 1, 1] programmers.co.kr 2. 접근 방법 1) 모든 인원끼리의 맨해튼 거리가 2 이하인지 확인 => 각 .. 더보기
[Lv2]괄호 변환(python) 1. 문제 2. 구현 과정 - 정말.... 이 문제만 보면 그렇게 졸음이 와서(?) 문제 이해하는데 오래 걸렸다.. 문제 이해하는 데 대부분의 시간을 소요한 것 같다. - 구현 방법은 이미 문제에서 다 정의해줬고, 특별한 알고리즘을 사용하는게 아니라 재귀 함수를 만드는 거라 특정 알고리즘에 대해 고민할 필요는 없었다. 문제를 제대로 이해하는 게 핵심인 것 같다. - 구현의 흐름은 문제에서 정의했지만 중요한 건 "왜?" 저렇게 구현해야 하는지 인데, 큰 흐름은 다음과 같다. 1) 문자열을 균형잡힌 문자열( U ) 와 나머지 문자열 ( V ) 로 나눔 2) U가 올바른 문자열이 아니라면, 'U'의 시작 문자는 ')', 마지막 문자는 '('일 것이다! 균형 잡힌 문자열이면서 올바른 문자열이 아니다 = '('와.. 더보기

티스토리툴바