알고리즘20 [알고리즘] 위상 정렬(Topological Sort) - 개발하는 지토 위상 정렬(Topological Sort) 위상 정렬은 순서가 정해져 있는 작업을 차례로 수행해야 할 때 그 순서를 결정해주기 위해 사용하는 알고리즘이다. 즉, 방향 그래프에 존재하는 각 정점들의 선행 순서를 위배하지 않으면서 모든 정점을 나열하는 것 이다. 위상 정렬을 가장 잘 설명할 수 있는 예시는 대학의 선수과목 구조 또는 게임에서의 스킬트리 중 선행스킬이 존재하는 경우이다. 앞선 대표 예 두가지 중 각자 더 이해가 쉬운 예시를 떠올려 보면 쉽게 이해할 수 있을 것이다. 위상 정렬이 성립하기 위해서는 반드시 그래프에 순환이 존재하지 않아야 한다. 즉, 비순환 방향 그래프(Directed Acyclic Graph, DAG) 여야 한다. 그리고 하나의 방향 그래프에 대해서 위상 정렬을 수행한 결과 값이.. 2021. 3. 18. [공부] 온라인 알고리즘 문제풀이 스터디 후기2 - 구글미트 (프로그래머스, 백준온라인저지) 오늘도 어제 같이 진행했던 분과 함께 알고리즘 문제풀이 스터디를 진행했다. 많은 문제를 풀어보진 못했다. 오늘 푼 문제는 1. 프로그래머스 - 3진법 뒤집기 : programmers.co.kr/learn/courses/30/lessons/68935?language=java 코딩테스트 연습 - 3진법 뒤집기 자연수 n이 매개변수로 주어집니다. n을 3진법 상에서 앞뒤로 뒤집은 후, 이를 다시 10진법으로 표현한 수를 return 하도록 solution 함수를 완성해주세요. 제한사항 n은 1 이상 100,000,000 이하인 자연수 programmers.co.kr 문제를 먼저 풀고, 슬라이딩 윈도우 알고리즘에 대한 강의를 각자 들었다. 해당 알고리즘 기법을 활용할 수 있는 문제! 2. 백준 - 수들의 합 2.. 2020. 10. 30. [알고리즘] 백준 2003번: 수들의 합 2 (자바/Java) - 슬라이딩 윈도우, 구간합 스터디 중에 풀었던 알고리즘 문제 백준 2003번: 수들의 합 2 문제를 가져와봤다. 사실 이 문제는 투 포인터 기법을 활용해서 문제를 푸는 것 같았다. 하지만 오늘 스터디에서 투 포인터를 들어가기 전에 슬라이딩 윈도 기법을 먼저 진행했기 때문에 이번 문제는 슬라이딩 윈도 기법으로 풀어보았다. 문제는 다음과 같다. 수들의 합 2 성공분류 시간제한 메모리 제한 제출 정답 맞은 사람 정답 비율 0.5 초 128 MB 17563 8645 5801 50.752% 문제 N개의 수로 된 수열 A [1], A [2], …, A[N] 이 있다. 이 수열의 i번째 수부터 j번째 수까지의 합 A[i] + A[i+1] + … + A[j-1] + A[j]가 M이 되는 경우의 수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에.. 2020. 10. 29. [공부] 온라인 알고리즘 문제풀이 스터디 후기 - 구글미트 (프로그래머스, 백준온라인저지) 오늘은 간단하게만 후기를 남겨보려 한다. 다음 스터디를 진행하면서는 좀 더 좋은 내용으로 글을 써볼 예정이다. 얼마 전에 내 블로그에 있던 문제풀이 글을 보시고 댓글을 남겨주신 분과 연락이 닿게 되었다. 같이 알고리즘 스터디를 하자는 제안이 있으셔서 나도 공부를 하고 있고, 더 열심히 해야 하는 입장이었기 때문에 흔쾌히 같이 하겠다고 했다. 그리고 오늘 오후 9~12시, 총 3시간 동안 스터디를 진행했다. 사실 아직 어떠한 방향으로 스터디를 하겠다고 명확히 정하질 못해서 체계적인 스터디는 아니지만, 차츰 발전하는 스터디가 되었으면 좋겠다. 오늘 같이 풀어본 문제는 1. programmers.co.kr/learn/courses/30/lessons/67256?language=java 코딩테스트 연습 - 키패.. 2020. 10. 29. [코딩테스트] 프로그래머스 2020 Dev-Matching: 웹 백엔드 개발자(하반기) 후기 - 개발하는 지토 이번 후기도 코딩 테스트 후기다. 일단 해당 시험도 사실 저번 주 토요일에 치렀었는데 조금 늦은 후기를 끄적여본다. 사실 지금 코딩테스트를 준비한 지 두 달 정도 된 것 같고.. 물론 일을 병행하느라 많은 시간을 투자하진 못했다. 어찌 됐든 지금까지 진행했던 몇 개의 코딩 테스트에서 좋은 결과를 얻지는 못했던 것 같았다. 아직 내 노력도 부족하고 공부량도 많지 않았기에 아쉽지만 좋은 경험을 쌓았다고 생각한다. 그리고 이번에 프로그래머스에서 진행한 '2020 Dev-Matching: 웹 백엔드 개발자(하반기)' 에 지원을 하고 시험을 봤다. 알고리즘 3문제, SQL 한문제가 출제가 되었고, 그래도 프로그래머스에 있는 SQL을 조금 끄적여보니 알고리즘보단 훨씬 쉬운 난이도로 문제들이 이루어져 있어서 SQL을.. 2020. 10. 14. [코딩테스트] 프로그래머스 월간 코드 챌린지 시즌1 - 2회차 후기 - 개발하는 지토 거의 일주일이 지난 후기를 간단하게 써본다. 저번 달부터 시작한 프로그래머스 월간 코드 챌린지 시즌1은 매달마다 한 번씩 코딩 테스트를 진행하고, 총 4문제가 출제되는 대회? 시험?이다. 저번 달에도 참여를 했었는데 후기는 안 적었더라.. ㅎㅎ 먼저 저번 코드 챌린지 때는 아마 4문제 중에 2문제를 풀고 3번 문제의 테스트 케이스를 몇 개 정도? 통과하여 상위 11프로의 성적이 나왔었던 걸로 기억을 한다. 신기하게도 이 코드 챌린지는 시험을 보는 중에도 계속 나의 등수를 확인할 수 있고, 몇 번 문제를 몇 명이 풀었는지도 확인할 수 있도록 시스템이 되어있어서 더욱더 경쟁심리를 자극하는 듯했다. 그리고 이번 시험에서도 4개의 문제가 나왔는데 나는 이번에도 2문제 + a 만큼 풀 수 있었다.. 왠지 한 달이.. 2020. 10. 14. 이전 1 2 3 4 다음
