IT

    [프로그래머스] 후보키
    알고리즘/문제풀이

    [프로그래머스] 후보키

    그냥 구현이 까다로웠던 문제이다... 이렇게 더럽게 풀어도 되나 싶었는데 그냥 더럽게 푸는게 맞았던 단순히 구현력을 물어보는 문제 같았다.1. 문제 설명테이블이 다음과 같이 있을때, 각각의 row를 유일하게 식별해줄 key를 고르는 문제이다.이때 key는 2가지 조건을 만족해야 하는데 그 조건은 다음과 같다.* 유일성(uniqueness) : 릴레이션에 있는 모든 튜플에 대해 유일하게 식별되어야 한다.* 최소성(minimality) : 유일성을 가진 키를 구성하는 속성(Attribute) 중 하나라도 제외하는 경우 유일성이 깨지는 것을 의미한다. 즉, 릴레이션의 모든 튜플을 유일하게 식별하는 데 꼭 필요한 속성들로만 구성되어야 한다.두 가지를 쉽게 직역하면 다음과 같다.* 유일성 -> 하나의 row를 유..

    [프로그래머스] 괄호 회전하기
    알고리즘/문제풀이

    [프로그래머스] 괄호 회전하기

    이전에 괄호변환과 너무 비슷한 유형이었다. 그래서 그때 사용했던 풀이법을 그대로 사용했는데, 테스트 케이스에서 틀려버렸다. 이전에 괄호 변환시 사용했던 풀이법이 정석은 아니었다. 스택을 사용하는게 정석이었다. 스택을 사용한 풀이법이 약한 경우가 있어서, 스택을 활용한 문제를 다시 풀어봐야할 필요성을 느꼈다. 그리고, 항상 느끼지만 대부분의 문제가 카카오 문제를 활용한 것이 매우 느껴진다. 카카오 문제를 공들여서 풀어놔야겠다. 복습해야 할 유형과 문제들을 정리해놔야지 ... 1. 문제 설명 [](){} 이러한 형태의 문자열이 주어진다. 그리고 문자열을 왼쪽으로 x만큼 회전시킨다. 0번만큼 회전시키면 그대로, 1번만큼 회전시키면 ](){}[ 이 된다. 이런식으로 문자열의 길이-1 까지 계속 회전시킨다. 각각..

    [개념정리] Python 가변객체, 불변객체, 얕은 복사, 깊은 복사
    알고리즘/개념

    [개념정리] Python 가변객체, 불변객체, 얕은 복사, 깊은 복사

    뉴스 클러스터링 문제를 풀다가 어떻게 여기까지 왔는지 모르겠지만... 아무튼 개념을 명확하게 짚고 넘어가야겠다. 일반 파이썬 교재에는 이 개념이 제대로 설명되어있지 않았다. 그래서 전문가를 위한 파이썬 교재를 펼쳤다. 1. 변수는 상자가 아니다. 파이썬의 변수는 모두 객체로 이뤄져 있는데, 이때 이 객체의 개념은 자바에서의 참조 변수와 같다. (보통 객체와 생성된 참조변수의 관계를 붕어빵 틀과 붕어빵으로 설명하는 경우가 있는데, 잘못된 설명인 것 같다.) 그래서 파이썬에서 변수는 다음과 같은 그림으로 표현할 수 있다. 어떤 객체라는 물체에 변수를 붙여서 같은 객체를 가리키게 하는 것이다. 변수는 객체에 붙은 레이블이라고 표현할 수 있다. 실제로, 이 개념을 프로그래밍을 할때 '변수1'이 객체에 할당되었다..

    [개념 정리] Python None 리턴하는 경우 / 재귀함수 None 리턴
    알고리즘/개념

    [개념 정리] Python None 리턴하는 경우 / 재귀함수 None 리턴

    예상 대진표 문제를 풀이하다가 만나게 된 문제, 정확히 알지 못해서 기본적인 개념이지만 정확하게 정리해두려고 한다. 1. 내가 헷갈린점 1) 파이썬 return 안해도 돼! -> 알아서 return 해주는 것 파이썬에서 함수가 return문이 없어도 되고, 없으면 리턴 없이 끝나는 줄 알았다. 알고보니 아니었음 .. 암튼 return문이 없으면 자동으로 return None을 하게 된다. 2) 재귀함수에서 재귀가 종료되는 경우 def dfs(): if 재귀 종료 조건: return cnt dfs() 이러한 함수가 있다고 하면, 나는 이런 트리 동작을 생각했다. 근데 이게 아니라 이거였다. 재귀가 종료되면, 해당 재귀에서 cnt를 리턴하고 해당 함수는 종료된다. 그리고, 해결되지 않은 나머지 함수에서는 자..

    [개념정리] 다익스트라 알고리즘
    알고리즘/개념

    [개념정리] 다익스트라 알고리즘

    최단 경로 문제 중, 하나의 정점에서 다른 모든 정점까지 가는 데에 걸리는 최단 비용을 구하는 알고리즘이다. 다익스트라 알고리즘은 욕심쟁이 알고리즘과 비슷하다. 현재의 정점에서 갈 수 있는 모든 정점을 확인하고, 그중에서 가장 비용이 적은 정점을 선택해 최선의 선택을 하게 된다. 동작 방식은 BFS와 비슷하다. 현재의 정점에서 갈 수 있는 모든 정점을 힙에 넣고, 그중에서 가장 비용이 적은 노드를 선택해 가장 짧은 경로를 업데이트 해나가는 것이다. 다익스트라 알고리즘을 구현하는 자료구조는 우선순위 큐를 사용해도 되지만, 파이썬에서는 대부분 최소힙을 사용한다. (가장 상위노드에 가장 적은 값이 오는 구조) 1. 예시 다음과 같은 그래프가 있을때, A에서 각 정점으로 도달하는 최소비용을 가진 경로를 구하라는..

    [프로그래머스] 다리를 지나는 트럭
    알고리즘/문제풀이

    [프로그래머스] 다리를 지나는 트럭

    문제가 정말 난해했다. 무슨소리를 하는지도 모르겠고, 전체적으로 조건도 명확하지 않았다;;; 어떻게 풀라는 것인지 ;;;;; 1. 문제 설명 최초에 다리의 길이와, 다리가 견딜 수 있는 하중의 무게, 그리고 지나가려는 트럭의 무게가 인자로 주어진다. 나는 일단 여기서 경과 시간이 1~2, 6~7인것이 이해가 안갔다. 지나갈때 몇초가 걸리는지에 대해 주어지지도 않았고, 스택을 활용한 좋은 문제인것은 맞지만 문제 출제진이 검토를 부실하게 한 것 같다. --; 이 문제를 그림으로 보면 조금 더 잘 와닿아서 그림으로 보겠다. 다리를 지나고 있는 자동차는 7kg 이기 때문에 그냥 지나가고 있다. 이때 1초가 추가된다. 순서대로 다음 자동차가 들어오려 한다. 여기서 헷갈림이시작된다. 자동차가 지나가는 행위 자체를 ..

    [프로그래머스] 행렬 테두리 회전하기
    알고리즘/문제풀이

    [프로그래머스] 행렬 테두리 회전하기

    문제가 그렇게 어려웠던 문제는 아니었다. 근데, 정말 오래걸렸다. 단순 구현문제라고 해서 답지를 보면 안된다길래 안보고 풀었지만.. 시간도 오래걸리고 ㅠㅠ 또르르... 일단 dx, dy를 코딩테스트로 풀때 우리가 생각하는 2차원 평면상의 x, y좌표랑 너무 헷갈렸다. 실제 문제풀때 이런게 헷갈리면 안돼서 이부분을 좀 제대로 머리에 인식해둬야겠다는 생각이 들었다. 그리고, 인덱스가 헷갈리는 문제는 꼭 종이에 풀이하면서, 변수명을 정확히 적으면서 해야한다. 1. 문제 설명 row와 columns가 주어지고, 주어진 만큼 1부터 시작해서 행렬을 채워 넣는다. 이후 문제에서 2,2 와 5,4 사이의 원소를 회전시키라고 한다. 회전시키면 이러한 형태가 된다. 이렇게 회전시킬 좌표를 n개가 문제에서 주어진다. 그리..

    [프로그래머스] 예상 대진표
    알고리즘/문제풀이

    [프로그래머스] 예상 대진표

    일단 재귀함수의 개념도 다시 짚고 가야했다. 1. 문제 설명 문제 상황은 토너먼트 상황이다. n은 참가하는 참가자 수이고, a와 b의 값은 각각 a와 b가 참가하는 순서이다. 여기서 문제는 a와 b가 무조건 각 토너먼트에서 승리하고 올라간다면, 언제 2명이 경쟁하는 순간이 오느냐이다. 그림으로 보면 다음과 같다. 노란색 네모가 최초의 4번째 참가자인 a이고, 연두색 네모가 최초의 7번째 참가자인 b이다. a와 b가 대결을 하게 되는 순간은 3번째 경기 과정이고 문제에서는 이 3번째를 구하는 함수를 요구한다. 2. 어려웠던 점 1) 재귀함수 return 처음에 코드를 이렇게 작성했는데, None을 리턴하게 되었다. def dfs(n, a, b, cnt): if abs(a - b) == 1: return c..

티스토리툴바