결국 빛나리라

https://www.acmicpc.net/problem/18353 18353번: 병사 배치하기 첫째 줄에 N이 주어진다. (1 ≤ N ≤ 2,000) 둘째 줄에 각 병사의 전투력이 공백을 기준으로 구분되어 차례대로 주어진다. 각 병사의 전투력은 10,000,000보다 작거나 같은 자연수이다. www.acmicpc.net > 문제 풀이 아이디어 DP로 풀 수 있는 문제이다. 해당 문제에서 dp에는 최대 병사 인원 수가 들어간다. 푸는 논리는 다음과 같다. - 우선 dp를 병사 수만큼 1로 초기화한다. - 1 번째 병사는 0 번째 병사보다 전투력이 작으므로 연산을 수행한다. (0 번째 병사의 인원수 +1) 과 (1번째 병사의 인원 수) 중 큰 값을 dp[1]에 넣어준다. - 2 번째 병사는 0 번째 병사보..

https://www.acmicpc.net/problem/18352 18352번: 특정 거리의 도시 찾기 첫째 줄에 도시의 개수 N, 도로의 개수 M, 거리 정보 K, 출발 도시의 번호 X가 주어진다. (2 ≤ N ≤ 300,000, 1 ≤ M ≤ 1,000,000, 1 ≤ K ≤ 300,000, 1 ≤ X ≤ N) 둘째 줄부터 M개의 줄에 걸쳐서 두 개 www.acmicpc.net > 문제 풀이 아이디어 bfs와 최단거리 유형으로 풀 수 있다. - 시작점인 1을 큐(q)에 넣고 최단 거리정보를 나타낸 dist 리스트의 시작점엔 0을 넣는다. - 1에서 갈 수 있는 노드는 2와 3이므로 이들을 q에 차례로 넣는다. 동시에 최단거리는 (0+1)로 dist의 각 인덱스에 추가해준다. - 2에서 갈 수 있는 ..

https://www.acmicpc.net/problem/1874 1874번: 스택 수열 1부터 n까지에 수에 대해 차례로 [push, push, push, push, pop, pop, push, push, pop, push, push, pop, pop, pop, pop, pop] 연산을 수행하면 수열 [4, 3, 6, 8, 7, 5, 2, 1]을 얻을 수 있다. www.acmicpc.net > 문제 풀이 아이디어 - 스택의 마지막 값이 입력의 첫번째 값보다 작으면 스택에 1씩 증가시킨 수를 추가한다. - 스택의 마지막 요소 값과 입력의 첫번째 값이 일치하면 스택의 마지막 값과 입력의 첫번째 값을 뺀다. - 위 과정을 입력리스트가 빈 리스트가 될 때까지 반복한다. - 만일 스택의 마지막 요소 값이 입력의..

https://www.acmicpc.net/problem/10814 10814번: 나이순 정렬 온라인 저지에 가입한 사람들의 나이와 이름이 가입한 순서대로 주어진다. 이때, 회원들을 나이가 증가하는 순으로, 나이가 같으면 먼저 가입한 사람이 앞에 오는 순서로 정렬하는 프로그램을 www.acmicpc.net 나이 순으로 정렬할 수 있도록 정렬기준을 age로 설정하였다. > 정답코드 > 배운점 파이썬의 sort 메소드는 값이 같은 원소의 경우 선후관계가 바뀌지 않는 stable sort알고리즘을 사용한다. 따라서, 아래와 같이 선후관게 i를 튜플에 추가하고 정렬기준으로 설정할 필요가 없다. 문자열 형태의 숫자로 정렬하면 string 형식으로 정렬된다. age는 문자열 형태의 숫자이기 때문에 string형식으..

https://programmers.co.kr/learn/courses/30/lessons/77884 코딩테스트 연습 - 약수의 개수와 덧셈 두 정수 left와 right가 매개변수로 주어집니다. left부터 right까지의 모든 수들 중에서, 약수의 개수가 짝수인 수는 더하고, 약수의 개수가 홀수인 수는 뺀 수를 return 하도록 solution 함수를 완성해주 programmers.co.kr left부터 right 수 까지의 모든 수에 대한 약수를 리스트에 추가한 후 리스트 요소의 개수가 짝수이면 answer에 더하고 홀수면 빼는 로직을 구현해야 한다. 이렇게 문제에 나온 논리 그대로 코드를 구현하면 다음과 같다. 구현 자체는 굉장히 쉽지만 다른 사람의 풀이에서 좋은 아이디어를 얻었기에 이를 기억하..

https://programmers.co.kr/learn/courses/30/lessons/42889 코딩테스트 연습 - 실패율 실패율 슈퍼 게임 개발자 오렐리는 큰 고민에 빠졌다. 그녀가 만든 프랜즈 오천성이 대성공을 거뒀지만, 요즘 신규 사용자의 수가 급감한 것이다. 원인은 신규 사용자와 기존 사용자 사이에 스 programmers.co.kr > 정렬 딕셔너리를 선언해서 key값엔 stage 단계, value값엔 실패율을 담은 후, sorted로 정렬했다. 그런데 문제는 sorted에서 dict.items()로 정렬하는 과정에서 딕셔너리가 리스트+튜플 형태로 변하기 때문에, 리스트 내의 튜플에서 stage값만 추출하기 위해 다시 반복문을 돌렸다. * 마지막 스테이지까지 도달한 사람이 없을 경우(마지막..

https://www.acmicpc.net/problem/1018 1018번: 체스판 다시 칠하기 첫째 줄에 N과 M이 주어진다. N과 M은 8보다 크거나 같고, 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 보드의 각 행의 상태가 주어진다. B는 검은색이며, W는 흰색이다. www.acmicpc.net > 브루트포스 만약 입력된 사각형이 9*9라면 우리는 다음과 같은 방식으로 총 네가지 경우에서 바꿔 칠해야하는 사각형의 개수를 구해야한다. 반복해야 할 수는 각각 n-7, m-7번이라는 것을 알 수 있다. 4가지 경우에서 W로 시작하는 패턴, B로 시작하는 패턴, 이 두가지 경우의 패턴에 대해 모두 테스트해야한다. 나 같은 경우엔 그냥 반복해야하는 문자열 패턴을 pat1, pat2로 설정해..

https://www.acmicpc.net/problem/1541 1541번: 잃어버린 괄호 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 www.acmicpc.net > 그리디 괄호를 추가하여 식의 결과를 '최소'로 만드는 알고리즘을 구현해야한다. '-' 이전의 수들은 모두 더해주고 '-' 이후의 수들을 모두 빼주면 최소 값을 구할 수 있다. 예를 들어, 1+2-3+4-5 에서 '-' 는 두번 나온다. 우선 이 두개를 기준으로 괄호를 넣어주면 다음과 같이 표현된다. 1+2-(3+4)-(5) 그런데 위의 식은 사실상 아래의 식과 같다. (1+2)-(3+4+..

https://www.acmicpc.net/problem/10866 10866번: 덱 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 www.acmicpc.net > 덱 선입, 후입이 모두 가능한 deque 함수로 구현가능하다. 앞으로 넣을 땐 appendleft(), 뒤로 넣을 땐 append() 메서드를 사용한다. * 리스트를 활용한 풀이도 가능하다. 리스트에서 push front 기능을 작성할 때 insert(넣는 위치, 넣을 수) 메소드를 활용할 수 있다.

https://www.acmicpc.net/problem/1181 1181번: 단어 정렬 첫째 줄에 단어의 개수 N이 주어진다. (1 ≤ N ≤ 20,000) 둘째 줄부터 N개의 줄에 걸쳐 알파벳 소문자로 이루어진 단어가 한 줄에 하나씩 주어진다. 주어지는 문자열의 길이는 50을 넘지 않는다. www.acmicpc.net > 정렬 sort 메서드를 활용해 정렬한다. 정렬 조건으로 첫 번째는 단어의 길이, 두 번째는 단어 사전 순으로 설정했다. 같은 단어는 한번만 출력되기 때문에 8 line 이후의 출력 코드에서 if 문을 통해 이전의 단어와 같은 단어이면 출력되지 않도록 작성했다. * 정답으로 통과는 했으나 비효율적인 코드이다. ▶ 배운점 그렇다면 본 코드에서 비효율을 어떻게 개선할 수 있을까? 첫 번째..