알고리즘
[Python/파이썬 프로그래머스] 불량 사용자
programmers.co.kr/learn/courses/30/lessons/64064 코딩테스트 연습 - 불량 사용자 개발팀 내에서 이벤트 개발을 담당하고 있는 "무지"는 최근 진행된 카카오이모티콘 이벤트에 비정상적인 방법으로 당첨을 시도한 응모자들을 발견하였습니다. 이런 응모자들을 따로 모아 불량 programmers.co.kr 풀이 오랜시간 풀 수 있을거같다가 실패한 문제. 내가 푼 방식 리스트를 하나 만들어서 banned_id index별로 될수있는 값을 리스트에 전부 넣어줬는데 그렇게 되면 [ [frodo,fradi],[frodo,crodo],[abc123,frodoc],[abc123,frodoc]] 이렇게 만들어지는데 조건 어떻게 구현해야할지 몰라서 실패 결국 답보고 이해한 결과 순열을 써서 ..
[Python/파이썬 프로그래머스] 튜플
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 2019 카카오 개발자 겨울 인턴십 문제 풀이 우선 주어진 s의 값을 replace를 써서 다듬고 리스트 형변환을 시켜줬씁니다. 그 다음 출력값이 입력 index에 상관없이 입력 갯수가 작은거부터 출력시켜줘야해서 cnt 값에 갯수랑 index값을 넣어준 뒤 cnt 값 따라가면서 flag로 기존에 존재하는 값인지 체크해주고 없..
[Python/파이썬 11057 백준] 오르막 수 (다이나믹 프로그래밍)
www.acmicpc.net/problem/11057 11057번: 오르막 수 오르막 수는 수의 자리가 오름차순을 이루는 수를 말한다. 이때, 인접한 수가 같아도 오름차순으로 친다. 예를 들어, 2234와 3678, 11119는 오르막 수이지만, 2232, 3676, 91111은 오르막 수가 아니다. 수 www.acmicpc.net 풀이 10844 쉬운 계단수 문제랑 굉장히 유사한 문제입니다.. 유사한 문제 풀어보면 쉽게 풀리네용... 주의할 점은 첫번째 0인 숫자가 들어갈 수 있다는거구, 오름차순 숫자 갯수를 찾아야합니다. 또한 이차원 리스트 사용 숫자를 일일히 구하다보면 공통점이 있는데 마지막 수가 0일 경우 다음 숫자는 1~9가 가능하고 1일 경우 2~9 2일 경우 3~9 . . . 9는 다음 숫자..
[Python/파이썬 백준 13913] 숨바꼭질 4 (BFS)
www.acmicpc.net/problem/13913 13913번: 숨바꼭질 4 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 풀이 다른 숨바꼭질 문제랑 같지만 path를 하나 더 써줘서 nx 인덱스에 전에 방문했던 x를 넣어줬습니다. 그 뒤 path[end]에 값을 따라가다보면 start가 나오게됩니다. import sys from collections import deque input=sys.stdin.readline start,end=map(int,input().split()) graph=[-1]..
[Python/파이썬 15990 백준] 1, 2, 3 더하기 5
www.acmicpc.net/problem/15990 15990번: 1, 2, 3 더하기 5 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 1,000,000,009로 나눈 나머지를 출력한다. www.acmicpc.net 풀이 1차원으로 계속 규칙을 찾으려니 30분정도 봤는데 못찾았다.. 어렵네용... 답을 참고해서 이해한 내용을 적자면 dp [1], dp[2], dp[3]에 각각 1,2,3으로 끝나는 상황을 넣는다. ex) dp[3] 은 2 1 1 2 3 이 예시와 같이 끝나는 숫자가 1일때 2일때 3일때 각각 1개씩이다 그 후 n이 만약 6인 상황에서 dp[5]에서 2로 끝난거 +1을 해주거나, 3으로 끝난거에 +1을 해주면 -> dp[6][0] dp[4]에서 1로 끝난거에 ..
[Python/파이썬 13549 백준] 숨바꼭질 3
www.acmicpc.net/problem/13549 13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 풀이 bfs문제입니다. 2*x, x-1, x+1인 경우에서 2*x 인 경우 : 순간이동하므로 시간 +0, appendleft해서 가장 우선순위로 설정하여 1000001까지 최단시간 미리 구해줌 x-1,x+1인 경우 : +1씩 더해줌 풀면서 시간초과 났었는데 apppendleft를 안써주고 if문으로 하나하나씩 정의해줘서 시간초과났음... import sys from collec..
[Python/파이썬 3055 백준] 탈출
www.acmicpc.net/problem/3055 3055번: 탈출 사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 한다. 이 숲에는 고슴도치가 한 마리 살고 있다. 고슴도치는 제 www.acmicpc.net 풀이 bfs 문제인데 물의 경로가 고슴도치에 영향을 주는 문제 처음 물(*)을 bfs 돌려서 check_water에 시간을 넣어줬습니다. 이 과정에서 물이 여러 개인 경우랑 두번째 물 bfs 일 경우 시간이 더 적게 걸리는 상황으로 걸러줬습니다. 다음 고슴도치(S) bfs 돌려서 물이 아예 없을 경우와 물보다 빨리 고슴도치가 움직인 경우를 걸러줬습니다. 제출과정에서 계속 10%에서 불통됐는데 반례가 D.. ... ..S 이..
[Python/파이썬 4963 백준] 섬의 개수
풀이 일반적인 bfs 문제인데 대각선만 추가됐습니다. bfs 돌때마다 cnt+=1 씩해줬습니다. import sys from collections import deque input=sys.stdin.readline queue=deque() dx=[0,0,1,-1, 1,1,-1,-1] dy=[1,-1,0,0, 1,-1,1,-1] def bfs(x,y): check[x][y]=True queue.append((x,y)) while queue: x,y=queue.popleft() for i in range(8): nx=x+dx[i] ny=y+dy[i] if 0
[Python/파이썬 11724 백준] 연결 요소의 개수
www.acmicpc.net/problem/11724 11724번: 연결 요소의 개수 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주 www.acmicpc.net 풀이 처음에 연결요소를 몰라서 구글링한 결과 그냥 이어진 덩어리를 말하는거 였네요. 간선으로 이어졌으면 한 덩어리입니다. 그래서 이 문제는 dfs나 bfs로 0~n 점까지 bfs를 써서 이어진 모든 점들을 구해주고 방문한 점은 check를 True로 하여 몇번 bfs 돌렸는지 갯수를 셌습니다! # 연결 요소의 개수 import sys from col..
백준 알고리즘 문제 100개 달성!!!
4월까지 200개가 목표긴 한데 되려나... 처음에 자료구조 위주로 스택 큐 등등 풀었습니다. 그르다가 알고리즘 구현,그리디,dp,bfs,그래프 등 맛보기로 풀다가 bfs문제가 재밌어서 bfs 위주로 풀었네용 다음에 삼성 기출 문제 맛봤는데 푸는것도 10문제 풀면 3,4개 풀긴 하는데 이게 공부가 되는건가 싶어서 지금은 다시 기초를 제대로 잡아야겠다 생각해서 저기 백준 문제집에 코드플러스?? 저거 sw역량 테스트 준비까지 다 푸려고 계획중입니다.. 30분에서 한시간정도 잡고 풀 수 있을거 같으면 계속 풀고 문제 못풀면 검색해서 답 보면서 이해하는 식으로 하구있어용... 올여름까지 300문제가 목표 다들 화이또!!