코딩테스트(python)

sort파이썬에서는 sort로 정렬 할 수 있는데 key값을 통해 여러 기준도 서설정 가능 하다.people = {"name": "Alice", "age": 30}, {"name": "Bob", "age": 25}, {"name": "Charlie",

이 문제는 최단거리 이므로 bfs를 통해 구현해주면 된다.bfs를 잘 모르는 지라 구글링을 하며 다른 사람의 답안을 참고 하며 작성해보았는데 처음에는 런타임 에러가 발생했다그 이유는 보통은 x,y 좌표 순서가 (x,y) 이다 보니 다른 사람의 풀이에서 이 부분을 x y

해시 관련 문제이다 보니 딕셔너리로 구현했다def solution(nums):nums 를 딕셔너리로 변환하면 중복이 제거 되어 딕셔너리의 length가 전체 포켓몬 종류의 수가 된다. 따라서 전체 종류의 수가 n/2 보다 크면 n/2 를 출력하고 (종류가 아무리 많더라

초반에 해시를 이용해 구현하는 방법이 감이 안잡혀 일단 리스트를 이용해 구현했다.물론 당연히 런타임에러가 발생함 ...딕셔너리를 이용하여 아래와 같이 수정함 이때 str_num in dic 처럼 해당 문자열이 딕셔너리에 존재하는지 딕셔너리를 통해 조회해서 이전과는 달

먼저 의상의 종류를 딕셔너리의 키에 넣고 의상을 값에 넣어 주었다이때 위의 코드처럼 키값을 이미 넣어준 의상 종류에 해당되는 의상을 넣을 때와 아닐 때를 다르게 처리해주어야한다.그렇지 않으면 value가 추가되는 것이 아니라 대체되어 모든 의상종류가 한 개의 value

이 문제에서 그룹 단어가 아닌 경우는 각 단어를 한 문자씩 확인해볼 때 이전에 등장 했으면서 왼쪽의 문자와 동일한 문자가 아닌 경우일 때 라고 생각했다.그래서 이런식으로 구현해주었다. 처음에 ans=1 하는 부분을 그룹단어 여부 체크에 넣어 주었더니 ans가 마이너스

먼저 처음에 틀렸던 부분은 윤년을 문제 내용에 없길래 고려안했는데 해줘야했다...ㅎㅎ 이정도는 알아서 해줘야 하나보다....아무튼 윤년이면 각 월별 날짜 수를 넣어준 리스트에서 2월달에 해당되는 날짜를 +1 해준다.그리고 해당 문제에서 입력 예시가 분 단위까지 주므로

처음에는 max(n_list) 를 이용해 해당 값의 인덱스가 다솜이의 인덱스가 될 때까지 while문을 반복하는 형식으로 하려 했다.그런데 4 10 10 10 10 이런 형식으로 다른 후보자와 투표수가 같을때에는 max() 를 하게되면 앞에오는 인덱스값이 max_ind

문제 해결을 위해 접근한 방식은 일단 cnt라는 변수를 설정해 n개의 종말의 수를 구할 때까지 while문을 반복하고 해당 숫자가 종말의 수 여부를 판독하기 위해 해당 숫자를 666이상일 동안 10으로 나누고1000으로 나눈 나머지가 666이 되면 종말의 숫자이므로 c

처음에는이 부분을 이런식으로 구현을 해주었더니1010101010과 같은 예시에서 에러가 발생했다그 이유는 마지막 숫자가 포함된 부분은 카운트가 되지 않았기 때문이다.그런데 사실 이 부분은 while 에서 i 가 len(s)보다 작을때에만 돌도록 구현을 해주어도 되었다.

이 문제는 가장 빠른 시간에 대해 물어보고 있지만 사실상 최단경로를 구하는 문제이다.걸리는 시간은 거리로 생각하고 기존의 최단경로 문제와 유사하게 풀이하면된다.그렇기 때문에 bfs 알고리즘 방식으로 문제를 해결해주었다.보통 미로 문제에서는 dx=-1,1,0,0 dy =

처음 이 문제를 마주했을 때에는 어떤식으로 풀어야 할지 감이 전혀 잡히지 않았었다. 아무래도 벌집모양의 구조를 고려하여 구현을 해야하니 벌집 모양을 리스트로 구현할 수도 없는 노릇이라 막막했다그래서 벌집 구조라는 것에 대한 집착은 버리고 숫자의 규칙에 집중하기로 했다.

일단 상하좌우를 탐색해야하는 좌표라는 점에서 미로 예제가 생각났다다만 미로 예제와는 달리 길이 막혀 갈 수 있는 길이 하나인게 아니라 사방이 둘러싸여 있는 영역이 몇개인지 세는것이였다.구체적인 로직을 짜기 전에 일단 큰 틀 먼저 잡았다. 먼저 생각한 순서는1\. 일단

문제를 보고 한번에 풀지 못해서 구글링 후 참고하여 풀었다.일단 dp로 해결해야하는 문제 였다. 그렇기 때문에 점화식을 세워본다면dp 1 = dp1dp2 = dp1 + p1 or dp0 + p2dp3 = dp2 + p1 or dp0+ p3dp4 = dp3 + p 1 o

먼저 이 문제를 처음 접했을 때 이동범위만 문제라고 생각되었다.왜냐하면 주어진 이동범위로 움직이고 원하는 목표지점까지의 최단거리를 구하는 문제이기 때문이다.이때 이동범위가 다른 부분을 어떻게 다르게 적용해야할 지 고민이 됐다.그래서 이동 할 수 있는 범위를 배열의 인

처음에는 범위를 제대로 안보고 이중 for문을 통해 구현 하였더니 당연히 시간초과가 발생했다.어떻게 해야할지 방법을 찾다가 dp를 통해 문제를 해결하면 되겠다고 막연히 생각은 했으나 단순이 dpx2-dpx1 을 해보다가 좀 더 식을 상세하게 세워야지 문제를 해결 할 수

이 문제는 정말 기본적인 미로탐색 문제다.n,m 까지 가는데 걸린 이동횟수를 구하는 문제이기때문에 따로 그래프를 만들지 않고 기존에 있는 그래프에 이동할때마다 값을 더해주어 n,m 의 좌표값을 출력해주도록 작성해주었다.코드상의 graph에서는 모든 좌표값이 -1되어있는

일단 문제를 해결하기위해 생각한 방법으로는 일반적인 미로찾기 방법을 살짝 변형해서 집이 있는 곳이라면 dfs 함수를 호출하고 해당 단지를 다 돌때까지 while문을 돌도록 코드를 작성해주었다.이런 방식으로 코드를 작성해서 예시 답완과 같은 출력이 나오는데까지에는 성공했

처음 이 문제를 접했을때는 바로 생각나는 알고리즘 기법이 없어서 난감했다.그런데 천천히 생각해보면 단순하게 자신과 인접하지 않은 두개중에서 최소값을 계속 더해주기만하면 가격의 최솟값을 구할 수 있다.그래서 이런식으로 각 배열에 그 전의 값들중 최솟값을 더해주면서 반복문

처음에 이 문제를 접했을 때에는 단순히 이전 행에서 고를 수 있는 값 중 최대를 고르면 될 줄 알았다그러나 문제 예시를 보면 알 수 있듯이 그 전 행의 값만 중요한게 아니라 전체적으로 최대합이 나올 수 있도록 하는게 중요한 문제이다.그렇기때문에 더더욱 dp 를 사용해서

처음 이 문제를 접했을때 스택 또는 큐로 풀어야겠다는 생각은 들었으나 어떻게 활용해서 해결해야할지는 쉽게 감이 잡히지는 않았다.앞에서부터 for 문으로 돌려서 하는 방법을 처음에 생각했는데 각 케이스별로 처리를 해주는 것이 쉽지 않다고 생각이 들었다.그래서 뒤에서부터

최솟값만들기는 길이가 같은 두배열의 모든 원소를 곱해서 나올 수있는 최솟값을 구하는 문제이다.최솟값이라는 말때문에 모든 경우의 수를 구해야하나하고 잠깐 생각하느라 아찔해졌지만 결국에는 두 배열을 곱해서 가장 작은 수가 되게 한다는 것은(A배열의 작은수 x B배열의 큰수

문제를 처음 보고 든 생각은 백준의 안전영역구하기 문제와 굉장히 유사하다는 느낌을 받았다.특정영역에 대해서 처리를 해주고 그 크기를 주해주는 점에서 bfs 알고리즘을 사용해서 처리해주면 될 것같다고 판단하였다.그런데 이 문제의 가장 어려운 점이라고 하면 평상시 풀던 좌

처음에 이 문제를 접했을 때에는 적어도 하나가 다른지원자보다 떨어지지 않는 자만 선발한다는 말에 꽂혀서 여집합을 이용해서 문제풀이를 해주려고 했다.이게 처음에 풀이한 내 코드이다. 하지만 시간초과가 발생한다.왜냐하면 문제를 보면 n의 범위가 1 ≤ N ≤ 100,000

처음에 이 문제를 접하고 C언어로 알고리즘을 풀 때처럼 아스키코드를 이용해서 대소문자 확인 및 변환을 해주려고 했는데 파이썬에는 islower,isupper,upper,lower과 같은 내장함수가 있다는 것을 알게 되었다.알고리즘이 어렵다기보단 파이썬의 어떤 내장함수를

처음 이 문제를 보고 든 생각은 숫자를 2진수로 변환하여 1의 갯수를 구해주는 부분을 따로 함수를 작성하여서 return 값을 통해 비교해주는 형식으로 코드를 작성해주어야 가독성이 좋을 것 같다고 생각했다.런타임에러를 고려하며 코드를 작성해주어야 할 만큼 복잡한 방식의

문제를 읽어보면 n이 100000 이하인 자연수이기때문에 이중 for문만 쓰지 않는다면 런타임에러 없이 충분히 문제를 해결해줄 수 있음을 알 수 있다.그래서 문제에 나온 피보나치 공식대로 식을 세워주기만 하면 정답이 된다.아주 간단한 문제였다.

이 문제를 처음 보자마자 dp로 풀어줘야겠구나 하는 생각이 들었다.(물론 문제에 아예 적혀있긴하다)아무튼 dp를 어떤식으로 활용하여 풀어주는가 이게 관건인데 이전열에서 올 수 있는 값중 최댓값을 계속해서 더해가는 방식으로 처리해주면 된다.이때 정수 삼각형을 배열로 작성

처음에 n의 범위가 꽤 커서 for문으로 각 범위에 대해 받을 때마다 해당 범위만큼 또 합계를 구해서 평균을 구하는 방식으로 하면 런타임에러가 나지 않을까 하는 생각이 들었다.근데 딱히 다른 방법이 떠오르는게 없어서 일단 해보았는데 다행히도 런타임에러는 안떴다.파이썬으

해당 문제는 사실 문제에서 부터 dfs/bfs 문제라고 주어져 있다. 다만 처음에 이 문제를 보고 플로이드 워셜로도 풀 수 있겠다고 생각이 들었는데 이 알고리즘으로 문제를 풀려고 하니 잘 안풀려서 일단 dfs 알고리즘으로 문제를 해결해주었다.dfs알고리즘으로 해결하는

문제 자체는 어렵지가 않은데 heap문제를 접해보지 않아서 heapq의 사용법을 몰라서 이 부분을 구글링을 통해 공부하여 문제를 해결해주었다.여기서 heap에 대해 정리를 해보자면 일단import heapq를 통해서 import를 먼저 진행해준다.기본적인 heap 사용

이 문제는 내가 풀었던 dfs/bfs 문제중에 가장 까다로웠던 문제였다.문제의 요점은 출근, 퇴근 길에 모두 방문 가능한 노드를 구하는것이때 유의할점은 출근할때는 s가 여러번 등장해도 되며 퇴근할 때에는 t가 여러번 등장해도 된다. 다만 목적지는 한번만 등장해야할 것문

처음에는 문제를 완전히 잘못 이해했다첫번째 징검다리부터 출발하여 이전에 밟은 돌보다 높이가 높은 돌이 나오면 이동하면서 개수를 세주는 방식으로 풀어주면 된다고 생각했기 때문이다.해당 문제에 첫번째 돌부터 밟아서 출발한다던가 하는 조건이 없기 때문에 어디서 시작할 지는

문제 처음 이 문제를 보고 2차원 리스트를 활용하여 i번째 리스트에는 i번 사람의 친구들의 무게를 담아줘서 그 리스트의 max 값의 i번 사람이 들 수 있는 무게보다 작다면 answer에 +1 해줘야겠다는 생각을 했다. 이때 인덱스 값과 회원번호는 1이 차이나므로

처음 이 문제를 보자마자 미로찾기 문제와 비슷하지만 상하좌우로 이동하는 것이 아닌 위로 u, 아래로 d 만큼 이동하는 문제구나 라는 생각이 들었다.그러므로 bfs 알고리즘을 이용하여 이 문제를 해결해주었다.처음에는 visited 리스트를 방문만 하면 1로 바꾸어 방문처

이 문제는 딱 봐도 DFS/BFS 문제다.그래서 생각한 것은 이중 for 문을 돌면서 1을 만나면 해당 좌표와 연결된 1 부분을 모두 계산한 후 방문처리 해주는 것을 반복해주기로 했다.해당 좌표와 연결된 1의 좌표를 구하는 함수를 bfs 로 두고 bfs 호출할 때마다

처음에 이 문제를 접했을 때에는 dfs를 통해 가능한 모든 경로를 탐색하면서 목적지에 도착할 때마다 ans 값에 +1을 해주어 해당 값을 답으로 출력해주려고 했다.이렇게 해서 테스트케이스에 대한 답은 출력했지만 시간초과라는 문제가 발생했다.아무리 생각해도 dfs로 푸

처음 이 문제를 접했을 때 bfs인가 생각은 했지만 구현하기가 어려워매일매일 1인 좌표의 상하좌우를 변경해주면서 날짜를 세는 방식으로 코드를 짰다.테스트케이스는 전부 출력되지만 시간초과가 발생하였다.그래서 구글링을 해본 결과 bfs를 사용하는데 살짝 응용해주어서 문제를

처음 이 문제를 보았을때는 공백이 들어가야하는 부분의 규칙을 찾아서 공백을 넣어주면 된다고 생각했다.이런식으로 직관적으로 숫자 규칙에 맞게 풀어주었다.하지만 이 방법은 추천하지 않는다. 왜냐하면 python으로 선택했을 때에는 시간초과가 발생하였고 pypy3로 해야지

이 문제는 전형적인 구역 개수 구하기 에서 살짝 변형된 문제이다.적록색약 환자가 보는 그림을 구해준다음에 두 그림에 대해서 구역의 개수를 구해주는 방식으로 문제를 풀었다.이때 유의할 점이 있는데 적록색약환자가 보는 그림을 만들어줄 때 원래의 그림을 넣어주고 이중 for

이 문제는 백준 7576번 문제와 굉장히 유사한 문제이다.다만 상자가 여러개 쌓이는 것으로 2차원 배열에서 3차원 배열이 됐음을 알 수 있다. 알고리즘을 공부하면서 3차원 배열에 대해서 다룰 일이 별로 없다보니 인덱스 값을 설정해주는 데에서 애를먹었다.어디가 x 좌표

처음 이 문제를 접했을 때 어떤 알고리즘으로 문제를 풀어야 할 지 뚜렷하게 생각나는 부분이 없어서 일단 주어진대로 구현을 해야겠다고 생각했다.집의 좌표와 치킨집의 좌표를 따로 리스트에 각각 저장해야겠다는 생각까지는 했으나 파이썬으로 combination을 사용하는 방법

처음에는 부분 수열이라는 것을 몰라서 문제를 이해하는데 어려움을 겪었다.문제를 이해한 후에도 어떻게 이 문제를 해결해줄지 고민을 하다가 구글링을 했다.도움을 받은 사이트: https://velog.io/@emplam27/%EC%95%8C%EA%B3%A0%EB%

이 문제를 보면 주어진 C개의 문자중 조건에 맞는 L개의 조합을 찾는 것이기 떄문에 combinations 를 사용해서 문제를 해결하였다.이 때 모음의 개수와 자음의 개수 체크는 모음이 담긴 리스트를 만들어서 이를 활용해서 체크해주었다.그리고 조건에 맞는 조합을 저장을

처음 이 문제를 봤을 때는 간단하게 해결 할 수 있는 문제라고 생각했다.그런데 조건을 보면 알겠지만 이 문제는 주어진 문제를 구현만 하는게 문제가 아니라 시간 최적화가 중요한 문제이다.왜냐하면 n이 무려 10만 이하의 수이기 때문이다.그렇기때문에 단순히 R이 나올때마다

이 문제는 문제에서 주어진 로직이 번거로워서 그렇지 구현자체는 bfs 를 이용하면 되는 문제이다.bfs를 활용한 미로 문제를 풀 때 처럼 구현을 해주지만 여기서 문제의 조건에 맞게 변형을 해주어서 문제를 해결했다.이때 처음 문제를 풀이했을 때 계속해서 오답이 나왔는데